I was told this problem a while ago, and recently someone explained the answer to me, which I didn't understand; could someone please explain in layman's terms (ish)?
You have a die with $n$ sides. Each side is numbered – uniquely – from $1$ to $n$, and has an equal probability of landing on top as the other sides (i.e. a fair die). For large $n$ (I was given it with $n = 1,000,000$), on average how many rolls does it take to achieve a cumulative score of $n$ (or greater)? That is, when you roll it, you add the result to your total score, then keep rolling and adding, and you stop when your score exceeds or is equal to $n$.
The cool thing about this problem: apparently, the answer is $e$. I would like to know exactly how this is derived.
Best Answer
If we divide every roll by $n$, rolling the die and dividing by $n$ approximates the uniform distribution on $[0,1]$ for arbitrarily large $n$. We then are looking for the expected number of samples from a uniform distribution required to get a sum above $1$.
For any integer $k \in \mathbb{N}$, Let $X_1, \ldots , X_k, \ldots$ be the random variables in question. Then $$ \mathbb{P}[X_1 + \ldots + X_k \leq 1] = \frac{1}{k!} $$ as $\frac{1}{k!}$ is the volume of the $k$-dimensional simplex defined by $X_1 + \ldots + X_k \leq 1$. Now, let $p_k$ be the probability that it takes exactly $k$ rolls to get above $1$; this is equal to $$ p_k = \mathbb{P}[X_1 + \ldots + X_{k-1} \leq 1] - \mathbb{P}[X_1 + \ldots + X_{k} \leq 1] = \frac{1}{(k-1)!} - \frac{1}{k!},$$ as we need the first $k-1$ samples to sum below $1$, and need the first $k$ to sum above $1$. Thus, the expected number of rolls required is \begin{align} \mathbb{E}[\text{Number of Rolls Required}] &= \sum\limits_{k = 1}^\infty k\cdot p_k \\ &= \sum\limits_{k = 1}^\infty k \left( \frac{1}{(k-1)!} - \frac{1}{k!}\right) \\ &= \sum\limits_{k = 2}^\infty k \left( \frac{1}{(k-1)!} - \frac{1}{k!}\right) &\text{ as the }k=1\text{ case contributes }0 \\ &= \sum\limits_{k = 2}^\infty \frac{1}{(k - 2)!}\\ &= e. \end{align}