Sum of uniform random variables until sum is greater than one

Introduction

I saw this problem on r/probabilitytheory

If you pick a uniformly random real number on [0,1] and repeat this until the sum of numbers picked is greater than 1, you’ll on average pick $e\approx 2.718$ numbers

Posed in a way that we can actually begin to solve this.

Sample independent uniform random variables $U_1,U_2,\dots$ and let $S_n=\sum _{i=1}^n{U}_i$. Let $N$ be the first integer $n$ such that $S_n>1$. Find $E[N]$

Bonus question: What is the $E[S_n]$? Can we find its distribution?

Of course, the first step is to replicate the simple simulation.

Simulation

# Sample from independent uniform U(0,1) distributions and stop when the sum
# is greater than 1. Let N be that first sum. Then E[N] = e

sim_sum <- function(t = 1) {
  s_n <- 0
  n <- 0
  while(s_n < 1) {
    s_n <- s_n + runif(1)
    n <- n + 1
  }
  c(n = n, s_n = s_n)
}


reps <- 1e4
N_sim <- data.frame(t(replicate(reps, sim_sum())))
N_sim_table <- table(N_sim$n)
N_sim_prob <- N_sim_table / reps

K <- as.numeric(names(N_sim_table))

mean_N <- mean(N_sim$n)
plot(K, N_sim_prob, type = 'b', ylim = c(0, 1), ylab = 'P(N = n)', xlab = 'N')
abline(v = mean_N, lty = 2)
text(x = mean_N + 1, y = 0.75, sprintf('Mean(n) = %.03f', mean_N))

Proof

The idea of the proof is to directly solve:

$$E[n]=\sum _{n=1}^{\mathrm{\infty }}n\cdot P(N=n)$$

So we need to calculate, $P(N=n)$. This is the same as, $P(S_{n-1}\le 1\text{ and }{S}_n>1)$. If we calculate $P(S_n\le x)=F_{S_n}(x)$ we can complete the proof.

$P(S_n\le x)$

Using the proof from this answer on math.stackexchange,

when $x\in [0,1]$, claim is that $P(S_n\le t)=\frac{x^n}{n!}$. When $n=1$, then $P(S_1\le t)=P(U_1\le t)=t$. Assume true for $n$. Then,

$$\begin{array}{rl}P(S_{n+1}\le x)& =P(S_n+U_{n+1}\le t)\\ & ={\int }_0^{1}P(S_n+u\le t)\underset{1}{\underbrace{f(u)}}du& & S_n\text{ and }{U}_{n+1}\text{ independent}\\ & ={\int }_0^{1}P(S_n\le t-u)du\\ & ={\int }_0^t\underset{\text{Induction Hypothesis}}{\underbrace{P(S_n\le t-u)}}du& & \text{Since }P(S_n\le t-u)=0\text{ when }u\in [t,1]\\ & ={\int }_0^t\frac{(t-u{)}^n}{n!}du\\ & =\frac{1}{n!}(\frac{-1}{n+1}(t-u{)}^{n+1}{|}_{u=0}^{u=t})\\ & =\frac{t^{n+1}}{(n+1)!}\end{array}$$

PMF of $S_n$

Since $F_{S_n}(x)=\frac{x^n}{n!}$ we have $$\begin{array}{rl}{f}_{S_n}(x)& =\frac{d{F}_{S_n}}{dx}\\ & =n\frac{x^{n-1}}{n!}\end{array}$$

$P(N=n)$

$$\begin{array}{rl}P(N=n)& =P(S_{n-1}\le 1\text{ and }{S}_n>1)\\ & =P(S_n>1|S_{n-1}\le 1)P(S_{n-1}\le 1)\\ & ={\int }_0^{1}P(U_n+x>1|S_{n-1}=x\le 1)\underset{1}{\underbrace{P(s\le 1|S_{n-1}=s)}}{f}_{S_{n-1}}(x)dx\\ & ={\int }_0^{1}P(U_n+x>1)f_{S_{n-1}}(x)dx& & U_n\text{ and }{S}_{n-1}\text{ independent}\\ & ={\int }_0^1(1-F_n(1-x))f_{S_{n-1}}(x)dx\\ & ={\int }_0^{1}x(n-1)\frac{x^{n-2}}{(n-1)!}dx\\ & =\frac{n-1}{(n-1)!}{\int }_0^1{x}^{n-1}dx\\ & =\frac{n-1}{n(n-1)!}=\frac{n-1}{n!}\end{array}$$

To double check the answer we can simulate

# This is formula we computed analytically
# (K - 1) / (factorial(K))
K <- as.numeric(names(N_sim_table))
expected_probs <- (K - 1) / (factorial(K))

plot(K, N_sim_prob, type = 'b', xlab = 'n', ylab = 'Prob(N = n)', ylim = c(0, 1), yaxp = c(0, 1, 4))
lines(K, expected_probs, type = 'b', col = 'red')

E[N] = e

$$\begin{array}{rl}E[N]& =\sum _{n=2}^{\mathrm{\infty }}n\cdot P(N=n)\\ & =\sum _{n=2}^{\mathrm{\infty }}\frac{n(n-1)}{n!}\\ & =\sum _{n=2}^{\mathrm{\infty }}\frac{1}{(n-2)!}\\ & =\sum _{n=0}^{\mathrm{\infty }}\frac{1}{n!}& & \text{since }\sum _{n=0}^{\mathrm{\infty }}\frac{x^n}{n!}=e^x\\ & =e\end{array}$$