Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
See Byron's answer there. – Did Jun 21 '13 at 17:39
Also answered on MathOverflow. – 40 votes Jul 19 '13 at 4:23
up vote 3 down vote accepted

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$.

share|cite|improve this answer
Thankyou, it's a little while since I did Laplace transforms, but I'll work through it. – Michael Jun 21 '13 at 18:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.