Roll as many dice as the die has sides

CS61A describes the rules as

In Hog, two players alternate turns trying to be the first to end a turn with at least 100 total points. On each turn, the current player chooses some number of dice to roll, up to 10. That player’s score for the turn is the sum of the dice outcomes. However, a player who rolls too many dice risks:

Sow Sad. If any of the dice outcomes is a 1, the current player’s score for the turn is 1.

In this paper, we show that for an $n$-sided die, the expected value is maximized by rolling $n$ dice for every natural number $n \geq 2$. Therefore, when there is no limit to the number of dice that can be rolled, the optimal choice for an $n$-sided die is to roll $n$ dice.

Derive the expected turn score

For one six-sided die, $$P(1)=\frac{1}{6}, \quad P(\neg 1)=\frac{5}{6}$$ And the total expectation is $$\text{E}(X) = \frac{1}{6} (1) + \frac{1}{6} (2 + 3 + 4 + 5 + 6)$$ Grouping the five outcomes that are not $1$, $$\text{E}(X) = \frac{1}{6} (1) + \frac{5}{6}(4) = 3.5$$ where $4$ is the average of the outcomes $2$ through $6$.

We now generalize this idea to rolling $m$ dice, each with $n$ sides. With multiple dice, Sow Sad occurs if at least one of the $m$ dice rolls a $1$.

Then since the dice are independent, the probabilities become $$P(\text{no 1s}) = \left( \frac{n-1}{n} \right)^m$$ and $$P(\text{at least one 1}) = 1 - \left( \frac{n-1}{n} \right)^m$$

From the law of total expectation, if a set of events is mutually exclusive and covers every outcome, then the expected value is the sum of the expected value given each event $A_i$ multiplied by the probability of that event. $$\text{E}(X) = \sum_i P(A_{i}) \cdot \text{E}(X \mid A_{i})$$ Sow Sad and its complement are two such events, so $$\begin{aligned} \text{E}(X) &= P(\text{at least one 1}) \, \text{E}(X \mid \text{at least one 1}) \\ &\quad + P(\text{no 1s}) \, \text{E}(X \mid \text{no 1s}) \end{aligned}$$ Then since Sow Sad gives you 1 point, $$\text{E}(X \mid \text{at least one 1}) = 1$$ Therefore, $$\text{E}(X) = \left[ 1 - \left( \frac{n-1}{n} \right)^m \right](1) + \left( \frac{n-1}{n} \right)^m \text{E}(X \mid \text{no 1s}) \tag{1}$$

To compute $\text{E}(X \mid \text{no 1s})$, we start by thinking in terms of a single die.

Let $Y$ be the outcome of rolling $1$ die given that it is not a $1$, so $Y$ is equally likely to be any of $2$ through $n$. On a six-sided die, there are $6-1=5$ ways to roll between a $2$ and $6$, hence $P(Y=i)=\frac{1}{6-1}$. To generalize to the probability of rolling an $n$-sided die from $2$ to $n$, we use $P(Y=i) = \frac{1}{n-1}$. The expected value of this is then $$\begin{aligned} \text{E}(Y) &= \sum_{i=2}^{n} i \left( \frac{1}{n-1} \right) \\ &= \frac{2 + 3 + \dots + n}{n-1} \end{aligned}$$ To calculate the sum of the first $n$ positive integers, we use $\frac{n(n+1)}{2}$. And since we exclude the outcome $1$, we subtract it from that sum and get $$\begin{aligned} \text{E}(Y) &= \frac{\frac{n(n+1)}{2} - 1}{n-1} \\ &= \frac{n(n+1) - 2}{2(n-1)} \\ &= \frac{(n-1)(n+2)}{2(n-1)} \\ &= \frac{n}{2}+1 \end{aligned}$$ Then note that conditioned on no 1s, each of the $m$ dice is an independent copy of $Y$, so the distribution $(X \mid \text{no 1s})$ is the same as the “sum” (convolution) of rolling $m$ of the $Y$ dice: $(X \mid \text{no 1s})=\underbrace{Y_1+Y_2+\cdots+Y_m}_{m \text{ times}}$. We can then use the linearity of expectation: $$\text{E}(X \mid \text{no 1s})=\text{E}(\underbrace{Y_1+Y_2+\cdots+Y_m}_{m \text{ times}})=m \cdot \text{E}(Y)=m \cdot \left(\frac{n}{2}+1\right)$$ Plugging into equation (1), the expected value is $$\begin{aligned} \text{E}(X) &= \left[ 1 - \left( \frac{n-1}{n} \right)^m \right](1) + \left( \frac{n-1}{n} \right)^m m \left( \frac{n}{2} + 1 \right) \\ &= 1 + \left( \frac{n-1}{n} \right)^m \left( \frac{m(n+2)}{2} - 1 \right) \end{aligned} \tag{2}$$ We write $\text{E}(m,n)$ when we want to make the dependence on $m$ and $n$ explicit.

Prove the maximum is at $m=n$

For a fixed number of sides, the line in Figure 1 goes up and then down. We want to determine where the greatest expectation is.

We define $\Delta = \text{E}(m+1, n) - \text{E}(m, n)$, or the difference in expectation between rolling $m+1$ dice and rolling $m$ dice.

Substituting equation (2) into this definition and simplifying, we have $$\Delta = \left( \frac{n-1}{n} \right)^m \frac{n(n+1)-m(n+2)}{2n}$$ Since $\left( \frac{n-1}{n} \right)^m$ and $2n$ are always positive, the sign of $\Delta$ depends only on $$n(n+1) - m(n+2)$$

When $\Delta > 0$, the expectation is increasing on the graph and $\text{E}(m, n) < \text{E}(m+1, n)$. Therefore $\Delta > 0$ exactly when $$\underbrace{m}_{\text{integer}} < \frac{n(n+1)}{n+2} = \underbrace{n-1}_{\text{integer}} + \underbrace{\frac{2}{n+2}}_{\text{fractional}}$$

Since $\frac{2}{n+2}$ is fractional, $$0 < \frac{2}{n+2} < 1 \qquad \text{for } n \geq 2$$ and adding $n-1$ to all sides, $$n-1 < n-1 + \frac{2}{n+2} < n$$

Since $n-1$ and $n$ are integers, $\frac{2}{n+2}$ is a fraction, and $m < n-1 + \frac{2}{n+2}$, we have $$m \leq n-1 \iff \Delta > 0$$

To illustrate this, imagine a number line with $m$ on the left and $n-1 + \frac{2}{n+2}$ (integer plus a fraction) on the right. Since $m$ is the integer right before $n-1+ \frac{2}{n+2}$, $m$ must be less than or equal to the integer $n-1$.

Since $n-1 + \frac{2}{n+2}$ is never an integer, $\Delta$ is never exactly $0$. Similarly, by negating terms of the biconditional (and that $m,n$ are integers), $$\Delta < 0 \iff m \geq n$$

Since $\Delta$ represents the change from $m$ to $m+1$, these statements mean $\text{E}(m,n)$ is increasing until $m=n$, and then exactly at $m=n$, we have $\text{E}(m=n,n)>\text{E}(m=n+1,n)$, hence all values $\text{E}(m>n,n)$ are less than $\text{E}(m=n,n)$, and this means $n$ is optimal.

For intuition, on the expectation graph, one can imagine expectation increasing when $\Delta > 0$ and expectation decreasing when $\Delta < 0$. The maximum is the turning point when $m$ switches from being less than or equal to $n-1$ to being greater than or equal to $n$, which implies $n$ is optimal.