0
$\begingroup$

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
$\endgroup$
10
  • 4
    $\begingroup$ 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. $\endgroup$
    – lulu
    Commented Sep 20, 2021 at 16:57
  • $\begingroup$ 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.$ $\endgroup$ Commented Sep 20, 2021 at 17:04
  • $\begingroup$ 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. $\endgroup$
    – nilypp
    Commented Sep 20, 2021 at 17:28
  • $\begingroup$ @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 ? $\endgroup$
    – Peter
    Commented Sep 20, 2021 at 18:08
  • $\begingroup$ @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? $\endgroup$
    – lulu
    Commented Sep 20, 2021 at 18:16

2 Answers 2

2
$\begingroup$

$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).$

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – nilypp
    Commented Sep 20, 2021 at 19:09
  • $\begingroup$ @nilypp To the best of my knowledge, it can not be solved, anymore than evaluating Bernoulli Numbers can be solved. $\endgroup$ Commented Sep 20, 2021 at 19:13
1
$\begingroup$

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}$

See also https://oeis.org/A000774 (fourth comment).

$\endgroup$
1
  • 1
    $\begingroup$ Excellent! This explains why I was finding by simulation that the result tended to be close to ln(n) + 1.57, which I now see to be the Euler–Mascheroni constant + 1. $\endgroup$
    – nilypp
    Commented Sep 20, 2021 at 20:02

Not the answer you're looking for? Browse other questions tagged .