Two Plus Two Older Archives

Two Plus Two Older Archives (http://archives2.twoplustwo.com/index.php)
-   Probability (http://archives2.twoplustwo.com/forumdisplay.php?f=23)
-   -   Pure probability question (http://archives2.twoplustwo.com/showthread.php?t=303538)

bobman0330 07-29-2005 07:32 PM

Pure probability question
 
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?

pzhon 07-29-2005 07:47 PM

Re: Pure probability question
 
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?

pzhon 07-30-2005 05:51 PM

Re: Pure probability question
 
[ 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.

gaming_mouse 08-01-2005 01:14 AM

Re: Pure probability question
 
[ 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?

pzhon 08-01-2005 01:57 AM

Re: Pure probability question
 
[ 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&lt;x2&lt;x3&lt;...&lt;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.

pzhon 08-01-2005 02:04 AM

Re: Pure probability question
 
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&lt;x&lt;0, so for 0&lt;x&lt;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&lt;x&lt;=1. f(1)=e. </font>

gaming_mouse 08-01-2005 01:57 PM

Re: Pure probability question
 
[ 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&lt;x2&lt;x3&lt;...&lt;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)?

pzhon 08-01-2005 04:35 PM

Re: Pure probability question
 
[ 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.

gaming_mouse 08-01-2005 04:49 PM

Re: Pure probability question
 
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

bobman0330 08-01-2005 05:37 PM

Re: Pure probability question
 
it is not immediately (or, to me, eventually) apparent why P(requiring draw N) = 1/(n-1)!


All times are GMT -4. The time now is 08:06 AM.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2024, vBulletin Solutions Inc.