What is the expected number of rolls made if a fair six-sided die is rolled until a number less than one of the previous rolls is rolled?

Question

I recently came across this problem in probability

Roll a fair six-sided die until you roll a number that is less than one of your previous rolls. To three decimal places, what is the expected value of the number of rolls made?

This is all what the question has to offer, any ideas?

Answer 1

Denote by $e_r$ the expected number of further rolls, given that the highest roll so far is $r$, and we are not yet done. Then $$e_0=1+{1\over6}\sum_{k=1}^6 e_k\ ,\quad e_r=1+{1\over6}\sum_{k=r}^6e_k\quad(1\leq r\leq 6)\ .$$ Solving this system (with Mathematica) leads to $$e_0={46\,656\over15\,625}=\left({6\over5}\right)^6=2.9856\ .$$ I hope that someone finds a simple explanation for this result. In fact one has $$e_r=(6/5)^{7-r}\qquad(1\leq r\leq 6)\ .$$

Answer 2

Let $X$ be the number of the first roll where the value of the die is less than that on one of the previous rolls. We would like to find $P(X > n)$, which is the probability that a sequence of $n$ rolls is non-decreasing, for $n \ge 0$. There are $6^n$ possible sequences of $n$ rolls, all of which we assume are equally likely. The number of these which are non-decreasing is $\binom{6+n-1}{n}$, the number of multisets of size $n$ taken from $\{1,2,3,4,5,6\}$. Then $$P(X>n) = \binom{6+n-1}{n} \left( \frac{1}{6} \right)^n$$ So $$E(X) = \sum_{n \ge 0} P(X>n) = \sum_{n \ge 0} \binom{6+n-1}{n} \left( \frac{1}{6} \right)^n = \left( 1 - \frac{1}{6} \right)^{-6} = \left( \frac{6}{5} \right)^6$$ where we have applied the binomial theorem for a negative power.

Answer 3

It might be better to have a look at the edit at first.

---

Let $\nu_{k}$ denote the expectation of the number of rolls still needed after the first roll under the extra condition that the first roll provides number $k\in\left\{ 1,2,3,4,5,6\right\} $.

If $\mu$ denotes the expectation then: $$\mu=1+\frac{1}{6}\sum_{k=1}^{6}\nu_{k}\tag1$$

For every $k\in\left\{ 1,2,3,4,5,6\right\} $ we have: $$\nu_{k}=\frac{k-1}{6}\cdot1+\frac{1}{6}\sum_{i=k}^{6}\left(1+\nu_{i}\right)=1+\frac{1}{6}\sum_{i=k}^{6}\nu_{i}$$Or fading away the fractions:$$6\nu_{k}=6+\sum_{i=k}^{6}\nu_{i}$$

These equations enable us to find $\nu_1,\dots,\nu_6$ and eventually $\mu$.

We can start at the bottom with $6\nu_6=6+\nu_6$ leading to $\nu_6=\frac{6}5$.

We can find that $5\nu_{k-1}=6\nu_k$ for $k=6,5,4,3,2$ by means of:

$$6\nu_{k-1}=6+\sum_{i=k-1}^{6}\nu_{i}\implies5\nu_{k-1}=6+\sum_{i=k}^{6}\nu_{i}=6\nu_{k}$$

These facts together lead to: $$\nu_k=\left(\frac65\right)^{7-k}\tag2$$

so that: $$\mu=1+\frac16\sum_{k=1}^6\left(\frac65\right)^{7-k}=1+\frac16\sum_{k=1}^6\left(\frac65\right)^{k}=\left(\frac65\right)^6\approx2.985984$$

Btw, this nice outcome makes me suspect that there is a more elegant route to the result.

---

Edit:

The answer can be simplified.

This because $(1)$ can be interchanged by the more simple:$$\mu=\nu_1\tag3$$ Then we are ready as soon as we have reached $(2)$:$$\mu=\nu_1=\left(\frac65\right)^{7-1}=\left(\frac65\right)^{6}$$ The (annoying) summation can be left out.

Answer 4

My approach would be to divide the problem into $N_k$, which is the expected number of rolls until you roll a number that is less than one of your previos rolls or $7-k$.

However my solution seem to disagree with the other answers. I suspect I've done some fundamental error somewhere, but I cannot see it. I would appreciate if somebody can point out one/the error (rather than just downvoting which is so contraproductive since I plan to delete this answer when I find out the error)

We start with $N_1$. With probability of $1/6$ we will roll first a $6$ and then are expected to roll $N_1$ more rolls. So

$$N_1 = (1/6)(1+N_1)$$ $$5N_1/6 = 1/6$$ $$N_1 = 1/5$$ Then you continue with $N_2$. Either you throw a $5$ with probability of $1/6$ and then the expected $N_2$ more throws or you throw a $6$ and then expected $N_2$ more throws. So

$$N_2 = (1/6)(1+N_1) + (1/6)(1+N_2) = 1/5 + 1/6 + N_2/6$$ $$5N_2/6 = 11/30$$ $$N_2 = 11/25$$

etc, until you calculated $N_6$. With little effort we see that the recursion formula is $N_k = (k + \sum_{j<k}N_j)/5$.

You can also consider the partial sums $S_k = \sum_1^k N_j$ and reformulate it as $S_k - S_{k-1} = N_k = (k + S_{k-1})/5$ or

$$S_k = (k + 6S_{k-1})/5$$

And substituting $T_k = S_k5^k$ or $S_k = T_k/5^k$ we get

$$T_k = k 5^{k-1} + 6 S_{k-1}$$

Now we start with $T_1=1$ and get

$$T_2 = 16$$ $$T_3 = 171$$ $$T_4 = 1526$$ $$T_5 = 12281$$ $$T_6 = 92436$$

Which means $S_6 = 92436/3125$ and $S_5=61405/3125$ which would make $N_6 = S_6 - S_5 = 31031/3125\approx 9.930$