# Number of uniform rvs needed to cross a threshold

Let $N(x)$ be the number of uniform random variables (distributed in $[0,1]$) that one needs to add for the sum to cross $x$ ($x > 0$). The expected value of $N(x)$ can be calculated and it is a very cool result that $E(N(1)) = e$. The expression for general $x$ is

$E(N(x)) = \sum_{k=0}^{[x]} (-1)^k \frac{(x-k)^k}{k!} e^{x-k}$

where $[x]$ is the largest integer less than $x$. When $x$ is large, this function $E(N(x))$ grows linearly (as one would expect). Computer simulations suggest that $E(N(x)) \approx 2x + 2/3$. My question is as follows: is it possible to guess this form for $E(N(x))$ without actually computing it? The $2x$ part is intuitive but is there a good intuition for why there is an additive constant and why that value is $2/3$?

My motivation is as follows: When I computed $E(N(x))$ using the formula above for large values of $x$, I came across this asymptotic and found it surprising that a polynomial equation in powers of $e$ gives values that are very close to a rational number. I am very interested in knowing the reason (if any) behind it. Thanks in advance for any help.

-
I think the intuition for the existence of the additive constant is clear: if you agree that the 2x part is intuitive you should agree that E(N(x+1)) is approximately E(N(x)) + 2, n'est-ce pas? This gives E(N(x)) \approx 2x + (e - 2) already. –  Qiaochu Yuan Jan 3 '10 at 7:20
I was thinking of E(N(1))=e as a transient that dies away as x goes to infinity and the steady state behavior being just E(N(x)) = 2x. But in light of Leonid's answer below, I think I understand your point. Thanks. –  Dinesh Jan 3 '10 at 7:39

Another way to put it: the expected value of the sum right after it crosses x is x+1/3. If you simply conditioned the sum to be in (x,x+1) then the expectation would be about x+1/2, with the sum almost uniformly distributed. But you also condition on the overshoot being less than the last jump. The expectation of the smaller of two uniform [0,1] iids is 1/3.

-
Beautifully explained. Thanks. –  Dinesh Jan 3 '10 at 7:37

This problem has delighted me since I first encountered it before college. I wrote up a generalization for a less mathematical audience in a poker forum.

One way to look at the original is that if f(x) = E(N(X)), then $f(x) = 1 + \int_{x-1}^x f(t) dt$, satisfying the initial condition that $f(x) = 0$ on $(-1,0)$. $f$ is 1 more than the average of $f$ on the previous interval.

We can get rid of the constant by using $g(x) = f(x) - 2x$ which satisfies $g(x) = \int_{x-1}^x g(t) dt$. $g$ is equal to its average on the previous interval. Now the initial condition becomes nontrivial: $g(x) = -2x$ on $(-1,0)$, and it is from this $-2x$ that the asymptotic value of $2/3$ comes.

$g$ is asymptotically constant, and we can guess from geometry and verify that the weighted average $\int_0^1 2t~g(x+t)dt$ is independent of $x$, hence equal to the asymptotic value of $g$. The value at $x=-1$ is $\int_0^1 4t(1-t)dt = \frac23$, so that is the asymptotic value of $g$.

The same technique works for more general continuous distributions supported on $\mathbb R^+$ than the uniform distribution, and the answer turns out to be remarkably simple. Let's find an analogous conserved quantity.

Let $\alpha$ be the density function. Let the $n$th moment be $\alpha_n$. We'll want $\alpha_2$ to exist.

Let $f(x)$ be the average index of the first partial sum which is at least $x$ of IID random variables with density $\alpha$. $f(x) = 1 + \int_{-\infty}^x f(t) \alpha(x-t) dt$, and $f(x) = 0$ for $x\lt0$. (We could let the lower limit be 0, too.)

Let $g(x) = f(x) - x/\alpha_1$. Then $g(x) = \int_{-\infty}^xg(t)\alpha(x-t)dt$, with $g(x) = -x/\alpha_1$ on $\mathbb R^-$.

We'll choose $h$ so that $H(x) = \int_{-\infty}^x g(t) h(x-t) dt$ is constant.

$0 = H'(x) = g(x)h(0) + \int_{\infty}^x g(t) h'(x-t)dt.$

This integral looks like the integral equation for $g$ if we choose $h'(x) = c\alpha(x)$. $c=-1$ satisfies the equation. So, if $h(x) = \int_x^\infty \alpha(t)dt$ then $H(x)$ is constant.

Let the asymptotic value of $g$ be $v$. Then the value of $H(x)$ is both $H(\infty) = v~\alpha_1$ and

$H(0) = \int_{-\infty}^0 g(t) h(0-t)dt$

$H(0) = 1/\alpha_1 \int_0^\infty y~h(y) dy$

$H(0) = 1/(2\alpha_1) \int_0^\infty y^2 ~\alpha(y)dy~~$ (by parts)

$H(0) = \alpha_2 / (2 \alpha_1)$

$v~ \alpha_1 = \alpha_2 / (2 \alpha_1)$

$v = \alpha_2 / (2 \alpha_1^2)$.

So, $f(x)$ is asymptotic to $x/\alpha_1 + \alpha_2/(2 \alpha_1^2)$.

For the original uniform distribution on [0,1], $\alpha_1 = \frac12$ and $\alpha_2 = \frac13$, so $f(x) = 2x + \frac23 + o(1)$.

As a check, an exponential distribution with mean 1 has second moment 2, and we get that $f(x)$ is asymptotic to $x+1$. In fact, in that case, $f(x) = x+1$ on $\mathbb R^+$. If you have memoryless light bulbs with average life 1, then at time $x$, an average of $x$ bulbs have burned out, and you are on the $x+1$st bulb.

-
Thanks Douglas. I was curious about what happens when the uniform rvs are replaced by other rvs. Nice analysis. On an unrelated note, most of the Latex didn't parse correctly for me while some formulae did parse correctly. I couldn't edit the response either (not enough reps?). Anyone else having the same trouble? –  Dinesh Jan 26 '10 at 0:11
Occasionally the Latex doesn't parse for me, either, but I see everything here. This write-up is essentially the same as the one in the poker forum, so if it's unreadable here you can read that one. Select the white text to make it visible, or copy it and paste it elsewhere. –  Douglas Zare Jan 26 '10 at 0:23