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.

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>

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>