Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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?
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.
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.
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}
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:
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
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...
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.
