How can I solve the expected number of frog jumps problem?

Question

A frog sits on the real number line at 0. It makes repeated jumps of random distance forward. For every jump, the frog advances by a random amount, drawn (independently) from the uniform distribution over $U([0, 1])$. The frog stops once it has reached or surpassed 1.

How many jumps does the frog make on average? What’s the standard deviation?

Here is my answer:

Let $N$ be a random variable with possible values 2, 3, 4, ... which represents the number of jumps the frog makes immediately after it has reached or surpassed 1. We will neglect the possibility of only one jump being required.

Let $X_1$, $X_2$, ... $X_n$ be a set of random variates taken from $U([0,1])$.

Let $$S_n = \sum_{i=1}^n X_i.$$

For $n\ge2$, the probability that $N=n$ is given by $$ \begin{aligned} P(N=n) &= P[(S_n \ge 1) \cap (S_{n-1}<1)] \\ &= P(S_n \ge 1)P(S_{n-1}<1). \end{aligned} $$ From the CDF of the Irwin-Hall distribution we know that $$P(S_n\le x)=\sum_{k=0}^n\frac{(-1)^k}{n!(n-k)!}(x-k)^n_+.$$ Hence, $$P(S_n\le 1)=\frac{1}{n!}.$$ Similarly, $$P(S_{n-1}\le 1)=\frac{1}{(n-1)!},$$ $$P(S_n > 1)=1 - \frac{1}{n!},$$ $$\implies P(N=n)=\frac{1}{(n-1)!} - \frac{1}{n!(n-1)!}.$$

Hence the expected value of $N$ (i.e. the average number of jumps) is given by (see WolframAlpha), $$\begin{aligned} E(N)&=\sum_{n=2}^\infty nP(N=n) \\ &=\sum_{n=2}^\infty \frac{n}{(n-1)!}\left(1-\frac{1}{n!}\right) \\ &= 2e - I_0(2) \\ &\approx 3.1570. \end{aligned}$$

Let $\mu = E(N)$. Now we need to calculate, $$E[(N-\mu)^2] = E(N^2) - \mu^2.$$ The first term is given by (see WolframAlpha): $$\begin{aligned} E(N^2) &= \sum_{n=2}^\infty n^2P(N^2=n^2) \\ &= \sum_{n=2}^\infty n^2P(N=n) \\\ &=\sum_{n=2}^\infty \frac{n^2}{(n-1)!}\left(1-\frac{1}{n!}\right) \\ &=5e-I_0(2) - I_1(2)\\ &\approx 9.7212. \end{aligned}$$ Hence the standard deviation, $\sigma$ is approximately (see WolframAlpha), $$ \begin{aligned} \sigma \approx 0.2185. \end{aligned} $$

However, when I check these results using the code below, it seems that $$\mu\approx 2.7222 \approx e?,$$ $$\sigma \approx 0.8752.$$ Can you see where I went wrong?

import numpy as np

num_trials = int(1e5)
N = np.zeros(num_trials)
for n in range(num_trials):
    X = 0
    while X < 1:
        N[n] += 1
        X += np.random.uniform()

print(np.mean(N))
print(np.std(N))

Answer 1

As noted in the comments, you have incorrectly assumed the events $S_n\geq 1$ and $S_{n-1}<1$ are independent.

Note that the events $N=n$ and $S_n<1$ are mutually exclusive and collectively exhaust the event $S_{n-1}\leq 1$. Also note that the Irwin-Hall distribution tells us $P(S_n\leq 1)=1/n!$ Thus,

$$\begin{align} P(N=n)&=P(S_{n-1}\leq 1)-P(S_n<1)\\ &={1 \over (n-1) !}-{1 \over n!}\\ &= {n-1 \over n!} \end{align}.$$

You can check that this should give you $E[N]=e,\text{Var}(N)=3e-e^2.$

Answer 2

You can write $$\mathbb{E}N = \sum_{n=0}^{\infty}nP(N=n) = \sum_{n=0}^{\infty}P(N>n)$$ $$=\sum_{n=0}^{\infty}P(S_n<1) $$ $$=\sum_{n=0}^{\infty}\frac{1}{n!} $$

Edit regarding the first line: The intuitive way is to think about how many times it gets counted if $N=3$, say. In the RHS sum this gets counted for $3$ once, at $n=3$. In the LHS it gets counted for $1$ three times, at $n=0,1,2$.

Answer 3

Thank you for the responses. They were very helpful. Here is my answer that I find more intuitive.

$$\begin{aligned} P(N\ge n+1) &= P(S_n < 1) \\ &= P(S_n \le 1) \text{ (since the probability $S_{n+1}=1$ is effectively 0.)} \\ &= \frac{1}{n!} \end{aligned}$$ Since $P(N\ge n)$ is a decreasing function of $n$, we know that $$\begin{aligned} P(N=n)&=P(N\ge n)-P(N\ge n+1) \\ &= \frac{1}{(n-1)!}-\frac{1}{n!} \\ &= \frac{n-1}{n!}. \end{aligned}$$ Hence, $$\begin{aligned} E(N)&=\sum_{n=2}^\infty \frac{1}{(n-2)!},\\ &=\sum_{n=0}^\infty \frac{1}{n!} \\ &=e. \end{aligned}$$ $$\begin{aligned} E(N^2)&=\sum_{n=2}^\infty \frac{n}{(n-2)!},\\ &=\sum_{n=0}^\infty \frac{n}{n!}+ \sum_{n=0}^\infty\frac{2}{n!}\\ &=\sum_{n=1}^\infty \frac{1}{(n-1)!}+ 2e\\ &=3e. \end{aligned}$$ Finally, $$\mu=e=2.71828...$$ $$\sigma=\sqrt{3e-e^2}=0.87509...\,.$$ Which agrees with Golden_Ratio's answer.