The expected payoff of a dice game

Solution 1:

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?

Solution 2:

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.

Solution 3:

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}

Solution 4:

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

Solution 5:

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