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<x<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<x<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<x<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)| <= 1/2 Max |h(z)| where x-1<=z<=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)| <= Integral |x-z| |h(z)|dz from z=x-1 to z=x
<= Integral |x-z| Max |h(z)| dz from z=x-1 to z=x
<= (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| < 1/2^x for x>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)|>= 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>
|