# Average number of $U[0,1]$ random numbers to reach $x$

Let $P(x)$ be a random process where you keep selecting random numbers, uniformly distributed between 0 and 1, until the sum reaches $x$.

From memory, the expected value of the number of terms needed by $P(x)$ is $e^x Q(x)$, where $Q(x)$ is a piecewise polynomial whose degree increases at each integer value of $x$. If I remember, it was
$$Q(x) = \sum_{k=0}^{\lfloor x\rfloor} (-1)^k\frac{(x-k)^k}{(k+1)!}$$

My question is: This formula numerically gives $(2/3)+2x$ plus exponentially decaying but oscillating terms. How do you go from $e^x Q(x)$ to $2/3 + 2x$ plus exponentially decaying terms?

-
See Byron's answer there. – Did Jun 21 '13 at 17:39
– 40 votes Jul 19 '13 at 4:23

Short version: do not use the formula for $Q(x)$.
Long version: let $U$ denote the first random number, then, conditionally on $U$, the mean number of draws needed to overcome $x$ is $1$ if $x\leqslant U$ and distributed like $1+P(x-U)$ otherwise. Thus, $$P(x)=1+E(P((x-U)^+))=1+\int_{(x-1)^+}^xP(t)\mathrm dt.$$ The Laplace transform is $$L(s)=\int_0^{+\infty}\mathrm e^{-sx}P(x)\mathrm dx.$$ Massaging the identity involving $P$ yields $$L(s)=\frac1{s-1+\mathrm e^{-s}}=\frac2{s^2}+\frac2{3s}+O(1),$$ when $s\to0$. Since $P$ is monotonous, the $\frac2{s^2}$ term implies that $P(x)=2x+o(x)$, and a little more work is needed to show that the $\frac2{3s}$ term implies that $P(x)-2x\to\frac23$.