Well, that was unexpected

Calculus Level 5

Let S = 0 S=0 .

Pick a random real number k k from a uniform distribution on [ 0 , 1 ] [0,1] . Then add k k to S S : if S < 1 S<1 then repeat the process and add another number. If S 1 S\ge1 then the process ends.

What is the expected value of S S ?

Credit to a teacher for showing me this problem


The answer is 1.35914.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Mark Hennings
Oct 22, 2016

I am grateful to Plinio Sd for pointing out a gap in the previous version of this proof.

Let X n X_n be the value of the n n th random variable, and let S n = j = 1 n X j S_n = \sum_{j=1}^n X_j be the sum of the first n n of them. Let N N be the number of RVs that are needed to make the sum greater than 1 1 , so that the random variable we want is S = S N S=S_N . So long as 0 < x 1 0<x\le1 , P [ S n < x ] = 0 x P [ S n 1 < x y ] d y \mathbb{P}[S_n<x]=\int_0^x \mathbb{P}[S_{n-1}<x-y]\,dy so a simple induction gives P [ S n < x ] = x n n ! 0 < x 1 \mathbb{P}[S_n<x]=\frac{x^n}{n!} \hspace{1cm}0<x\le1 Thus P [ N = n ] = [ S n 1 < 1 S n ] = 1 ( n 1 ) ! 1 n ! = n 1 n ! n 2 \mathbb{P}[N=n]=\mathbb[S_{n-1}<1\le S_n]=\frac{1}{(n-1)!}-\frac{1}{n!}=\frac{n-1}{n!} \hspace{1cm}n \ge2 Although we do not have the full probability density function f n f_n for S n S_n it is clear that f n ( x ) = x n 1 ( n 1 ) ! 0 x 1 f_n(x) \; = \; \frac{x^{n-1}}{(n-1)!} \hspace{1cm} 0 \le x \le 1 Moreover P [ S 1 + x a n d N = n ] = 0 1 f n 1 ( y ) P [ 1 y X n 1 + x y ] d y = 0 x f n 1 ( y ) P [ 1 y X n 1 ] d y + x 1 f n 1 ( y ) P [ 1 y X n 1 + x y ] d y = 0 x f n 1 ( y ) y d y + x x 1 f n 1 ( y ) d y = x ( n 1 ) ! x n n ! \begin{aligned} \mathbb{P}[S \le 1+x \; \mathrm{and}\; N = n] & = \; \int_0^1 f_{n-1}(y)\mathbb{P}[1-y \le X_n \le 1+x-y]\,dy \\ & = \; \int_0^x f_{n-1}(y)\mathbb{P}[1-y \le X_n \le 1]\,dy + \int_x^1 f_{n-1}(y) \mathbb{P}[1-y \le X_n \le 1+x-y]\,dy \\ & = \; \int_0^x f_{n-1}(y)y\,dy + x\int_x^1 f_{n-1}(y)\,dy \; = \; \frac{x}{(n-1)!} - \frac{x^n}{n!} \end{aligned} and hence E [ S N = n ] P [ N = n ] = 0 1 ( 1 + x ) d d x [ x ( n 1 ) ! x n n ! ] d x = 0 1 ( 1 + x ) [ 1 ( n 1 ) ! x n 1 ( n 1 ) ! ] d x = 3 n 2 n 2 2 ( n + 1 ) ! \begin{aligned} \mathbb{E}[S|N=n]\,\mathbb{P}[N=n] & = \; \int_0^1 (1+x)\,\frac{d}{dx}\left[\frac{x}{(n-1)!} - \frac{x^n}{n!}\right]\,dx \; = \; \int_0^1 (1+x)\left[\frac{1}{(n-1)!} - \frac{x^{n-1}}{(n-1)!}\right]\,dx \\ & = \; \frac{3n^2 - n - 2}{2(n+1)!} \end{aligned} for any n 2 n \ge 2 , and hence E [ S ] = E [ E [ S N ] ] = n 2 E [ S N = n ] P [ N = n ] = n 2 3 n 2 n 2 2 ( n + 1 ) ! = 1 2 n 2 [ 3 ( n 1 ) ! 4 n ! + 2 ( n + 1 ) ! ] = 1 2 e \begin{aligned} \mathbb{E}[S]& =\; \mathbb{E}[\mathbb{E}[S|N]]\;=\;\sum_{n \ge 2} \mathbb{E}[S|N=n]\,\mathbb{P}[N=n] \\ & = \; \sum_{n \ge 2} \frac{3n^2 - n - 2}{2(n+1)!} \; = \; \frac12\sum_{n \ge 2} \left[ \frac{3}{(n-1)!} - \frac{4}{n!} + \frac{2}{(n+1)!}\right] \\ & = \; \tfrac12e \end{aligned} making the answer 1.359140 \boxed{1.359140} .

Could you tell me what is E and P here? These signs are completely new to me.

MD Rahman - 4 years, 5 months ago

Log in to reply

Expectation and probability.

Mark Hennings - 4 years, 5 months ago

I think the second equation is not correct. If n = 10 n=10 , then E [ S N = 10 ] = 5 \mathbb{E}[S|N=10]=5 . But, it does not make sense that E [ S N = 10 ] > 2 \mathbb{E}[S|N=10] > 2 . I guess the problem lies in the fact that N N is not independent from X j X_j . For example, if X 1 = 0.99 X_1=0.99 , then it is very likely that N = 2 N=2 .

Plinio SD - 3 years, 6 months ago

Log in to reply

What we are doing here is a rather delicate separation of the process into two parts. Remember that S = S N S = S_N .

We could have a set-up where N N is equal to the value I obtain when rolling a 6 6 -sided die Then it is still true (for example) that E [ S N N = 20 ] = E [ S 20 ] = 10 \mathbb{E}[S_N|N=20] \; = \; \mathbb{E}[S_{20}] \; = \; 10 for example, even though S = S N S=S_N cannot exceed 6 6 . The point is that what is actually possible is strictly controlled by the probability distribution of N N , which handles the different conditional expectations. In the above example, the probability that N = 20 N=20 is 0 0 , which means that the counter-intuitive conditional expectation does not contribute.

Mark Hennings - 3 years, 6 months ago

Log in to reply

I agree with your example. But, in the case of this example, the rolling of the die is independent from the sequence { X j } j \{X_j\}_j . However, in the case of the problem this does not hold. In fact, I have found that for n 2 n\ge 2 , E [ S N = n ] = 1 + n 2 ( 1 + n ) . \mathbb{E}[S|N=n] = 1 + \frac{n}{2(1+n)}. This also leads to the correct result, since E [ S ] = n 2 E [ S N = n ] P ( N = n ) = n 2 ( n 1 ) ( 2 + 3 n ) 2 ( n + 1 ) ! = e 2 . \mathbb{E}[S] = \sum_{n\ge 2} \mathbb{E}[S|N=n]\mathbb{P}(N=n) = \sum_{n\ge 2} \frac{(n-1)(2+3n)}{2(n+1)!} = \frac{e}{2}.

Plinio SD - 3 years, 6 months ago

Log in to reply

@Plinio Sd You are right. It means that things are more complex algebraically. I have modified my proof to suit.

Mark Hennings - 3 years, 6 months ago

Log in to reply

@Mark Hennings Nice! I upvoted your solution :)

Plinio SD - 3 years, 6 months ago

Let the process stop after the n n th time .

The condition for this is we pick x 1 , x 2 . . . . . . . . . . x n x_{1},x_{2}..........x_{n} and x n + 1 x_{n+1} such that x 1 + x 2 + . . . . . x n < 1 \displaystyle x_{1}+x_{2}+.....x_{n}<1 and x 1 + x 2 + x 3 + . . . . . x n + x n + 1 > 1 \displaystyle x_{1}+x_{2}+x_{3}+.....x_{n}+x_{n+1}>1 .

Let A A denote the event that x 1 + x 2 + . . . . . . . . x n < 1 \displaystyle x_{1}+x_{2}+........x_{n}<1 and B B denote the event that x 1 + x 2 + x 3 + . . . . . + x n + x n + 1 > 1 \displaystyle x_{1}+x_{2}+x_{3}+.....+x_{n}+x_{n+1}>1 .

We need P ( A B ) P(A\cap B) in order to calculate expectation.

P ( A B ) = P ( A ) P ( B A ) P(A\cap B) = P(A)\cdot P(B\vert A) . [Here P ( B A ) P(B\vert A) denotes the probability of event B B given that event A A has happened] .

So let us calculate P ( A ) P(A) .

The probability of this event is given by Volume of a standard n-simplex Volume of unit Hypercube in n-dimension \displaystyle \frac{\text{Volume of a standard n-simplex}}{\text{Volume of unit Hypercube in n-dimension}} .

The volume of the standard n-simplex can be found using calculus.

0 1 0 1 x n 0 1 x n 1 x n . . . . . . 0 1 x 3 . . . . . . x n 1 x n 0 1 x 2 x 3 . . . . . . x n 1 x n d x 1 d x 2 d x 3 . . . . . . d x n 1 d x n = 1 n n ! = 1 n ! \displaystyle \int_{0}^{1}\int_{0}^{1-x_{n}}\int_{0}^{1-x_{n-1}-x_{n}}......\int_{0}^{1-x_{3}-......-x_{n-1}-x_{n}}\int_{0}^{1-x_{2}-x_{3}-......-x_{n-1}-x_{n}} \,dx_{1}\,dx_{2}\,dx_{3}......dx_{n-1}\,dx_{n} = \frac{1^{n}}{n!}=\frac{1}{n!} .

Hence P ( A ) = 1 n ! \displaystyle P(A) = \frac{1}{n!}

Now to find P ( B A ) P(B\vert A) let us call ( x 1 + x 2 + . . . . . . . . x n ) = z \left(x_{1}+x_{2}+........x_{n}\right) = z .

So the P ( B A ) P(B\vert A) is identical to finding the probability of P ( z + x n + 1 ) < 1 P(z+x_{n+1}) <1 where z z and x n + 1 x_{n+1} are uniformly and randomly selected from ( 0 , 1 ) (0,1) which is an easy two dimensional problem. We can even apply basic geometry to solve it . It would be the area of the triangle formed by the line x + y = 1 x+y=1 and the coordinate axis . But let us do it by the above simplex concept as a 2 -simplex 2\text{-simplex} is just a line.

P ( B A ) = 0 1 0 1 x n + 1 d z d x n + 1 = 1 2 \displaystyle P(B\vert A) =\int_{0}^{1}\int_{0}^{1-x_{n+1}}\,dz\,dx_{n+1} = \frac{1}{2} .

Hence P ( A B ) = 1 2 n ! \displaystyle P(A\cap B) = \frac{1}{2\cdot n!}

Hence the expectation E ( S ) \text{E}(S) is given by E ( S ) = n = 1 n P ( A B ) = n = 1 n 2 n ! = 1 2 n = 1 1 ( n 1 ) ! = e 2 \displaystyle \text{E}(S)=\sum_{n=1}^{\infty} n\cdot P(A\cap B) = \sum_{n=1}^{\infty}\frac{n}{2\cdot n!} = \frac{1}{2}\sum_{n=1}^{\infty}\frac{1}{(n-1)!} = \frac{\text{e}}{2} .

Useful wiki :- Simplex .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...