Expected number of turns (2)

Kent Merryfield

Let $y$ be an arbitrary positive number. Define $g(y)$ to be the expected number of independent uniform $[0,1]$ random variables needed for the the sum to first exceed $y.$

Compute $g(y)$ and discuss the asymptotic behavior of $g(y)$ as $y\to\infty.$

**Posted:** Mon Dec 13, 2004 9:24 am

Kent Merryfield

A bit of intuition about that asymptotic behavior: The expected value of each of our random variables is $\frac12.$ In order for the sum to exceed $y$ , perhaps the sum of the expectations should be about $y$ . In other words, don't be too surprised if $g(y)$ works out to something like $2y$ for large $y.$

Of course, I'm looking for something more detailed than that.

**Posted:** Mon Dec 13, 2004 9:28 am

grobber

I think it's been proven in the previous thread that for $y$ between $0$ and $1$ , $g(y)=e^y$ . Another way to prove that:

The probability that the number of turns is $\le n$ is $1-\frac {y^n}{n!}$ , because $\frac{y^n}{n!}$ is the volume of the small simplex in the corner of the $n$ -hypercube, having mutual orthogonal sides of length $y$ (this is where we use $y\le 1$ ; if $y>1$ , the shape in the corner is no longer a simplex) along the sides of the cube. The probability that the number of turns is $n$ is thus $\frac{y^{n-1}}{(n-1)!}-\frac{y^n}{n!}$ , and from here it's really easy: we add up expressions of the form $n(\frac{y^{n-1}}{(n-1)!}-\frac{y^n}{n!})$ and use the series expansion of $e^y$ .

I don't know what the right way to approach the general case is though.

**Posted:** Mon Dec 13, 2004 10:10 am

Kent Merryfield

Hint: try conditioning on the value of the first term in the sequence of random variables.

(Yes, $g(y)=e^y$ for $0<y\le1.$ If convenient, you may also let $g(y)=0$ for $y<0.)$

**Posted:** Wed Dec 15, 2004 9:33 am

jmerry

Another variation on this problem- what if we're adding independent exponential random variables of mean $k$ ? The answer is particularly nice in that case.

The asymptotic behavior is accessible for almost any positive continuous random variable, in exactly the expected form (x/mean)+(constant)+(goes to 0)

**Posted:** Thu Dec 16, 2004 1:07 am

jhaussmann5 · Riemann Hypothesis Offline Joined: 29 Dec 2003 Posts: 343

**Posted:** Fri Dec 17, 2004 9:50 pm

Kent Merryfield

**Posted:** Sat Dec 18, 2004 7:02 am

Kent Merryfield

I'll go ahead an post the first part of my solution, although I will leave part of it for a few days to see if anyone else has any ideas.

We have a sequence of independent identically distributed nonnegative continuous random variables. The density of this distribution is $f(x)$ , where $f$ is supported on $[0,\infty).$ Let $g(y)$ be the expected number of these random variables required for the sum to exceed $y.$ As a notational convenience, define $g(y)=0$ for $y<0.$

Condition on the first random variable. It has the value $x,$ which leaves the remaining target as $y-x.$ Thus the expected number of remaining terms will be $g(y-x),$ making the expected overall number of terns given that the first terms was $x$ equal to $1+g(y-x).$ (Note that this holds even if $x>y.$ ) But the overall expected value is the expectation of the conditional expectations. Hence we have the following integral equation for $g$ :

$g(y)=1+\int_0^yf(x)g(y-x)dx.$

We recognize the integral as a convolution, and abbreviate this equation as $g=1+f*g.$

**Posted:** Sun Dec 19, 2004 9:19 am

Kent Merryfield

Since we have a linear convolution equation, a transform method looks attractive. With everything happening on $[0,\infty)$ , I turn to the Laplace tranform.

Let $F(s)=\int_0^{\infty}f(x)e^{-sx}dx$ and $G(s)=\int_0^{\infty}g(y)e^{-sy}dy.$ Note that $F(s)$ is, except for a sign change, the "moment generating function" for the underlying random variable.

Apply the Laplace tranform to our integral equation to get

$G(s)=\frac1s+F(s)G(s)$

We rearrange this to $G(s)=\frac1{s(1-F(s))}.$

Try this for jmerry's example: the exponential distribution of mean $k$ . Then $f(x)=\frac1ke^{-x/k}$ and $F(s)=\frac1{1+ks}.$ Then our equation leads to $G(s)=\frac{1+ks}{ks^2}=\frac1k\cdot\frac1{s^2}+\frac1s.$ From that we derive that $g(y)=\frac yk+1.$

Now back to the original case, in which the random variable was uniform $(0,1)$ . In that case, $F(s)=\frac{1-e^{-s}}s.$ From this we derive $G(s)=\frac1{s-1+e^{-s}}.$

To get anywhere with this we expand this as a geometric series:

$G(s)=\frac1{s-1}-\frac{e^{-s}}{(s-1)^2}+ \frac{e^{-2s}}{(s-1)^3}+\cdots$

Let $H(y)$ be the Heaviside unit step function - that is, $H(y)=1$ for $y\ge0$ and $H(y)=0$ for $y<0.$ The inverse Laplace transform of the series above gives us that

$g(y)=\sum_{k=0}^{\infty}H(y-k)\frac{(-1)^k(y-k)^k}{k!}e^{y-k}.$

This can be restated as

$g(y)=\sum_{k=0}^{\lfloor y\rfloor}\frac{(-1)^k(y-k)^k}{k!}e^{y-k}.$

The function is smooth except at the integers. It is continuous at 1, has a continuous first derivative at 2, a continuous second derivative at 3, and so on.

Still to be addressed: the asymptotic behavior as $y\to\infty.$ I'll wait a few days to give others a chance to work on that.

**Posted:** Sun Dec 19, 2004 9:37 am

Kent Merryfield

The time has come to finish off this topic.

For the original case, the function $g(y)$ is asymptotically equal to $2y+\frac23.$ That is, $g(y)=2y+\frac23+q(y)$ where $\lim_{y\to\infty}q(y)=0.$

For the same problem in which the uniform (0,1) distribution is replaced by a "nice enough" continuous positive random variable with mean $\mu$ and variance $\sigma^2$ , then the $g(y)$ for that case is asymptotically equal to $\frac{y}{\mu}+\frac12+\frac{\sigma^2}{2\mu^2}.$

I'm not sure what "nice enough" means. Bounded with square integrable density would be sufficient but is certainly stronger than it needs to be. But some condition is needed, because discrete distributions would follow a somewhat different (but related) pattern.

We will do this by Laplace transform methods. For the original case, from above, we see that $g(y)$ has Laplace transform $G(s)=\frac1{s-1+e^{-s}}.$ Expanding this as a Laurent series about 0, we find that $G(s)=\frac2{s^2}+\frac23\cdot\frac1s+Q(s)$ where $Q(s)$ has a removable singularity at 0 and behaves like $\frac1s$ at $\infty.$ The inverse transform of this is $g(y)=2y+\frac23+q(y).$ The inverse Laplace transform procedure gives us that

$q(y)=\frac1{2\pi}\int_{-\infty}^{\infty}Q(it)e^{ity}dt.$

Since $Q(it)\in L^2(\mathbb{R})$ we can say that $q(y)\in L^2.$ Furthermore, since $Q$ is smooth, $q$ behaves itself at infinity. From this, I argue that $\lim_{y\to\infty}q(y)=0.$

For the more general case, the random variable has density $f(x)$ with Laplace transform $F(s)=\int_0^{\infty}f(x)e^{-sx}dx = 1 - \mu s + \frac{\mu^2+\sigma^2}2s^2 + O(s^3).$ The function $g$ has Laplace transform

$G(s)=\frac1{s(1-F(s))}= \frac1{\mu s^2-\frac{\mu^2+\sigma^2}2s^3+\cdots} =$
$\frac1{\mu}\cdot\frac1{s^2}+\frac{\mu^2+\sigma^2}{2\mu^2}\cdot \frac1s +Q(s)$

where once again, $Q(s)$ has a removable singularity at zero. If we assume nice enough behavior for $Q$ , the asymptotic result follows.

The same result can also be obtained by considering the "excess" - that is, by examing the distribution of the amount by which the running sum exceeds $y$ when we reach the stopping point.

**Posted:** Mon Dec 27, 2004 2:10 pm