3. In the game of Patience, you roll a fair, 6-sided die repeatedly. If the die

Question

3. In the game of Patience, you roll a fair, 6-sided die repeatedly. If the die ever shows 1, you lose the game and get S0. You may also choose to stop at any time before rolling a 1, in which case you win the amount shown on the die after the last roll (so if you choose to stop after rolling a 3, then you get $3). One strategy is to wait until a roll of k or greater before cashing out (with k being 2, 3, 4, 5, or 6). Find the expected value of the game when you follow this strategy with k = 2, k 3, k 4, k-5, and k = 6 (that's a total of 5 expected values to calculate). Which choice of k is best?

Explanation / Answer

Lets explore this with a roll of a dice. If you roll a dice 600 times, you would expect to see the
number one, 100 times:
P(Roll a 1) = (Chances For) / (Total Chances) = 100/600 = 1/6
Odds on the other hand are given as:
Odds(Roll a 1) = (Chances For) : (Total Chances) = 100 : 500 = 1 : 5

This question is similar to the example i am going to show

Q. Suppose we play a game with a die where we roll and sum our rolls. We can stop any time, and the
sum is our score. However, if our sum is ever a multiple of 10, our score is zero, and our game is over.
What strategy will yield the greatest expected score? What about the same game played with values
other than 10?

Ans. Let’s generalize things right away. Suppose we want to avoid multiples of m. For now, let’s suppose m 6.
Suppose we have been playing, and our sum is n, and
km < n < (k + 1)m
for some integer k > 0.
If our score is less than (k + 1)m 6, then we should certainly roll until it is at least (k + 1)m 6,
since there is no risk.
Suppose (k + 1)m 6 n < (k + 1)m. Should we roll to get past (k + 1)m? There is at least a 1/6
chance that this will result in a score of zero, and the best our score could be (without risking another
multiple of m) is (k + 2)m 1. Hence the expected value E of our score with risking one multiple
of m is
E < 5/6 ((k + 2)m 1)
and this is less than (k + 1)m 6 if
k > 4 + 31/m.
Hence, if k > 4 + 31/m
, then we should stop rolling if our score, n, is in the interval
km < n < (k + 1)m
and possibly earlier.
Suppose m = 10. Then 4 + 31
10 = 7.1, so (with k = 8 > 7.1) we should definitely stop rolling if our score is between 84 and 89.
We can then work out an optimal strategy recursively as follows.
Let E(x) be the expected value of our ultimate score if our sum is ever x.
Then E(84) = 84, E(85) = 85, E(86) = 86, E(87) = 87, E(88) = 88, and E(89) = 89 (since we will stop at any of those scores). We also know E(x) = 0 if x is a positive multiple of m.
We can then define f(n) = 1/6Ei=16 E(n + i).

Then, if f(n) > n, we should roll when our sum is n
and E(n) = f(n). On the other hand, if f(n) n, we should stop rolling when our sum is n and
E(n) = n.
In this way, we can calculate E(n) downward from n = 83 to n = 0, noting whether we stop rolling
or not to create our optimal strategy and the expected value of our strategy.

Writing a little code, we can thus find that we should roll unless the sum is 24 or 25 or greater than
33. With this strategy, the expected score is
162331123011053862884431
12281884428929630994432
= 13.21711859042473....
Applying this same method to other values of m, we have the following table.
m stop if expected value
6 n 19 7.22
7 n 15 8.58
8 n = 18 or n 26 10.12
9 n = 21, 22 or n 30 11.67
10 n = 24, 25, or n 33 13.21
11 n = 27, 28 or n 38 14.72
12 n = 30, 31 or n 42 16.27
13 n = 33, 35, 35 or n 46 17.90
14 n = 36, 37, 38 or n 50 19.43
15 n = 39, 40, 41 or n 54 20.97
16 n = 42, 43, 44, 58, 59, 60, 61, 62 or n 74 22.51
17 n = 45, 46, 47, 62, 63, 64, 65, 66 or n 79 24.07
18 n = 48, 49, 50, 66, 67, 68, 69, 70 or n 84 25.64
19 n = 51, 52, 53, 70, 71, 72, 73, 74 or n 89 27.2136
20 n = 54, 55, 56, 74, 75, 76, 78 or n 94 28.75
For 2 m 5, it is probably best to attack each one separately, which perhaps I will do some other
time.

similarly in our question we can replace m 6 with m 1 and then follow same steps.

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.