12
$\begingroup$

Here's the question:

You have a standard six-sided die and you roll it repeatedly, writing down the numbers that come up, and you win when two of your rolled numbers add up to $7$. (You will almost surely win.) Necessarily, one of the winning summands is the number rolled on the winning turn. A typical game could go like this: $1, 1, 4, 5, 3$; you win on the 5th turn because $3 + 4 = 7$. How many turns do you expect to play?

Here's what I've tried: We seek $E(N)$ where $N$ is a random variable counting the number of turns it takes to win. Then $N \ge 2$, and $$E(N) = \sum_{n=2}^\infty n P(N=n) = \sum_{n=1}^\infty P(N > n).$$ I want to find either $P(N=n)$, the probability that I win on the $n$th turn, or $P(N > n)$, the probability that after $n$ turns I still haven't won. Note that $P(N = 1) = 0$. Let $X_k$ be the number rolled on the $k$th turn. Then $$P(N = 2) = P(X_1 + X_2 = 7) = \sum_{x=1}^6 P(X_1 = x)P(X_2 = 7-x) = 6\cdot \frac{1}{6}\cdot\frac{1}{6} = \frac{1}{6}.$$ So far so good. To compute $P(N > 3)$ I let $A_{i, j} = \{\omega \in \{1, \dotsc, 6\}^3 : w_i + w_j = 7\}$ and used the inclusion-exclusion principle and symmetry to find $$|A_{1,2} \cup A_{2,3} \cup A_{1,3}| = 3|A_{1,2}| - 3|A_{1,2}\cap A_{1,3}| = 90$$ so $P(N > 3) = \frac{126}{216} = \frac{7}{12}$. This is the probability that no two of three dice sum to seven. Similarly, I found $P(N > 4)$ to be $\frac{77}{216}$.

I don't see how to generalize the above. I also thought that $$P(N > n) = P(X_i + X_j \ne 7 \text{ for all }1 \le i\ne j \le n) = (1 - P(X_i + X_j = 7))^{\binom{n}{2}} = \left(\frac{5}{6}\right)^{n(n-1)/2}$$ but that's false because the events are not independent.

I also tried $$P(N = n) = P(X_n = 7 - X_k \text{ for some } 1 \le k < n \text{ and }N \ne n - 1)$$ where that last clause is shorthand for "and the previous rolls did not secure your victory". This yields the recursion $p_n = (1-(5/6)^{n-1})(1-p_{n-1})$, $p_1 = 0$, which didn't agree with my previously computed probabilities. (Perhaps I made an error.)

$\endgroup$
  • $\begingroup$ Hint: in enumerating the sequences of rolls there are six choices for the first one and five for all the other ones that follow. $\endgroup$ – Marko Riedel Apr 18 '16 at 20:26
  • $\begingroup$ For clarification, would the sequence of rolls $1,3,6$ result in a termination on roll three since $1+6=7$ despite the one and six not being adjacent? $\endgroup$ – JMoravitz Apr 18 '16 at 20:31
  • $\begingroup$ If it helps, then $P(N=3)=\frac{54}{6^3},P(N=4)=\frac{294}{6^4},P(N=5)=\frac{1206}{6^5}$. $\endgroup$ – barak manos Apr 18 '16 at 20:47
  • 2
    $\begingroup$ When you say "You will always win", I assume you mean "You will almost surely win". Because it is possible (however unlikely) to get only $1,2$ and $3$ indefinitely. $\endgroup$ – Arthur Apr 18 '16 at 20:48
  • $\begingroup$ @JMoravitz Yes, of course, the rolls involved in the final sum do not have to be consecutive. I will modify the example since it is apparently misleading. $\endgroup$ – Unit Apr 18 '16 at 23:19
17
$\begingroup$

To be clear: What follows assumes that the pair that adds to $7$ need not be consecutive. Thus, for example, I am assuming that the sequence $\{1,3,6\}$ ends the game in three rolls.

Let $E=E_0$ be the answer. If you have rolled a collection $S$ which contains no pair which adds to $7$ then let $E_S$ denote the expected number of rolls it will take from there. As every roll is equally probable, all that really matters is the size of $S$, so let $E_S=E_n$ if $S$ has $n$ elements. Of course the only possible $n$ are $\{0,1,2,3\}$.

We start with $E_3$. We note that rolling again has a $\frac 12$ chance of completing the $7$ and a $\frac 12$ chance of getting a useless duplicate, thus $$E_3=\frac 12\times 1+\frac 12 \times (E_3+1)\implies E_3=2$$

Now for $E_2$. As before we consider the next toss and write $$E_2=\frac 13\times 1+\frac 13 \times (E_2+1)+\frac 13 \times (E_3+1)\implies E_2=\frac 52$$

And $E_1$. As before $$E_1=\frac 16\times 1+\frac 16 \times (E_1+1)+\frac 46\times (E_2+1)\implies E_1=\frac {16}5$$

And then of course $$E=E_1+1=\frac {21}5$$

$\endgroup$
  • $\begingroup$ Lulu, your assumption is (obviously) correct, and this is a beautiful answer! $\endgroup$ – Unit Apr 18 '16 at 23:33
  • $\begingroup$ Given the definition of $E_3$ (the expected number of rolls to win having already rolled three numbers) I understand the intuition behind the identity $E_3 = \frac{1}{2} + \frac{1}{2}(E_3 + 1)$. Unfortunately, I wouldn't be able to come up with this myself, and I don't see where this comes from formally. Is this conditional expectation? Total expectation? What random variables are involved here? $\endgroup$ – Unit Apr 18 '16 at 23:45
  • 1
    $\begingroup$ The random variables are the outcomes of the next toss. This type of argument comes from thinking about Markov processes (which I strongly recommend learning about). The idea is this: writing out all the paths is tedious and difficult (as you learned) but it is also unnecessary. You don't need the full history...all you need to keep track of is the list of values you have observed. That's the meaning of my $E_S$...it says "just look at the list of values you have observed and go from there...forget about the exact path you took in seeing those values." $\endgroup$ – lulu Apr 18 '16 at 23:51
  • 1
    $\begingroup$ To be clear: my argument and the argument of @JMoravitz are really the same. I prefer the language of states...I think it is clearer and more intuitive for people who aren't used to Markov computations. On the other hand, the matrix arguments are essential if you have a lot of states. For example, if you ask your question with a weighted die (different probabilities for each value) then you need a different state for every subset and my method would get too involved...for that one, I'd use a matrix just to hold the information more efficiently. $\endgroup$ – lulu Apr 18 '16 at 23:58
  • $\begingroup$ I was asking for something explicit. Here's what I got: for any subset $S$ of $\{1, \dotsc, 6\}$ let $N_S$ be the number of rolls it takes to win, having already rolled the numbers in $S$. Then $E(N_S) = P(N_S = 1) + \sum_{n=1}^\infty (n+1) P(N_S = n+1)$. For $|S| = 3$, $P(N_S = 1) = \frac{1}{2}$ since we can roll any number not in $S$. For the other sum, $P(N_S = n+1)$ equals the probability of rolling something useless times the probability of winning $n$ steps after that, so it's $\sum_{k \in S} \frac{1}{6} P(N_{S\cup\{k\}} = n) = \frac{1}{2} P(N_S = n)$. $\endgroup$ – Unit Apr 19 '16 at 0:23
7
$\begingroup$

assuming that rolls need not be consecutive I.e. $1,3,6$ would be a terminating sequence of rolls since $1+6=7$ despite the $1$ and the $6$ not being adjacent.

I will admit I didn't read through all of your work, but this is the method I would approach the problem from. We can describe this using an absorbing markov chain with the following states:

$A_1 = $ Exactly one type of number has been seen so far. (This can be used as the starting state as we are guaranteed to enter this state after the first roll)

$A_2 = $ Exactly two types of numbers have been seen so far and they do not sum to seven. (The two numbers would be both from $\{1,2,3\}$, both from $\{4,5,6\}$, or one from each)

$A_3 = $ Exactly three types of numbers have been seen so far and no pair of which sum to seven. (The three numbers would be all from $\{1,2,3\}, \{4,5,6\}$ or from some combination thereof)

Finally, $B$ will be the endstate where we have some pair of numbers adding to seven. Convince yourself that these are indeed the only possible states.

From each state, you may either travel from $A_i$ to $A_{i+1}$, from $A_i$ to itself, or from $A_i$ to $B$ according to the following stochastic matrix with order of rows and columns as $A_1,A_2,A_3,B$

$$\begin{bmatrix} \frac{1}{6} & 0 & 0 & 0\\ \frac{2}{3} & \frac{1}{3} & 0 & 0\\ 0&\frac{1}{3}&\frac{1}{2}&0\\ \frac{1}{6}&\frac{1}{3}&\frac{1}{2}&1\end{bmatrix}$$

Recognizing this as an absorbing stochastic matrix, we rearrange the rows/columns into standard form: $\left[\begin{array}{c|c} I&S\\\hline 0&R\end{array}\right]$. We will instead use order $B,A_1,A_2,A_3$ for rows and columns

$$\begin{bmatrix} 1&\frac{1}{6}&\frac{1}{3}&\frac{1}{2}\\ 0&\frac{1}{6}&0&0\\ 0&\frac{2}{3}&\frac{1}{3}&0\\ 0&0&\frac{1}{3}&\frac{1}{2}\end{bmatrix}$$

In solving for the long-term state in the case of multiple possible absorbing states, we would calculate it using the limiting matrix: $\left[\begin{array}{c|c}I&S(I-R)^{-1}\\0&0\end{array}\right]$. Of course, in the current problem, there is only one ending state, so we know it will become $1$ in the entire top row and zeroes elsewhere. Still, the matrix $(I-R)^{-1}$ contains incredibly useful information and is referred to as the fundamental matrix for the markov chain. Depending on starting position, the sum of the column will give the expected number of turns until reaching an endstate. Alternatively, if the starting position is unknown, multiplying by an appropriate probability vector will give the desired information.

In our case: $I-R = \begin{bmatrix}\frac{5}{6}&0&0\\-\frac{2}{3}&\frac{2}{3}&0\\0&-\frac{1}{3}&\frac{1}{2}\end{bmatrix}$

$(I-R)^{-1} = \begin{bmatrix}1.2&0&0\\1.2&1.5&0\\0.8&1&2\end{bmatrix}$

Summing along the first column, we expect from having started in state $A_1$ it to take $1.2+1.2+.8 = 3.2$ turns to complete. Accounting for the fact that it takes one turn to enter state $A_1$, this gives a total expected time as $4.2$ turns.


As an aside, one can extract $Pr(N=n)$ from the stochastic matrix. Letting $A$ be the matrix in standard form and $v$ be the column vector with a $1$ in the second entry and zeroes elsewhere, you have the first entry of $A^{n-1}v - A^{n-2}v$ will give the probability that you arrive at the endstate on turn $n$ but not having already been there on turn $n-1$.

$\endgroup$
  • $\begingroup$ It is fine that you did not read through all of my work; it is incorrect, and I included it simply to avoid being asked "What have you tried?". I have never heard of absorbing Markov chains before - time to read up. Thanks for your answer! $\endgroup$ – Unit Apr 18 '16 at 23:37
  • $\begingroup$ @Unit PatrickJMT does a good job explaining the basics, though his notation differs from that which I use. He uses row-stochastic matrices and row-vectors, whereas I use column-stochastic matrices and column-vectors. The theory is the same, though often transposed. Alternatively, several books on linear algebra, "finite-mathematics," or probability will contain units on markov chains as they are rich examples. $\endgroup$ – JMoravitz Apr 19 '16 at 1:18
  • $\begingroup$ For completeness' sake, I found $P(N = n)$ by the indicated method (diagonalizing the matrix to take its $n$th power): it's $0$ for $n \le 1$ and $8/2^n - 24/3^n + 30/6^n$ for $n \ge 2$. $\endgroup$ – Unit Apr 29 '16 at 18:41
0
$\begingroup$

The answer is: 4.

Reasoning: A six sided die presumably has numbers in $\{1,...,6\}$. Every one of those numbers can be used to add to $7$. So take your first roll. It doesn't matter what the number is. Now look at your die. There is one number that can add to seven with your first number, and you can roll it with probability $1/6$. Thus, the probability of winning on each successive turn is $1/6$. The probability of winning on a successive turn is given by the binomial distribution where $p = 1/6$.

The interesting part about this problem is how it is phrased: it is asking for how many turns you expect to need until you win. To me, that means the number of rolls required to find a probability of you winning $\ge 1/2$.

The expected value of the binomial distribution is $np$. So, we want $np \ge 1/2$. Since $p = 1/6$, $n$ must be at least $3$. Therefore, you need your first turn ($1$) plus your $3$ "expected" turns to win: $1 + 3 = 4$.

$\endgroup$
  • $\begingroup$ This is wrong. Yes, after the first roll, there is only one following number that will sum to 7, which means the probability of winning after 2 rolls is 1/6. But if you do not win after the second roll, having rolled either the same number as the first, or a different, but non-winning number, the probability of winning on the third roll is at least 1/6 (and strictly greater in the "different and non-winning" case, as there are now two available complements to 7 that can make you win). So "the probability of winning on each successive turn" is not 1/6. $\endgroup$ – Unit Apr 19 '16 at 17:26
  • $\begingroup$ As for the phrasing of the problem, I believe it is unambiguous. When I ask for the expected number of rolls, I am referring to mathematical expectation, which is, in this case, the quantity $p_1 + 2p_2 + 3p_3 + \dotsb$ where $p_n$ is the probability of winning on the $n$th roll. $\endgroup$ – Unit Apr 19 '16 at 17:29
  • $\begingroup$ @Unit, Sorry for the late reply. It sounds like you're looking for the cumulative distribution function, whose expectation gives precisely the result you're interested in. While I was pointing out that the probability of winning on the nth roll given the (n-1)st roll is unsuccessful is exactly 1/6 (else, you wouldn't be rolling). The CDF is given by the sum from 1 to the n'th roll: p_n = sum((5/6)^(n-1)*(1/6) * (n)C(i)) from i=1 to n In this case, we would need to sum to infinity, or alternatively approximate by a gaussian computationally and integrate. $\endgroup$ – Paul Straus Apr 25 '16 at 3:43
  • $\begingroup$ No, I am not looking for the c.d.f. And again, the probability of winning on the $n$th roll given an unsuccessful $(n-1)$st roll is not 1/6. If you roll a 1 on your first roll and a 2 on your second, your second roll was unsuccessful. On your third roll, you will win if you get a 5 or a 6: that's a 1 in 3, not a 1 in 6, chance of winning. $\endgroup$ – Unit Apr 25 '16 at 3:44
  • $\begingroup$ Ahh I see. Looks like I misinterpreted part of the problem. $\endgroup$ – Paul Straus Apr 25 '16 at 3:48
0
$\begingroup$

While not exactly stated, it seems that you win only if the sum of consecutive numbers sums to 7.

Obviously you can't win on the first roll. For every roll thereafter, you have a $1/6$ chance of winning on the next roll, (and a $5$ in $6$ chance of the game continuing).

Now, $P(N=2) = \frac{1}{6}$, $P(N=3) = \frac{5}{6}\times\frac{1}{6}$, $P(N=4) = \left(\frac{5}{6}\right)^2\times\frac{1}{6}$, so $P(N=n) = \left(\frac{5}{6}\right)^{n-2}\times\frac{1}{6}$.

Thus $$E(N) = \sum P(N=n)n = 2\times\frac{1}{6} + 3\times\frac{5}{6}\times\frac{1}{6} + 4\times\left(\frac{5}{6}\right)^2\times\frac{1}{6} + \dotsb = \frac{1}{6} \sum_{n=0}^{\infty}(n+2)\left(\frac{5}{6}\right)^n.$$

I don't know if you need to derive this, but, $$\sum_{n=1}^{\infty} n x^{n-1} = \sum_{n=0}^{\infty}(n+1) x^n = \frac{1}{1-x}\sum_{n=0}^\infty x^n = \frac{1}{(1-x)^2}$$ so $$\frac{1}{6}\sum_{n=0}^{\infty}(n+2)\left(\frac{5}{6}\right)^n = \frac{1}{6}\sum_{n=0}^\infty(n+1)\left(\frac{5}{6}\right)^n + \frac{1}{6}\sum_{n=0}^\infty \left(\frac{5}{6}\right)^n$$ which equals $$\frac{1}{6}\times\frac{1}{\left(1-\frac{5}{6}\right)^2} + \frac{1}{6}\times\frac{1}{1-\frac{5}{6}} = 7.$$

$\endgroup$
  • 2
    $\begingroup$ From the question, "you win when two of your rolled numbers add up to 7". This is clear. It doesn't mean "you win when the last two of your rolled numbers add up to 7". $\endgroup$ – John Bentin Apr 18 '16 at 21:33
  • $\begingroup$ You missed the \ before infty on the first sum in your second to last line. I would have fixed it, but I don't have full edit privileges and that won't meet the six character minimum for an edit. $\endgroup$ – Matthew Apr 18 '16 at 23:13
  • $\begingroup$ Sorry, Doug: you win if the sum of any two rolls is 7. Your misconception must have arisen from the "typical game" I provided; I have modified the example. Thanks for your effort! $\endgroup$ – Unit Apr 18 '16 at 23:27

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.