# Roll an n-sided die, your result is m. Roll an m-sided die. Continue until m = 1. What is the expected number of rolls? [closed]

Roll an n-sided die, your result is m. Roll an m-sided die. Continue until m = 1. What is the expected number of rolls? This comes from playing around with a random number generator.

Example: n = 100

• Roll 1 (100-sided): 67
• Roll 2 (67-sided): 14
• Roll 3 (14-sided): 2
• Roll 4 (2-sided): 2
• Roll 5 (2-sided): 1
• What have you tried? There is a natural recursion here, which ought to make it easy to compute many small values. That's a good way to search for patterns.
– lulu
Commented Sep 20, 2021 at 16:57
• Right. Let $X_n$ be the random variable equal to the number of rolls starting with an $n$-sided die. There is a recursion for $E(X_n)$ in terms of $E(X_m)$ for $2\leq m<n.$ Commented Sep 20, 2021 at 17:04
• It's been a while since I've done this sort of thing. I got to $E(X_{n}) = \frac{1}{n}\cdot1 + \frac{n-1}{n}\cdot (1 + E(X_{m}))$, but I'm not sure where to go from there. And I don't think that's quite right anyway, the second term should probably be something along the lines of a sum of $\frac{1}{n}\cdot E(X_{m})$ from 2 to n. Commented Sep 20, 2021 at 17:28
• @lulu Since this problem does not seem to be easy at all at first glance, do you also have a tip for the following problem I tried to solve since years ? $37$ players play roulette, every player plays another of the $37$ numbers $0-36$ , at each coup 1 dollar. What is the expected number of coups after which all players have a negative score ? Can we apply recursive formulas here as well ? Commented Sep 20, 2021 at 18:08
• @Peter To be clear: you are thinking of a European style wheel, with a single $0$, and not an American style wheel with $0$ and $00$? And, what is the payout? Usually, on the European wheel, a bet on a single number has a $36:1$ payout (making the expectation negative). Is that what you want here?
– lulu
Commented Sep 20, 2021 at 18:16

$$E(1) = 0.$$

$$E(2) = (1/2)(1) + (1/2)[1 + E(2)] \implies E(2) = (2).$$

$$E(3) = (1/3) + (1/3)[1 + E(2)] + (1/3) [1 + E(3)] \implies$$

$$(2/3)E(3) = (1/3)(3) + (1/3)E(2) = 1 + (2/3) = (5/3) \implies$$

$$E(3) = (5/2).$$

In general, working recursively, you have that

$$E(n) = (1/n)\{1 + [1 + E(2)] + [1 + E(3)] + \cdots + [1 + E(n)]\}.$$

This simplifies to

$$[(n-1)/n]E(n) = 1 + (1/n)[E(2) + E(3) + \cdots E(n-1)].$$

This simplifies to

$$(n-1)E(n) = n + E(2) + E(3) + \cdots + E(n-1).$$

• This is useful, so that could alternatively be written as: $E(n) = \frac{1}{n-1}\cdot(n + \sum_{m=2}^{n-1} E(m))$, where $E(2) = 2$, is that right? How can a recurrence relation of that type be solved? Commented Sep 20, 2021 at 19:09
• @nilypp To the best of my knowledge, it can not be solved, anymore than evaluating Bernoulli Numbers can be solved. Commented Sep 20, 2021 at 19:13

The solution of the recurrence by @user2661923 is given by

$$E[n] = 1+ H_{n-1}$$

where $$H_n = \sum_{k=1}^n \frac{1}{k}$$ are the harmonic numbers.

This is a consequence of the identity: $$n H_n = n + H_1 + H_2 + \cdots H_{n-1}$$