 Two Plus Two Older Archives Pure probability question
 FAQ Members List Calendar Search Today's Posts Mark Forums Read #1
 bobman0330 Member Join Date: Aug 2004 Posts: 52 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 &gt; 1?
#2
 pzhon Member Join Date: Mar 2004 Posts: 66 Re: Pure probability question

<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
 pzhon Member Join Date: Mar 2004 Posts: 66 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.
#4
 gaming_mouse Senior Member Join Date: Oct 2004 Location: my hero is sfer Posts: 2,480 Re: Pure probability question

[ QUOTE ]
<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
 pzhon Member Join Date: Mar 2004 Posts: 66 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.
#6
 pzhon Member Join Date: Mar 2004 Posts: 66 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>
#7
 gaming_mouse Senior Member Join Date: Oct 2004 Location: my hero is sfer Posts: 2,480 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)?
#8
 pzhon Member Join Date: Mar 2004 Posts: 66 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.
#9
 gaming_mouse Senior Member Join Date: Oct 2004 Location: my hero is sfer Posts: 2,480 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
#10
 bobman0330 Member Join Date: Aug 2004 Posts: 52 Re: Pure probability question

it is not immediately (or, to me, eventually) apparent why P(requiring draw N) = 1/(n-1)! Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Two Plus Two     Two Plus Two Internet Magazine     About the Forums     MOD DISCUSSION     ISOP General Poker Discussion     Texas Hold'em     Beginners Questions     Books and Publications     Televised Poker     News, Views, and Gossip     Brick and Mortar     Home Poker     Poker Beats, Brags, and Variance     Poker Theory Limit Texas Hold'em     Mid- and High-Stakes Hold'em     Medium Stakes Hold'em     Small Stakes Hold'em     Micro-Limits     Mid-High Stakes Shorthanded     Small Stakes Shorthanded PL/NL Texas Hold'em     Mid-, High-Stakes Pot- and No-Limit Hold'em     Medium-Stakes Pot-, No-Limit Hold'em     Small Stakes Pot-, No-Limit Hold'em Tournament Poker     Multi-table Tournaments     One-table Tournaments Other Poker     Omaha/8     Omaha High     Stud     Other Poker Games General Gambling     Probability     Psychology     Sports Betting     Other Gambling Games     Rake Back     Computer Technical Help Internet Gambling     Internet Gambling     Internet Bonuses     Software 2+2 Communities     Other Other Topics Other Topics     Sporting Events     Politics     Science, Math, and Philosophy     The Stock Market

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