![]() |
#1
|
|||
|
|||
![]()
OK, here's one I got from a friend of a friend.
You have a uniform random distribution from (0,1). You repeatedly take numbers from this distribution and add them up. WHat is the expected number of times you will draw before you have a number > 1? |
#2
|
|||
|
|||
![]()
Answer in white:
<font color="white">e=1+1+1/2+1/6+1/24+...+1/n!+... The probability that the sum of the first n is at most 1 is 1/n!. </font> Followup: Suppose you add the numbers up until you get 1000. Roughly how many do you expect it to take? |
#3
|
|||
|
|||
![]()
[ QUOTE ]
Followup: Suppose you add the numbers up until you get 1000. Roughly how many do you expect it to take? [/ QUOTE ] It's easy to see that the average is a bit more than 2000. Here is a hint: The average is about 2000+a/b, where a and b are small integers. Of course, the problem is not just to determine a/b, but also to justify it. |
#4
|
|||
|
|||
![]()
[ QUOTE ]
Answer in white: <font color="white">e=1+1+1/2+1/6+1/24+...+1/n!+... The probability that the sum of the first n is at most 1 is 1/n!. </font> [/ QUOTE ] pzhon, i can verify this by doing the multiple integral directly for the first few terms, but i don't see the trick behind this one line proof. can you explain? |
#5
|
|||
|
|||
![]()
[ QUOTE ]
[ QUOTE ] The probability that the sum of the first n is at most 1 is 1/n!. [/ QUOTE ] i can verify this by doing the multiple integral directly for the first few terms, but i don't see the trick behind this one line proof. can you explain? [/ QUOTE ] I presume you mean the statement above. The part of the n-dimensional hypercube below the hyperplane x1+x2+...+xn=1 is a pyramid over the n-1 dimensional case. This has an n-dimensional volume of 1/n times the (n-1)-volume of the base, so the volume is 1/n! by induction. There is also a volume-preserving linear transformation that takes the part with sum less than or equal to 1 to the part of the unit n-cube with x1<x2<x3<...<xn: x1' = x1 x2' = x1+x2 x3' = x1+x2+x3 ... xn' = z1+x2+x3+...+xn. This part of the unit n-cube has volume 1/n! by symmetry, as there are n! possible orderings of the coordinates. |
#6
|
|||
|
|||
![]()
Alternate solution in white:
<font color="white">Let f(x) be the expected number of terms before the sum is at least x. f(x) = 1 + Integral with respect to z of f(z) from z=x-1 to z=x. f'(x)=f(x)-f(x-1). f(x)=0 for -1<x<0, so for 0<x<1, f'(x)=f(x). The limit of f(x) as x decreases to 0 is 1, so by solving this differential equation with initial condition f(0)=1, f(x)=e^x on 0<x<=1. f(1)=e. </font> |
#7
|
|||
|
|||
![]()
[ QUOTE ]
I presume you mean the statement above. The part of the n-dimensional hypercube below the hyperplane x1+x2+...+xn=1 is a pyramid over the n-1 dimensional case. This has an n-dimensional volume of 1/n times the (n-1)-volume of the base, so the volume is 1/n! by induction. There is also a volume-preserving linear transformation that takes the part with sum less than or equal to 1 to the part of the unit n-cube with x1<x2<x3<...<xn: x1' = x1 x2' = x1+x2 x3' = x1+x2+x3 ... xn' = z1+x2+x3+...+xn. This part of the unit n-cube has volume 1/n! by symmetry, as there are n! possible orderings of the coordinates. [/ QUOTE ] Thanks pzhon. Both of those solutions are nice, especially the second. But why did you write out the expansion for e, as though the statement below it followed directly from that expansion (in your original answer in white)? |
#8
|
|||
|
|||
![]()
[ QUOTE ]
But why did you write out the expansion for e, as though the statement below it followed directly from that expansion (in your original answer in white)? [/ QUOTE ] # draws necessary = Z1 + Z2 + Z3 + ... where Zi = 0 if the ith draw was not necessary Zi = 1 if the ith draw was necessary (which happens with probability 1/(i-1)! ) The expected number of draws necessary is the sum of the probabilities of requiring the first draw (1/0!), the second draw (1/1!), the third draw (1/2!), etc. |
#9
|
|||
|
|||
![]()
ahhh... i got it. i didn't realize that was the expectation. i thought the statement below it was supposted to follow from it, rather than the other way around.
thanks, gm |
#10
|
|||
|
|||
![]()
it is not immediately (or, to me, eventually) apparent why P(requiring draw N) = 1/(n-1)!
|
![]() |
|
|