Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

1 Answer

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|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
add comment

Your Answer

 
discard

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.