6
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ What kind of interview was it, job interview? If yes, did you get the job although you failed? $\endgroup$ Jan 15 '20 at 18:11
  • 1
    $\begingroup$ It was an intern interview. Specifically machine learning intern. I'm a new grad. $\endgroup$
    – Ted
    Jan 15 '20 at 18:14
  • 1
    $\begingroup$ 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). $\endgroup$
    – lulu
    Jan 15 '20 at 18:15
  • $\begingroup$ @Ted That´s interesting. $\endgroup$ Jan 15 '20 at 18:18
  • 1
    $\begingroup$ Indeed, we get to the $.2857$ limit very quickly, so there are only a handful of numbers to test. As expected, $6$ is maximal. $\endgroup$
    – lulu
    Jan 15 '20 at 18:22
5
$\begingroup$

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$

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Shon Verch
    Jan 15 '20 at 18:43
  • 1
    $\begingroup$ @ShonVerch Absolutely. Indeed, I first did this numerically and only after that realized that it followed from the simple consideration of averages. $\endgroup$
    – lulu
    Jan 15 '20 at 18:45
  • $\begingroup$ 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. $\endgroup$
    – Shon Verch
    Jan 15 '20 at 18:46
  • $\begingroup$ @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. $\endgroup$
    – lulu
    Jan 15 '20 at 18:49
  • 1
    $\begingroup$ 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 $\endgroup$
    – Ted
    Jan 15 '20 at 18:52
1
$\begingroup$

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

$\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.