Two Plus Two Older Archives  

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

Reply
 
Thread Tools Display Modes
  #11  
Old 08-01-2005, 06:08 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 ]
it is not immediately (or, to me, eventually) apparent why P(requiring draw N) = 1/(n-1)!

[/ QUOTE ]

check out pzhon's responses to my questions.... he gives two different proofs.
Reply With Quote
  #12  
Old 08-03-2005, 07:03 PM
irchans irchans is offline
Senior Member
 
Join Date: Sep 2002
Posts: 157
Default Why is the answer 2000 + a/b?

[ QUOTE ]
[ 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.

[/ QUOTE ]

OK,
This problem seems difficult. After a fair amount of work (solving ODE's) I got a general expression, f[n], for the expected number of random numbers needed to exceed an integer n. When I compute the value of this expression for various values of n, it is very very near to 2*n+ a/b for two rather small integers a and b. (See pzhon's post.) I have no idea why the answer is so close to this fraction. The values for f[n], a, and b are given below in white with some more details.


<font color="white"> I got that the expected number of random numbers needed to exceed n is exactly

f[n] = Sum[ (-n + i)^i/i! Exp[n - i], {i, 0, n}].

For
n=1 f[n] = 2.7182818284590452354 = e
n=2 f[n] = 4.6707742704716049919 = e^2 - e
n=3 f[n] = 6.6665656395558899041 = e^3 - 2 e^2 + e/2
n=4 f[n] = 8.6666044900326954372
n=5 f[n] = 10.666662068622411858
n=6 f[n] = 12.666667141378121401
n=7 f[n] = 14.666666781522143450
n=8 f[n] = 16.666666670426887824
n=9 f[n] = 18.666666665270321349
n=10 f[n] = 20.666666666476318801
n=11 f[n] = 22.666666666669991177
n=12 f[n] = 24.666666666669900329
n=13 f[n] = 26.666666666666922273
n=14 f[n] = 28.666666666666641305
n=15 f[n] = 30.666666666666660344
n=16 f[n] = 32.666666666666666457
n=17 f[n] = 34.666666666666666744
n=18 f[n] = 36.666666666666666677
n=19 f[n] = 38.666666666666666666
n=20 f[n] = 40.666666666666666666

So I figure to get a sum of 1000, you need an average of 2000+2/3 random numbers. As I said, I have no idea why f[n] is approximately equal to 2*n + 2/3.

pzhon, you said "It's easy to see ...". Do you care to enlighten us?

</font>
Reply With Quote
  #13  
Old 08-04-2005, 05:23 AM
pzhon pzhon is offline
Member
 
Join Date: Mar 2004
Posts: 66
Default Re: Why is the answer 2000 + a/b?

Followup answer in white:
<font color="white">
To justify that the answer is very roughly 2000, you can use the Central Limit Theorem.

To get the exact answer, you can solve some lag differential equations for f(x) = Expected number of draws before the total is at least x, namely f'(x)=f(x)-f(x-1). Numerically, you can see that f(n) is very close to 2n+2/3. However, as irchans points out, this is not obvious from the form of the exact answer.

Here is a way to prove that f(x) is asymptotic to 2x+2/3:

[img]/images/graemlins/diamond.gif[/img] For simplicity, consider g(x) = f(x)-2x. This simplifies the integral equation:

f(x) = 1 + integral f(z)dz from z=x-1 to z=x, f(x)=0 on -1&lt;x&lt;0.

g(x)
= -2x + f(x)
= -2x + 1 + integral f(z)dz from z=x-1 to z=x
= -2x + 1 + integral (g(z) + 2z)dz from z=x-1 to z=x
= -2x + 1 + integral 2zdz + integral g(z)dz from z=x-1 to z=x
= -2x + 1 + x^2 - (x-1)^2 + integral g(z)dz from z=x-1 to z=x
= integral g(z)dz from z=x-1 to z=x.

Note that g(x) = -2x on -1&lt;x&lt;0.

[img]/images/graemlins/diamond.gif[/img] If g is asymptotic to some constant, what must that constant be? It would help to find some sort of weighted average of g on an interval that is preserved by the progression of the integral equation. Then we can compute that weight for -2x on -1&lt;x&lt;0, and compare this with the weight of a constant function.

On the interval [0,1], geometric considerations suggest weighting g(z) by z, since the value of g(z) will be used to determine g(1) through g(1+z). To make the total weight 1, we'll use the weight 2z on [0,1]. We're in luck: this weighted average is the same for all unit intervals.

[img]/images/graemlins/diamond.gif[/img]Claim: The integral of 2z g(x+z)dz from z=0 to z=1 does not depend on x.

Proof: By Leibniz,

d/dx integral 2z g(x+z)dz from z=0 to z=1

= integral 2z g'(x+z)dz from z=0 to z=1

= - integral 2 g(x+z)dz from z=0 to z=1
+ 2z g(x+z) evaluated from z=0 to z=1 (integration by parts)

= - integral 2 g(x+z)dz from z=0 to z=1
+ 2(1) g(x+1) - 2(0) g(x+0)

= -integral 2 g(z)dz from z=x to z=x+1 + 2 g(x+1)

= -2 g(x+1) + 2 g(x+1)

= 0

Since the derivative is 0, this function is constant.

[img]/images/graemlins/diamond.gif[/img] If g is asymptotic to some constant, it must be asymptotic to the weighted average on [-1,0],

integral 2z g(z-1)dz from z=0 to z=1

= integral 2z (-2)(z-1)dz from z=0 to z=1

= 2/3

Therefore, the only possible linear asymptote of f(x) is 2x+2/3.

[img]/images/graemlins/diamond.gif[/img] We still need to establish that g(x) is asymptotic to 2/3, or equivalently, than h(x)=g(x)-2/3=f(x)-2x-2/3 is asymptotic to 0.

Claim: |h(x)| &lt;= 1/2 Max |h(z)| where x-1&lt;=z&lt;=x.

Proof:

From the integral equation for g,

h(x) = Integral h(z)dz from z=x-1 to z=x.

From the conserved weighted average for g,

0 = Integral (z-(x-1)) h(z)dz from z=x-1 to z=x.

Subtracting,

h(x) = Integral (x-z) h(z)dz from z=x-1 to z=x.

|h(x)| &lt;= Integral |x-z| |h(z)|dz from z=x-1 to z=x

&lt;= Integral |x-z| Max |h(z)| dz from z=x-1 to z=x

&lt;= (Max |h(z)| on [x-1,x]) Integral |x-z|dz from z=x-1 to z=x

= (Max |h(z)| on [x-1,x]) 1/2

That's what we were trying to prove.

[img]/images/graemlins/diamond.gif[/img] Claim: |f(x)-2x-2/3| &lt; 1/2^x for x&gt;0.

Proof: This is satisfied for x on [0,1].

Suppose there is a nonempty set of exceptions. Let X be the infimum. By the continuity of f, it must be that |h(X)|=1/2^X. By the previous lemma, |h(z)|&gt;= 2/2^X somewhere on the interval [X-1,X], which contradicts the assumption that X was the infimum of the set of exceptions. The set of exceptions must be empty.

So, f(x) is asymptotic to 2x+2/3, and we have an exponentially decreasing bound on the error.

</font>
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 10:47 PM.


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