35
$\begingroup$

There's a question in my Olympiad questions book which I can't seem to solve:

You have the option to throw a die up to three times. You will earn the face value of the die. You have the option to stop after each throw and walk away with the money earned. The earnings are not additive. What is the expected payoff of this game?

I found a solution here but I don't understand it.

$\endgroup$
  • 3
    $\begingroup$ Whats the name of the olympiad book? $\endgroup$ – PT272 Jul 13 '16 at 14:03
62
$\begingroup$

Let's suppose we have only 1 roll. What is the expected payoff? Each roll is equally likely, so it will show $1,2,3,4,5,6$ with equal probability. Thus their average of $3.5$ is the expected payoff.

Now let's suppose we have 2 rolls. If on the first roll, I roll a $6$, I would not continue. The next throw would only maintain my winnings of $6$ (with $1/6$ chance) or make me lose. Similarly, if I threw a $5$ or a $4$ on the first roll, I would not continue, because my expected payoff on the last throw would be a $3.5$. However, if I threw a $1,2$ of $3$, I would take that second round. This is again because I expect to win $3.5$.

So in the 2 roll game, if I roll a $4,5,6$, I keep those rolls, but if I throw a $1,2,3$, I reroll. Thus I have a $1/2$ chance of keeping a $4,5,6$, or a $1/2$ chance of rerolling. Rerolling has an expected return of $3.5$. As the $4,5,6$ are equally likely, rolling a $4,5$ or $6$ has expected return $5$. Thus my expected payout on 2 rolls is $.5(5) + .5(3.5) = 4.25$.

Now we go to the 3 roll game. If I roll a $5$ or $6$, I keep my roll. But now, even a $4$ is undesirable, because by rerolling, I'd be playing the 2 roll game, which has expected payout of $4.25$. So now the expected payout is $\frac{1}{3}(5.5) + \frac{2}{3}(4.25) = 4.\overline{66}$.

Does that make sense?

$\endgroup$
  • $\begingroup$ @ mixedmath♦ assuming that there is unlimited number of rolls, what would be calculation of E(x) for 4, 5 and 6 rolls? could you please demonstrate? I can't get the correct numbers, E(X) I calculate goes over six for 5 rolls which doesn't make sense. Intuitively, having unlimited number of rolls, one would keep rolling as long as six comes, so that the max E(x) should approach 6. is that correct? $\endgroup$ – Michal Oct 25 '16 at 14:18
  • $\begingroup$ I think it's worth looking at what this question really is essentially about. It's asking what is the expected payout given a perfect strategy. A perfect strategy would be by definition, "roll again if the probability of getting a greater number is more than 0.5 in the remaining throws, else stop". This inductive (sort of) method seems to be the only way to handle the calculations. The strategy used here is slightly different. It is 'roll again if the value is below the mean'. This assumes that the probability is normally distributed $\endgroup$ – Dis-integrating Jul 12 '17 at 20:12
  • $\begingroup$ or at least, the number of outcomes above and below the mean are the same. If the value is less than the mean, then we have an over 50% chance of getting more than the mean on the next throw. This strategy implies that we should only roll again if we are to be successful on the next throw. It doesn't account for the number of throws available. It also doesn't account for the changing mean? $\endgroup$ – Dis-integrating Jul 12 '17 at 20:15
43
$\begingroup$

This problem is solved using the theory of optimal stopping for Markov chains. I will explain some of the theory, then turn to your specific question. You can learn more about this fascinating topic in Chapter 4 of Introduction to Stochastic Processes by Gregory F. Lawler.


Think of a Markov chain with state space $\cal S$ as a game.

A payoff function $f:{\cal S}\to[0,\infty)$ assigns a monetary "payoff'' to each state of the Markov chain. This is the amount you would collect if you stop playing with the chain in that state.

In contrast, the value function $v:{\cal S}\to[0,\infty)$ is defined as the greatest expected payoff possible from each starting point; $$v(x)=\sup_T \mathbb{E}_x(f(X_T)).$$ There is a single optimal strategy $T_{\rm opt}$ so that $v(x)=\mathbb{E}_x(f(X_{T_{\rm opt}})).$ It can be described as $T_{\rm opt}:=\inf(n\geq 0: X_n\in{\cal E})$, where ${\cal E}=\{x\in {\cal S}\mid f(x)=v(x)\}$. That is, you should stop playing as soon as you hit the set $\cal E$.


Example:

You roll an ordinary die with outcomes $1,2,3,4,5,6$. You can keep the value or roll again. If you roll, you can keep the new value or roll a third time. After the third roll you must stop. You win the amount showing on the die. What is the value of this game?

Solution: The state space for the Markov chain is $${\cal S}=\{\mbox{Start}\}\cup\left\{(n,d): n=2,1,0; d=1,2,3,4,5,6\right\}.$$ The variable $n$ tells you how many rolls you have left, and this decreases by one every time you roll. Note that the states with $n=0$ are absorbing.

You can think of the state space as a tree, the chain moves forward along the tree until it reaches the end.

enter image description here

The function $v$ is given above in green, while $f$ is in red.

The payoff function $f$ is zero at the start, and otherwise equals the number of spots on $d$.

To find the value function $v$, let's start at the right hand side of the tree. At $n=0$, we have $v(0,d)=d$, and we calculate $v$ elsewhere by working backwards, averaging over the next roll and taking the maximum of that and the current payoff. Mathematically, we use the property $v(x)=\max(f(x),(Pv)(x))$ where $Pv(x)=\sum_{y\in {\cal S}} p(x,y)v(y).$

The value of the game at the start is \$4.66. The optimal strategy is to keep playing until you reach a state where the red number and green number are the same.

$\endgroup$
  • $\begingroup$ You beat me to it. Very good answer, because it allows for an easy generalization to $k$ dice rolls. $\endgroup$ – Jérémie Aug 6 '12 at 17:11
  • $\begingroup$ Thanks for your kind words. I enjoy teaching this topic very much, and I happen to use this exact problem! $\endgroup$ – user940 Aug 6 '12 at 17:14
  • $\begingroup$ That's a very nice graphic. How did you make it? It's also a very nice answer. $\endgroup$ – davidlowryduda Aug 6 '12 at 17:21
  • $\begingroup$ @mixedmath Thanks. The diagram comes from some notes that I use to teach Markov chains. I created it (a long time ago!) with pictex, and a lot of fiddling around. $\endgroup$ – user940 Aug 6 '12 at 17:23
  • $\begingroup$ @Byron I have a similar type of question HERE that I am still struggling with. Can you help me? $\endgroup$ – CodyBugstein Oct 14 '12 at 2:27
5
$\begingroup$

Suppose you have only two rolls of dice. then your best strategy would be to take the first roll if its outcome is more than its expected value (ie 3.5) and to roll again if it is less. Hence the expected payoff of the game rolling twice is: \begin{equation} \frac{1}{6}(6+5+4) + \frac{1}{2}3.5 = 4.25. \end{equation} If we have three dice your optimal strategy will be to take the first roll if it is 5 or greater otherwise you continue and your expected payoff will be: \begin{equation} \frac{1}{6}(6+5) + \frac{2}{3}4.25 = 4+\frac{2}{3}. \end{equation}

$\endgroup$
0
$\begingroup$

Can someone explain to me why the expectation value of the outcome is not the same as the markov solution?

Imagine you were playing such that you cash out after 500 tries (instead of 2 or 3 treis). On your first roll, you roll a 4. Would you stop at the first roll because it's higher than 3.5? I think not. Your odds of getting a six are almost certain.

What is the expectation value of rolling a die twice, while only keeping the highest value? We can compute this as follows:

How many ways can I roll a 1? The answer is 1. 1 on my first roll. (1)

How many ways can I roll a 2? The answer is 2. Either on the first roll, (2) or on the second roll, assuming my first roll was a 1 (1,2).

How many ways can I roll a 3? The answer is 3. Either on the first roll (3) or on one of the second rolls, assuming my first roll was a 1,2 or 3 (1,3) (2,3).

And so on...

Therefore, there is only 1 outcome where I'd make \$1, two outcomes where I'd make \$2, 3 outcomes where I'd make \$3 dollars, up to 6 outcomes where I'd make \$6.

The total number of outcomes, then, is (1+2+3+4+5+6) = 21.

The expectation value is then:

$<E> = \$1 \frac{1}{21} + \$2\frac{2}{21} + \$3\frac{3}{21}$

$<E> = \frac{1}{21} \sum_{n=1}^{6} n^2$

$<E> = \$91/21 $

$<E> = \$4.3\bar{3}$

I guess I'm trying to answer the question "how much would you pay to play this game"? I'd pay up to $4.333.

The other solutions look more sophisticated, so maybe I'm blowing smoke.

$\endgroup$
  • $\begingroup$ Not really " blowing smoke " but computing a different method .seems with probability their are multiple methods that seem like a sound and logical answer and more or less a sequence of deductions that lead to an answer that seems 100% true , but then another method seems more accurate and thus the 100% ' correct ' or true . I find this alot in studying probability problems . $\endgroup$ – Randin Aug 12 '16 at 6:34
0
$\begingroup$

You have reframed the problem wherein you roll the dice simultaneously, and select the higher number.

The problem in question introduces the element of choice. You roll 1 dice. Then, you have the choice to reroll, but you must take the second result.

For instance, you could roll a 2, and elect to roll again, getting a 1. But, you must keep this result. In this case your result has worsened, despite the option of a second roll.

This is why your answer is different. It is addressing a fundamentally different question.

The Markov chain answer is the best, as it formally quantifies when you should elect to reroll. We know on a 6-sided dice when it makes sense to reroll. But when things get more complicated and this isn't immediately apparent, it's helpful to abstract that choice and find it arithmetically.

Best regards, Alex

$\endgroup$
0
$\begingroup$

The following table exhibits the optimal play after two throws:

Throw 1 Throw 2 Action Expectation


1 1 Throw 3.5 1 2 Throw 3.5 1 3 Throw 3.5 1 4 Stop 4 1 5 Stop 5 1 6 Stop 6 2 1 Throw 3.5 2 2 Throw 3.5 2 3 Throw 3.5 2 4 Stop 4 2 5 Stop 5 2 6 Stop 6 3 1 Throw 3.5 3 2 Throw 3.5 3 3 Throw 3.5 3 4 Stop 4 3 5 Stop 5 3 6 Stop 6 4 1 Throw 3.5 4 2 Throw 3.5 4 3 Throw 3.5 4 4 Stop 4 4 5 Stop 5 4 6 Stop 6 5 1 Throw 3.5 5 2 Throw 3.5 5 3 Throw 3.5 5 4 Stop 4 5 5 Stop 5 5 6 Stop 6 6 1 Throw 3.5 6 2 Throw 3.5 6 3 Throw 3.5 6 4 Stop 4 6 5 Stop 5 6 6 Stop 6

Optimal play after two throws has the same expectation regardless of the value of the first throw, namely 4.25. Therefore, it makes no sense to throw a second time if the first throw is greater than or equal to 4.25, i.e. if you throw a 5 or a 6 on the first throw. Similarly, it always makes sense to throw a second time if the first throw is less than 4.25, i.e. if it's a 1, 2, 3 or 4.

Throw 1 Action Expectation


1 Throw 4.25 2 Throw 4.25 3 Throw 4.25 4 Throw 4.25 5 Stop 5 6 Stop 6

Finally, we compute the expectation of the game:

1/6*4.25+1/6*4.25+1/6*4.25+1/6*4.25+1/6*5+1/6*6=14/3=4.666...

$\endgroup$
0
$\begingroup$

Start from the end.

What happens if you do not care about the first two rolls? The expected payoff is $(1+2+3+4+5+6)/6 = 3.5$. Now you have a freedom to go step earlier and make a decision about your strategy after the second roll (you still do not care about the first roll). We can actually find the optimal scenario which maximizes payoff: $$E[X] = \frac{n}{6}3.5 + \frac{1}{6}[6+5+ \ldots+(n+1)] = \frac{n}{6}3.5 + \frac{1}{6}\cdot\frac{7+n}{2}(6-n)$$ It has a maximum for $n=3$ and then $E[X] = 4.25$. The meaning of the above expression is that if we roll $1,2,\ldots , n$ then we should roll once again. Otherwise we stop.

Ok, we move to the first roll and apply the same idea, but with a new expectation value $4.25$: $$E[X] = \frac{n}{6}4.25 + \frac{1}{6}\cdot\frac{7+n}{2}(6-n)$$ Maximum is for $n=4$ and we get $E[X] = 4.6666...$.

In the problem the optimal strategy is the following:

  1. If you roll $1,2,3$ or $4$ in the first try, then reroll the dice. Otherwise take what you got, because on average you will not get more than $4.25$.
  2. In the second try. If you roll $1,2$ or $3$ you should roll once again. Otherwise stop, because on average you will not gain more than $3.5$.
$\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.