Roll a die until it lands on any number other than 4. What is the probability the result is > 4?

Question

A player is given a fair, six-sided die. To win, she must roll a number greater than 4 (i.e., a 5 or a 6). If she rolls a 4, she must roll again. What are her odds of winning?

I think the probability of winning $P(W)$, can be expressed recursively as:

$$ P(W) = P(r = 5 \cup r = 6) + P(r = 4) \cdot P(W) $$

I've approximated $P(W)$ as $0.3999$ by running 1 million trials in Java, like this:

import java.util.Random;
public class Dice {

    public static void main(String[] args) {
        int runs = 1000000000;
        int wins = 0;
        for (int i = 0; i < runs; i++) {
            wins += playGame();
        }
        System.out.println(wins / (double)runs);
    }

    static Random r = new Random();

    private static int playGame() {
        int roll;
        while ((roll = r.nextInt(6) + 1) == 4);
        return (roll == 5 || roll == 6) ? 1 : 0;
    }
}

And I see that one could expand $P(W)$ like this:

$$ P(W) = \frac{1}{3} + \frac{1}{6} \left(\frac{1}{3} + \frac{1}{6}\left(\frac{1}{3} + \frac{1}{6}\right)\right)... $$

But I don't know how to solve this type of recurrence relation without resorting to this sort of approximation. Is it possible?

Answer 1

Just solve it using algebra:

\begin{aligned} P(W) &= \tfrac 2 6 + \tfrac 1 6 \cdot P(W) \\[7pt] \tfrac 5 6 \cdot P(W) &= \tfrac 2 6 \\[7pt] P(W) &= \tfrac 2 5. \end{aligned}

Answer 2

Note: This is an answer to the initial question, rather than the recurrence.

If she rolls a 4, then it essentially doesn't count, because the next roll is independent. In other words, after rolling a 4 the situation is the same as when she started. So you can ignore the 4. Then the outcomes that could matter are 1-3 and 5-6. There are 5 distinct outcomes, 2 of which are winning. So the answer is 2/5 = 0.4 = 40%.

Answer 3

The answers by dsaxton (https://stats.stackexchange.com/a/232107/90759) and GeoMatt22 (https://stats.stackexchange.com/a/232107/90759) give the best approaches to the problem. Another is to realize that your expression

$$P(W) = \frac13+\frac16\left(\frac13+\frac16(\cdots)\right)$$

Is really a geometric progression:

$$\frac13+\frac16\frac13+\frac1{6^2}\frac13+\cdots$$

In general we have

$$\sum_{n=0}^{\infty}a_0q^n = \frac{a_0}{1-q}$$

so here we have

$$P(W) = \frac{\frac13}{1-\frac16} = \frac13:\frac56=\frac{6}{15}=\frac25.$$

Of course, the way to prove the general formula for the sum of a geometric progression, is by using an algebraic solution similarly to dsaxton.

Answer 4

All of the above answers are correct, but they don't explain why they are correct, and why you can ignore so many details and avoid having to solve a complicated recurrence relation.

The reason why the other answers are correct is the Strong Markov property, which for a discrete Markov Chain is equivalent to the regular Markov property. https://en.wikipedia.org/wiki/Markov_property#Strong_Markov_property

Basically the idea is that the random variable

$\tau:=($the number of times until the die does not land on 4 for the first time)

is a stopping time. https://en.wikipedia.org/wiki/Stopping_time A stopping time is a random variable which doesn't depend on any future information.

In order to tell whether the $n$th roll of the die is the first one which has not landed on a 4 (i.e. in order to decide whether $\tau=n$), you only need to know the value of the current roll, and of all previous rolls, but not of any future rolls -- thus $\tau$ is a stopping time, and the Strong Markov property applies.

What does the Strong Markov property say? It says that the number which the die lands on at the $\tau$th roll, as a random variable, $X_{\tau}$, is independent of the values of ALL previous rolls.

So if the die rolls 4 once, twice, ..., 50 million times, ..., $\tau -1$ times before finally landing on another value for the $\tau$th roll, it won't affect the probability of the event that $X_{\tau} > 4$.

$$\mathbb{P}(X_{\tau}>4|\tau=1)=\mathbb{P}(X_{\tau}>4|\tau=2)=\dots = \mathbb{P}(X_{\tau}>4|\tau=50,000,000)=\dots $$

Therefore we can assume, without loss of generality, that $\tau=1$. This is just the probability that the die lands a value greater than 4 given that it does not land on 4, which we can calculate very easily:

$$\mathbb{P}(X_1>4|X\not=4) = \frac{\mathbb{P}(X_1 > 4 \cap X_1 \not=4)}{\mathbb{P}(X_1 \not= 4)} = \frac{\mathbb{P}(X_1 > 4)}{\mathbb{P}(X_1 \not=4)}=\frac{\frac{1}{3}}{\frac{5}{6}}=\frac{1}{3}\cdot\frac{6}{5}=\frac{2}{5} $$ which of course is the correct answer.

You can read more about stopping times and the Strong Markov property in Section 8.3 of (the 4th edition of) Durrett's Probability Theory and Examples, p. 365.

Answer 5

Another way to look at the problem.

Lets call a 'real result' a 1,2,3,5 or 6.

What is the probability of winning on the first roll, if you got a 'real result'? 2/5

What is the probability of winning on the second roll, if the second roll is the first time you got a 'real result'? 2/5

Same for third, fourth.

So, you can break your sample in (infinte) smaller samples, and those samples all give the same probability.