rolling dice - win if the sum of rolls is exactly $n$

This question was asked during my interview: Suppose you have a fair dice (6 faces as usual). You can pick a positive integer $$n$$. Then you can repeatedly roll a dice until the sum of the rolls exceeds or equals to $$n$$. If the sum is exactly $$n$$, it is a win. Otherwise, you lose. Find $$n$$ that maximizes your chance of winning.

Let $$P(n)$$ be probability of win when the value is $$n$$. Then, $$P(n) = \sum_{i=1}^6 \frac{1}{6}P(n-i)$$

However, solving this recurrence seems complicated and tedious. Is there an easier way to solve this?

• What kind of interview was it, job interview? If yes, did you get the job although you failed? Jan 15 '20 at 18:11
• It was an intern interview. Specifically machine learning intern. I'm a new grad.
– Ted
Jan 15 '20 at 18:14
• For large numbers we can use the fact that the average "jump" is $3.5$ to see that about $1$ in every $3.5$ numbers is hit, making the probability that we get some large specified large number $\frac 1{3.5}\approx .2857$ which is less than the probability of getting a $6$, say (which I see to be about $.36$ assuming I didn't botch the hasty computation).
– lulu
Jan 15 '20 at 18:15
• @Ted That´s interesting. Jan 15 '20 at 18:18
• Indeed, we get to the $.2857$ limit very quickly, so there are only a handful of numbers to test. As expected, $6$ is maximal.
– lulu
Jan 15 '20 at 18:22

As you remark, for $$n>6$$ the probability that you land on $$n$$ is the average of the $$6$$ predecessor probabilities. As such, it can never exceed the maximum of those $$6$$.

It is clear that $$n=6$$ has the greatest probability of the first six values (easy to check this by hand, of course). Thus no value beyond $$6$$ can be more likely, as iterated averages must lower the maximum. Thus the maximum value occurs for $$n=6$$, for which the probability is just a little greater than $$.36$$

It's not even close. $$P(5)\approx .30877$$ and $$P(n)<.3$$ for all $$n\neq 5,6$$. The limiting value, for large $$n$$ is $$\frac 1{3.5}\approx .28571429$$ since the average toss of the die is $$3.5$$ This limit is reached fairly quickly, as $$P(26)\approx .28574$$

• It should also be noted that it's really easy to verify this computationally since each recurrence must only iterate through a maximum of six times, and unless $n$ is absurdly large, you'll reach the base case fairly quickly. It can also be sped up using dynamic programming techniques. Jan 15 '20 at 18:43
• @ShonVerch Absolutely. Indeed, I first did this numerically and only after that realized that it followed from the simple consideration of averages.
– lulu
Jan 15 '20 at 18:45
• Yep! Given as this seems to an interview question for machine learning, I don't think they intended for the recurrence to simplify, I think they just wanted to see an implementation of it. Jan 15 '20 at 18:46
• @ShonVerch with that in mind, a harder question would be "for which value $>6$ is the probability maximized?" Numerically, that appears to be $n=11$, and I don't immediately see a simple way to intuit that. The probability is fairly flat out there.
– lulu
Jan 15 '20 at 18:49
• I have never thought about iterated averages. Thanks for the idea! @Shon Verch. I was given a technical written test and was asked to provide an analytical solution, not an implementation
– Ted
Jan 15 '20 at 18:52

Let us start from the probability of winning when $$n = 1$$. This can only happen when the first toss of the die results in a 1. We lose if it does not end up on 1. So, the probability of winning with $$n = 1$$ is $$1/6$$,

$$P(1)=\frac{1}{6} \approx 0.1667\;.$$

When $$n=2$$, we can win if the first toss results in a 2, which has probability $$1/6$$, or if the first toss results in a 1 and the second toss results in a 1. Note that if the first toss results in 1, the probability of winning with the second toss is $$P(1)$$,

$$P(2)=\frac{1}{6} + \frac{1}{6}P(1) = \frac{7}{6}P(1) = \frac{7}{6^2} \approx 0.1944\;.$$

For $$n=3$$, if the first toss results in a 3, we win with probability $$1/6$$. If the first toss results in a 2, we win with probability $$1/6 * P(n=1)$$ because the probability of getting a 2 in the first toss is $$1/6$$ and the probability of getting from 2 to 3 in the subsequent tosses is $$P(n=1)$$. Similarly, if the first toss results in a 1, we win with probability $$1/6 * P(n=2)$$ because the probability of getting 1 in the first toss is $$1/6$$ and the probability of going from 1 to 3 in subsequent tosses is $$P(n=2)$$. Summing the probabilities of these three cases, we get,

$$P(3)=\frac{1}{6} + \frac{1}{6}P(2) + \frac{1}{6}P(1) = \frac{7}{6}P(2) = \frac{7^2}{6^3} \approx 0.2269\;,$$

where, in the second equality, we used the definition of $$P(2)$$. For $$n=4, 5, 6$$ we follow the same reasoning of splitting the probability of $$P(n)$$ based on the result of the first toss of the die to obtain,

\begin{align} P(4) &= \frac{1}{6} + \frac{1}{6}P(3) + \frac{1}{6}P(2) + \frac{1}{6}P(1) = \frac{7}{6}P(3) = \frac{7^3}{6^4} \approx 0.2647 \;, \\ P(5) &= \frac{1}{6} + \frac{1}{6}P(4) + \frac{1}{6}P(3) + \frac{1}{6}P(2) + \frac{1}{6}P(1) = \frac{7}{6}P(4) = \frac{7^4}{6^5} \approx 0.3088 \;, \\ P(6) &= \frac{1}{6} + \frac{1}{6}P(5) + \frac{1}{6}P(4) + \frac{1}{6}P(3) + \frac{1}{6}P(2) + \frac{1}{6}P(1) = \frac{7}{6}P(5) = \frac{7^5}{6^6} \approx 0.3602 \;. \end{align}

So far, the probabilities increased gradually from $$n=1$$ to $$n=6$$ and the maximum probability is P(6).

We can summarise the probabilities for $$n$$ from 1 to 6 as,

$$P(n) = \frac{7}{6}P(n-1) = \frac{1}{7}\left(\frac{7}{6}\right)^n \,, \; n=1, 2, \ldots, 6 \;.$$

For $$n=7$$, as we did before, we split the probability based on the result of the first toss of the die. If the first toss results in a 1 (probability 1/6), the probability to reach 7 in the remaining tosses is $$P(7-1)=P(6)$$. If the first toss results in a 2 (probability 1/6), the probability to reach 7 in the remaining tosses is $$P(7-2)=P(5)$$, and so on. So, we obtain,

\begin{align} P(7) &= \frac{1}{6}P(6) + \frac{1}{6}P(5) + \frac{1}{6}P(4) + \frac{1}{6}P(3) + \frac{1}{6}P(2) + \frac{1}{6}P(1) \\ &= \frac{1}{6} \left[ P(6) + P(5) + P(4) + P(3) + P(2) + P(1) \right] \;. \end{align}

Thus, $$P(7)$$ is the average of the probabilities of the previous 6 $$n$$'s. Since $$P(6)$$ is the highest probability in the sum in square brackets, the average is lower than $$P(6)$$. So, $$P(7)$$ is lower than $$P(6)$$. Indeed, if we carry out the calculation, we get $$P(7) \approx 0.2536$$.

We can apply the same reasoning to any $$n \geq 7$$ to obtain,

$$P(n) = \frac{1}{6} \left[ P(n-1) + P(n-2) + P(n-3) + P(n-4) + P(n-5) + P(n-6) \right] \;.$$

When $$P(6)$$ is present in the square brackets, it is the highest probability, meaning that the average is always smaller than $$P(6)$$. When $$P(6)$$ is not present in the square brackets, the highest probaility in the square brackets is lower than $$P(6)$$ and, as a consequence, the average is smaller than $$P(6)$$. Therefore, $$n=6$$ is the number with the highest probability of winning, which is approximately 36%.