Math puzzle: Breaking the camel's back.

[pzhon]

[ QUOTE ]
Part 3: Produce a method for determining the asymptotics for some more general continuous weight distributions, such as the square of a uniformly distributed random variable, or the sum of two.

[/ QUOTE ]
Solution to Part 3 in white:
<font color="white">
The method I used for Part 2 generalizes well. Let a(x) be the probability density function for the weight of a summand. We don't require that the weights be bounded, but they have to be positive, so a(x)=0 for x&lt;0. We'll also use that the weight is continuous, although that isn't really required. Let f(x) for the expected index of the partial sum greater than x, and f(x) =0 for x&lt;0. As before, f satisfies an integral equation,

f(x)= 1 + Integral from t=0 to t=x of f(t) a(x-t) dt.
Equivalently, we can let the lower value be -oo, as f is 0 on (-oo,0).

As before, we'll get rid of that constant term by subtracting off a linear factor. To do this, we need the weight to have an expected value, w. We'll also want the variance to exist. Define g(x) = f(x) - x/w. Note that when x&lt;0, g(x) is not 0, but is -x/w instead. Then g satisfies an integral equation

g(x) = Integral from t=-oo to t=x g(t) a(x-t) dt.

We'd like to find a conserved quantity

H(x) = Integral t=-oo to t=x of g(t) h(x-t) dt.

We'll choose h so this is constant. Because of a different choice of variables, we didn't need the integration by parts (yet), but we get a more complicated application of Leibniz's rule since the upper limit of integration is not constant.

H'(x) = g(x)h(0) + Integral from t=-oo to t=x of g(t) h'(x-t)dt

Let h'(x) be c * a(x), so that this last integral resembles the integral equation for g(x).

H'(x) = g(x) h(0) + Integral from t=-oo to t=x of g(t) c a(x-t) dt
H'(x) = g(x) h(0) + g(x) c
H'(x) = g(x) (h(0) + c)

So, setting c=-h(0), H becomes constant.

We can scale h(0) arbitrarily, so let h(0)=1. Then
h(x) = 1 - Probability(weight &lt; x)
h(x) = Probabability (weight &gt; x)

Let the asymptotic value of g be v.

limit as x-&gt;oo H(x)
= limit as x-&gt;oo of Integral from t=-oo to t=x of g(x) h(x-t) dt
= limit as x-&gt;oo of Integral from t=-oo to t=x of v h(x-t)dt
= v * Integral from y=0 to y=oo of h(y) dy
= v * (-1) Integral from y=0 to y=oo of y h'(y) dy (by parts)
= v * Integral from y=0 to y=oo of y a(y) dy
= v * w

H(0)
= Integral from t=-oo to t=0 of g(t)h(-t)dt
= Integral from t=-oo to t=0 of -t/w h(-t) dt
= Integral from y=oo to y=0 of y/w h(y) (-1)dy
= Integral from y=0 to y=oo of y/w h(y) dy
= 1/w Integral from y=0 to y=oo of y h(y) dy
= 1/w (-1) Integral from y=0 to y=oo of y^2/2 h'(y) dy (by parts)
= 1/(2w) Integral from y=0 to y=oo of y^2 a(y) dy
= 1/(2w) * second moment of weight distribution

So, the asymptotic value v satisfies v * w = 2nd moment/(2w), or v= 2nd moment / (2 * 1st moment^2).

f(x) is asymptotic to x/(1st moment) + 2nd moment/(2 * 1st moment^2).

As a check, the nth moment for a random variable uniformly distributed on [0,1] is 1/n, so we get f(x) ~ x/(1/2) + 1/3 /(2 * 1/4) = 2x + 2/3.

How about an exponential distribution with mean 1? The 1st moment is 1, and the second moment is 2 (and variance is 2-1=1). f(x) ~ x + 2/2 = x+1. In fact, f(x) isn't just asymptotic to x+1, f(x)=x+1. The count of exponential distributions adding up to x is 1 more than a random variable with a Poisson distribution with mean x. So the expected value is x+1.
</font>