20
$\begingroup$

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?

$\endgroup$
  • 6
    $\begingroup$ That's a lot of effort to set up the recurrence relation. You have good reason to believe that the answer is 0.4. That's a strong hint that there's another way to think of the problem that gets you the answer directly. Look for it. Geomatt's answer will get you there, which in turn will help you understand what's going on here and even help you simplify other problems you encounter more quickly without this sort of effort. If a seemingly complicated problem appears to have a simple answer, you should always invest the time to try to figure out why. Pays huge dividends later. $\endgroup$ – Joel Aug 28 '16 at 6:46
  • 8
    $\begingroup$ Once you realize that due to the equal probabilities of all six results and the independence of the rolls there is nothing special about any particular outcome of this experiment, it is obvious that all five of the possible results are equally probable. $\endgroup$ – whuber Aug 28 '16 at 16:35
  • 6
    $\begingroup$ I'm slightly disappointed nobody has put up the absorbing Markov Chain solution to this yet :-) Math Stack Exchange has a noble tradition of the "overkill solution" that rarely seems to permeate to Cross Validated... $\endgroup$ – Silverfish Aug 28 '16 at 21:48
  • 2
    $\begingroup$ It is 2/5 to pick either of $\{5,6\}$ from $\{1,2,3,5,6\}$ so your simulation is probably correct. $\endgroup$ – mathreadler Aug 29 '16 at 9:59
  • 2
    $\begingroup$ This post vs the answers is what I imagine data scientists are like vs statisticians. $\endgroup$ – bdeonovic Aug 29 '16 at 18:12
47
$\begingroup$

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}

$\endgroup$
  • 2
    $\begingroup$ Note that this calculation is only valid because the Strong Markov Property holds for discrete Markov chains. $\endgroup$ – Chill2Macht Aug 30 '16 at 4:52
  • $\begingroup$ I don't recall my discrete Markov chains, but, I'd hazard, from simple math, that you mean that the recurrence relation is only valid because of the Strong Markov Property. After the relation is established, we are just solving for x. $\endgroup$ – josinalvo Aug 31 '16 at 7:33
  • $\begingroup$ Is this correct? $\endgroup$ – josinalvo Aug 31 '16 at 7:34
  • 1
    $\begingroup$ @josinalvo: Technically, the question is whether P(W) on both sides of the equation mean the same. The Strong Markov Property implies they do. In the absence of that property, P(W) on the left side means "the chance to win with this roll" and 1/6*P(W) on the right means "the chance to win after rolling a 4". $\endgroup$ – MSalters Apr 18 '17 at 11:52
81
$\begingroup$

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%.

$\endgroup$
  • 8
    $\begingroup$ You can make this a little more direct: "Consider the first roll that is not a 4. Then the outcomes ..." $\endgroup$ – Joel Aug 28 '16 at 6:47
  • 2
    $\begingroup$ Most people's eyes roll over when they see tons of math, so I like this one better. Basically you are removing 4 from the results, so it is 1, 2, 3, 5, 6. It becomes obvious you have 40% chance at that point. $\endgroup$ – Nelson Aug 29 '16 at 1:23
  • $\begingroup$ I thought this from the title, so mostly just skimmed the full question after I clicked on it. Otherwise I probably would have confused myself and second-guessed! $\endgroup$ – GeoMatt22 Aug 29 '16 at 1:29
  • 1
    $\begingroup$ @Nelson I've seen more people whose eyes roll over when they see this kind of reasoning in a probability problem than people whose eyes roll over when they see $p=a+bp$. $\endgroup$ – JiK Aug 29 '16 at 9:40
  • $\begingroup$ Yes. The moral of the story is: don't try to make a problem harder than it needs to be. $\endgroup$ – Jay Aug 30 '16 at 1:16
14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @William, I don't think your comment is appropriate for several reasons. 1. I never said that you need geometric series for this. 2. The concepts you use in your answer are much heavier machinery, it's ironic to say "you don't need geometric series! You just need the much more advanced and sophisticated strong Markov property". 3. A solution which is simple and rigorous was already provided by dsaxton. Your method is more roundabout and overkill for this problem. 4. The OP already had an expression equivalent to a geometric series, someone had to address that, may as well be me. $\endgroup$ – Meni Rosenfeld Aug 30 '16 at 9:50
  • 1
    $\begingroup$ @William: Ultimately, your own answer is fine, insightful, and a useful addition to the collection of answers to the question. That doesn't mean you should go to every other answer and say that yours is so much better. They're all fine as well. Not everything has to be approached in the most abstract and general way possible. $\endgroup$ – Meni Rosenfeld Aug 30 '16 at 9:51
  • $\begingroup$ It has been a while since I was a math major, so I apologize if my answer lacked rigor. (Just please don't tell me it relies on the axiom of choice, as that would be humiliating!) :) $\endgroup$ – GeoMatt22 Sep 20 '16 at 13:31
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ As far as I can tell from the wiki entry, the existence of a stopping time is necessary but not sufficient to say that a series of events exhibits the SMP. Sorry if I'm missing an in-joke or profound insight, but why not just assume that rolls are independent and get on with it? $\endgroup$ – Jacob Raihle Aug 30 '16 at 15:35
  • $\begingroup$ @JacobRaihle "Strong Markov property, which for a discrete Markov Chain is equivalent to the regular Markov property." This scenario clearly constitutes a discrete Markov chain. The rolls are independent, that's why it's a discrete Markov chain. The issue is that the event "first roll which does not land on 4" is not independent of the previous rolls, for reasons which are hopefully obvious. $\endgroup$ – Chill2Macht Aug 30 '16 at 15:50
  • $\begingroup$ It's equally clear that the rolls are independent. So what additional benefit does the SMP provide? $\endgroup$ – Jacob Raihle Aug 30 '16 at 15:55
  • $\begingroup$ @JacobRaihle Even though the value of the rolls are independent, the value of the die the first time it lands on a value not equal to 4 is NOT independent of the values on which the die landed on previous rolls. $\endgroup$ – Chill2Macht Aug 30 '16 at 15:59
  • $\begingroup$ It should be, since the rolling stops as soon as that happens. There can be no non-4 roll that isn't also the first one. And even if that were not the case, I'm not sure what kind of relationship you are suggesting. $\endgroup$ – Jacob Raihle Aug 30 '16 at 16:01
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.