6

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?

Ted
  • 365
  • What kind of interview was it, job interview? If yes, did you get the job although you failed? – callculus42 Jan 15 '20 at 18:11
  • 1
    It was an intern interview. Specifically machine learning intern. I'm a new grad. – Ted Jan 15 '20 at 18:14
  • 1
    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. – callculus42 Jan 15 '20 at 18:18
  • 1
    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

2 Answers2

5

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$

lulu
  • 70,402
  • 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. – Shon Verch Jan 15 '20 at 18:43
  • 1
    @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. – Shon Verch 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
  • Yea, that certainly seems like a problem reminiscent of machine learning. I don't think there is a purely analytical way of approaching it so perhaps gradient descent? – Shon Verch Jan 15 '20 at 18:50
  • 1
    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
  • @ShonVerch It's intriguing. That particular problem is too easy to see directly...I'll try to design a variant of it where you can't realistically plot all the values in the desired range. As a rule, optimization questions when you know in advance that the field is extremely flat are very hard. – lulu Jan 15 '20 at 18:53
1

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

Fil727
  • 111