Expected Count in the 'Sum Over One' Game

Understanding - summation until one

A standard game would unfold like this:

The number of variables, N, takes positive integer values greater than or equal to 0.

Most of the time, when faced with the duty of computing the expected value of N, we would find the probability that N equals a particular integer k. Unfortunately, in our case, this is hardly a straightforward task, and I wholeheartedly commend you if you try and do it.

Since it looks like computing the individual probabilities is rather arduous, how can we proceed from here?

Solution

Let’s start by writing the formula for the expectation of a discrete random variable:

$\mathbb{E} = \displaystyle\sum_{i=1}^{\infty} i \cdot \mathbb{P} (N=i)$

$= \mathbb{P}(N=1) + \mathbb{P}(N=2) + \mathbb{P}(N=2) + \mathbb{P}(N=3) + \mathbb{P}(N=3) + \mathbb{P}(N=3) + \dots$

$= 1 + \mathbb{P}(N > 1) + \mathbb{P}(N > 2) + \dots$ Splitting $i \cdot \mathbb{P}(N=i)$ into a sum of $\mathbb{P}(N=i)$ counted $i$ times and aligning the values, we can rewrite the expectation.

The preceding sums, excluding the first being equal to 1, are respectively equal to $\mathbb{P}(N>k)$ for each $k \geq 1$. It is known that $\mathbb{P}(N > k) = \frac{1}{k!}$, so: $\mathbb{E}(N) = 1 + \displaystyle\sum_{k=1}^{\infty} \frac{1}{k!} = \displaystyle\sum_{k=0}^{\infty} \frac{1}{k!} = e$

Simulations

import random

def sim_game():
    s = 0
    count_rounds = 0 
    
    while s<1:
        s += random.uniform(0,1)
        count_rounds += 1
    
    return count_rounds

counts = 

print(f"Avg rounds: {np.mean(counts)}")