Two Plus Two Older Archives  

Go Back   Two Plus Two Older Archives > General Gambling > Probability

Reply
 
Thread Tools Display Modes
  #1  
Old 07-29-2005, 07:32 PM
bobman0330 bobman0330 is offline
Member
 
Join Date: Aug 2004
Posts: 52
Default 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?
Reply With Quote
  #2  
Old 07-29-2005, 07:47 PM
pzhon pzhon is offline
Member
 
Join Date: Mar 2004
Posts: 66
Default 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?
Reply With Quote
  #3  
Old 07-30-2005, 05:51 PM
pzhon pzhon is offline
Member
 
Join Date: Mar 2004
Posts: 66
Default 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.
Reply With Quote
  #4  
Old 08-01-2005, 01:14 AM
gaming_mouse gaming_mouse is offline
Senior Member
 
Join Date: Oct 2004
Location: my hero is sfer
Posts: 2,480
Default 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?
Reply With Quote
  #5  
Old 08-01-2005, 01:57 AM
pzhon pzhon is offline
Member
 
Join Date: Mar 2004
Posts: 66
Default 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.
Reply With Quote
  #6  
Old 08-01-2005, 02:04 AM
pzhon pzhon is offline
Member
 
Join Date: Mar 2004
Posts: 66
Default 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>
Reply With Quote
  #7  
Old 08-01-2005, 01:57 PM
gaming_mouse gaming_mouse is offline
Senior Member
 
Join Date: Oct 2004
Location: my hero is sfer
Posts: 2,480
Default 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)?
Reply With Quote
  #8  
Old 08-01-2005, 04:35 PM
pzhon pzhon is offline
Member
 
Join Date: Mar 2004
Posts: 66
Default 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.
Reply With Quote
  #9  
Old 08-01-2005, 04:49 PM
gaming_mouse gaming_mouse is offline
Senior Member
 
Join Date: Oct 2004
Location: my hero is sfer
Posts: 2,480
Default 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
Reply With Quote
  #10  
Old 08-01-2005, 05:37 PM
bobman0330 bobman0330 is offline
Member
 
Join Date: Aug 2004
Posts: 52
Default Re: Pure probability question

it is not immediately (or, to me, eventually) apparent why P(requiring draw N) = 1/(n-1)!
Reply With Quote
Reply

Thread Tools
Display Modes

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 Jump


All times are GMT -4. The time now is 07:45 PM.


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