Impromptu gambling with dice

Suppose the die has $N$ sides. The key is to think about the problem recursively; the only thing that matters in determining the expected value is the number that was most recently rolled. Therefore, let’s define $f(n)$ to be the amount of money we expect to win if the last number we rolled was $n$. We’d like to solve for $f(1)$ since this is equivalent to the case where the game hasn’t started yet (any number subsequently rolled allows the game to continue). If we last rolled $n$, several cases emerge:

• If we roll $k \in \{1,2,\dots,n-1\}$ we win \$1 and the game stops immediately. This will occur with probability $\tfrac{n-1}{N}$.
• If we roll $k \in \{n,n+1,\dots,N\}$, we add \$1 to our winnings, and the game continues. We can expect to win an extra $f(k)$ as the game continues. Each number $k$ has an equal probability $\tfrac{1}{N}$ of being rolled.

Since each number $\{1,\dots,N\}$ has an equal chance to be rolled, we can write the following recursion for $f(n)$:
\[
f(n) = \frac{n-1}{N} + \frac{1}{N}\sum_{k=n}^N \left( 1+f(k)\right),\qquad n=1,2,\dots,N
\]Evaluating this for $n=N$, we obtain the relation
\[
f(N) = \frac{N-1}{N} + \frac{1}{N}\left( 1+f(N)\right)
\]Solving for $f(N)$, we obtain $f(N)=\tfrac{N}{N-1}$. This is our terminal condition: the expected winnings if we just rolled the highest possible number.

Now rewrite the original recursion for both $n+1$ and $n$ and subtract one equation from the other, we obtain:
\[
f(n+1)-f(n) = \frac{1}{N}-\frac{f(n)+1}{N}, \qquad n = 1,2,\dots,N-1
\]Rearranging, we obtain the simple recursion:
\[
f(n) = \left(\frac{N}{N-1}\right)f(n+1), \qquad n = 1,2,\dots,N-1
\]Since $N$ is a constant, we can recursively evaluate this and obtain:
\[
f(1) = \left(\frac{N}{N-1}\right)^{N-1} f(N)
\]Substituting the $f(N)$ we found earlier, we obtain our final answer:

$\displaystyle
f(1) = \left(\frac{N}{N-1}\right)^{N}
$

Note that $f(1)$ is undefined if $N=1$. This makes sense; if there is only one side to the die, you’ll always roll the same thing and so the game never ends! Here is a plot of how the expected winnings change as a function of $N$:

With a 100-sided die, we get an expected prize of $\left(\tfrac{100}{99}\right)^{100} \approx 2.7320$. As the number of sides increases, the expected prize decreases, but tends to a finite limit (the red line shown in the plot). In the limit $N\to\infty$, we have $f(1) \to e \approx 2.7183$.

Computing the distribution

Let’s calculate the probability $p(N,k)$ that the game with an $N$-sided die lasts $k$ rounds. We can do this by counting carefully:
\begin{align}
p(N,k) &= \frac{\text{#seq. of len. }k\text{ from }\{1,\dots,N\}\text{, first decrease occurs at end}}{\text{#sequences of length }k\text{ from }\{1,\dots,N\}}
\end{align}The denominator is simply $N^k$. The numerator is a bit trickier, and we can argue as follows. Let’s define $S(N,k)$ be the number of nondecreasing sequences of length $k$ from $\{1,\dots,N\}$. Then:
\begin{align}
&\text{#seq. of len. }k\text{ from }\{1,\dots,N\}\text{, first decrease occurs at end}\\
& \qquad = (\text{#seq. of len. }k\text{, first }k-1\text{ is nondecreasing})\\
&\qquad\qquad\qquad-(\text{#seq. of len. }k\text{, entirely nondecreasing})\\
& \qquad = N S(N,k-1)-S(N,k)
\end{align}So how do we count nondecreasing sequences? To calculate $S(N,k)$, imagine we have $a_1$ 1’s, $a_2$ 2’s, and so on up to $a_N$ $N$’s. Since the sequence is nondecreasing, these must occur in order. So we’re effectively looking for the number of ways of choosing $a_i \ge 0$ for $i=1,\dots,N$ such that $a_1+\dots+a_N = k$. We can do this via the stars and bars method.

The reasoning is as follows. Suppose we wanted to count the solutions to $a_1+a_2+a_3+a_4 = 5$ where each $a_i \ge 0$. Now imagine an arrangement of 5 stars and 3 bars, such as ★|★★★||★. Each star is “1” and the bars are separators. This arrangement represents the solution $1 + 3 + 0 + 1 = 5$. So the total number of ways of splitting 5 stars into 4 groups is the same as the number of ways of arranging 5 stars and 3 bars. Equivalently, it’s the number of ways of picking, out of 8 slots, which 3 will have bars (or stars) in them, so ${8 \choose 3} = 56$.

Therefore, we conclude that $S(N,k) = {N+k-1 \choose k}$. Substituting into our previous expression, we obtain after a bit of algebra:
\begin{align}
p(N,k) &= \frac{1}{N^k} \left( N S(N,k-1)-S(N,k) \right) \\
&= \frac{1}{N^k} \left( N{N+k-2 \choose k-1}-{N+k-1 \choose k}\right)\\
%&= \frac{1}{N^k} \left( \frac{(N+k-2)!N}{(k-1)!(N-1)!}-\frac{(N+k-1)!}{k!(N-1)!}\right)\\
%&= \frac{1}{N^k} \frac{(N+k-2)!}{(k-1)!(N-1)!}\left( N-\frac{N+k-1}{k} \right) \\
%&= \frac{1}{N^k} \frac{(N+k-2)!}{(k-1)!(N-1)!}\frac{(N-1)(k-1)}{k} \\
%&= \frac{1}{N^k} \frac{(N+k-2)!}{k!(N-2)!}(k-1) \\
&= \frac{k-1}{N^k} {N+k-2\choose k}
\end{align}So we conclude that:

$\displaystyle
p(N,k) = \frac{k-1}{N^k} {N+k-2\choose k}
$

As a sanity check, we can verify that $p(N,k)$ is a legitimate probability mass function for each $N$. In other words, the sum over $k$ is equal to $1$. We can check this using a neat telescoping sum argument:
\begin{align}
\sum_{k=2}^{\infty} p(N,k)
&= \sum_{k=2}^{\infty}\frac{ N S(N,k-1)-S(N,k) }{N^k}\\
&= \sum_{k=2}^{\infty}\left(\frac{S(N,k-1)}{N^{k-1}}-\frac{S(N,k)}{N^k}\right)\\
&= \frac{S(N,1)}{N}\\
&=1
\end{align}What we were after all along was the expected value, so we can compute this directly as well:
\begin{align}
\sum_{k=2}^{\infty} k\, p(N,k)
&= \sum_{k=2}^{\infty}k\frac{ N S(N,k-1)-S(N,k) }{N^k}\\
&= \sum_{k=2}^{\infty}\left[ \left(\frac{(k-1)S(N,k-1)}{N^{k-1}}-\frac{kS(N,k)}{N^k}\right) + \frac{S(N,k-1)}{N^{k-1}} \right]\\
&= \frac{S(N,1)}{N} + \sum_{k=1}^{\infty} \frac{S(N,k)}{N^{k}} \\
&= \sum_{k=0}^{\infty} \frac{1}{N^{k}} {N+k-1 \choose k}
\end{align}This final sum is an example of a binomial series. In general, we have:
\[
(1-z)^{-N} = \sum_{k=0}^{\infty} {N+k-1 \choose k} z^k\qquad\text{for all }|z|<1 \]If we let $z=\frac{1}{N}$, we recover the solution we derived in the first part for the expected winnings in the game.

Limiting distribution

To calculate the distribution as $N\to\infty$, we can make use of Stirling’s approximation, which says that $n! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$ as $n\to \infty$.
\begin{align}
\lim_{N\to\infty} \frac{k-1}{N^k} {N+k-2\choose k}
&= \lim_{N\to\infty} \frac{k-1}{N^k} \frac{(N+k-2)!}{k!(N-2)!} \\
&= \lim_{N\to\infty} \frac{k-1}{k!} e^{-k} \frac{(N+k-2)^{N+k-2}}{N^k (N-2)^{N-2}} \\
&= \lim_{N\to\infty} \frac{k-1}{k!} e^{-k} \left( \frac{N+k-2}{N} \right)^k \left( \frac{N+k-2}{N-2} \right)^{N-2}\\
&= \lim_{N\to\infty} \frac{k-1}{k!} e^{-k} \left( \frac{N+k-2}{N-2} \right)^{N-2}\\
&= \frac{k-1}{k!}
\end{align}So the limiting distribution as $N\to\infty$ is given by:

$\displaystyle
p(\infty,k) = \frac{k-1}{k!}
$

Again, as a sanity check, $p(\infty,2) = \frac{1}{2}$. This makes sense because if your die has a large number of sides, your second number will be smaller than your first about half the time. Here is an animation of how the distribution changes as we add more sides to the die.

It was brought to my attention that there is already a nice write-up for this problem in this article. However, it’s behind a paywall. Here is an earlier draft of that same article that if freely available. If you’d like to see another solution method, I encourage you to check it out! Of note, the alternate solution also treats the case where the dice rolls are real numbers in $[0,1]$. This case is in fact equivalent to the case of having an $N$-sided die with $N\to\infty$.