EV of a strictly increasing sequence of n-sided dice rolls

Question

You roll a fair, $n$-sided die. If its value is higher than that of your previous roll (or this is your first roll), you add it to your score and roll again. If not, you keep any banked points and your turn is over. I'd like to know the expected score for each turn.

Example playthrough with a D20:

Rolls: 7, 12, 16, 13 (turn ends)

Score: $7 + 12 + 16 = 35$

This process was inspired by the ball flight mechanic from the dice game Roll In One.

Simulating this in Python yields the surprising (to me, at least) conclusion that the expected score is $n$. Looking forward to any insights you have to offer!

Answer 1

Let $I_k$ be the indicator that all faces rolled prior to the first roll of $k$ are an increasing sequence of faces less than $k$.

The expected score is $\sum_{k=1}^n k~\mathsf E(I_k)$ , where $\mathsf E(I_k)$ is the probability that face $k$ is scored.

Let $[1,2,5]$ represent an array of rolls of faces 1, 2, and 5 in that order, and so forth.

$$\begin{align}\mathsf E(I_1)&=\mathsf P([1])\\&=\dfrac{1}{n}\\\mathsf E(I_2) &=\mathsf P([2]\cup[1,2])\qquad\text{ie: roll 2 on the first roll, or 1 then 2.} \\&= \dfrac 1n+\dfrac{1}{n^2}\\\mathsf E(I_3]&=\mathsf P([3]\cup[2,3]\cup[1, 3]\cup[1,2,3]) \\&=\dfrac 1n+\dfrac 2{n^2}+\dfrac{1}{n^3}\\\mathsf E(I_4) &=\mathsf P([4]\cup[1,4]\cup[2,4]\cup[3,4]\cup[1,2,4]\cup[1,3,4]\cup[2,3,4]\cup[1,2,3,4])\\&=n^{-1}+3n^{-2}+3n^{-3}+ n^{-4}\\&=n^{-4}(n+1)^3\\\vdots& \qquad\text{a pattern based on selecting subsets of the numbers less than }k\\\vdots&\qquad\text{oh, and the Binomial Expansion Theorem gives us that closed form}\\\mathsf E(I_k) &= \sum_{j=1}^{k}\dbinom{k-1}{j-1}n^{-j}\\&=n^{-k}(n+1)^{k-1} \end{align}$$

So the expected score is $$(n+1)^{-1}\sum_{k=1}^n k (n^{-1}(n+1))^{k} = n$$

...

Using the identity $\displaystyle\sum_{k=1}^n k r^{k} = \dfrac{r (n r^{n + 1} - (n + 1) r^n + 1)}{(r - 1)^2}$

Answer 2

For integers $0\le s\le n$ let $E(n,s)$ be the expected score of a game played with an $n$-sided die (sides numbered from $1$ to $n$) which is the same as your game except that the first roll must be greater than $s$ (or else the game ends with a score of zero).

Claim. $E(n,n-r)=r$ for $0\le r\le n$. (In particular $E(n,0)=n$, which answers your question.)

The proof is by induction on $r$. It's clearly true for $r=0$ and $r=1$. In general, $$E(n,n-r)=\sum_{k=0}^{r-1}\frac{n-k+E(n,n-k)}n=\sum_{k=0}^{r-1}\frac{n-k+k}n=\sum_{k=0}^{r-1}1=r.$$