This Riddler puzzle is an impromptu gambling game about rolling dice.
You and I stumble across a 100-sided die in our local game shop. We know we need to have this die — there is no question about it — but we’re not quite sure what to do with it. So we devise a simple game: We keep rolling our new purchase until one roll shows a number smaller than the one before. Suppose I give you a dollar every time you roll. How much money do you expect to win?
Extra credit: What happens to the amount of money as the number of sides increases?
Here is my solution:
[Show Solution]
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$.
For a more in-depth analysis of the distribution, read on:
[Show Solution]
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$.
Nice once again! I eventually found the same thing after some bumbling that led me to notice the empirical similarity between this game and one that seems rather different: (N/1-N)^N is also 1/(1-1/N)^N, which is one over the chance of getting zero successes in N trials of an experiment with individual probabilities 1/N of success (such as 100 rolls of this Riddler’s die without side 100 coming up), and so is the expected number of runs of N trials before a no-succesess one. I wonder if there’s some clever way of thinking about the Riddler game that assimilates it to that one (or maybe it’s just that, like e, the binomial distribution tends to show up).
Second, you can also show quickly that the limit is e by considering the continuous case of a die with real values in [0,1]. The expected value of a non-game-ending roll #(r-1), is (r-1)/r, which is therefore the probability of the game ending on roll #r (if it hasn’t by then), and the probability of the game *not* ending them is 1/r. The probability (from the start) of the game ending on roll #r, then, is the sum, for r from 1 to r-1, of r/r!, and the limit of that sum is e.
thanks! I made note of the connection between the [0,1] case and the infinite-N case at the end of my post. I found it a lot more intuitive to think about random real numbers in a closed interval rather than infinite integers.
Great post! I’ve been reading your blog for a few months now and am always impressed by your solutions. One minor typo, when you subtract the two equations, it should be:
f(n+1) – f(n) = 1/N – (f(n)+1)/N
Thanks for sharing your solutions!
thanks! fixed the typo.
I’m sorry; I’m having a fundamental problem with this calculation, and his to do with, what seems to me, the way you’ve established your initial formula — which assumes that N=1 is undefined and thus doesn’t include a calculation for it.
Empirically speaking, there is a universe where you roll 100, over and over again, infinitely. Which would be the situation if N = 1, but even if N = 100, there’s a nonzero possibility of landing on 100 endlessly, forever, until the heat death of the universe. While the probability of that occurring is extremely low, any non-zero probability of an infinite amount is, by definition, infinite. So your expected value in this particular game would be infinity dollars.
To put it another way: If you’re using a 2-sided die, then you have a traditional St. Petersburg lottery. Using a 100-sided die just gives you a special iteration of a St. Peterburg lottery.
We can both agree that the situation $N=1$ leads to infinite expected winnings, since the game is deterministic; the same things is rolled every turn so the game never ends.
You’re right that for $N > 1$ the game can in principle last forever, albeit with a vanishingly small probability. However, this is different from the St. Petersburg Paradox in that the expected value is not infinite. In the paradox, you flip coins and keep playing as long as you keep getting Heads and you win $2^n$ where $n$ is the number of flips it took to get your first Tails. The probability of having longer and longer games shrinks exponentially but the amount you can win grows exponentially. The result is that the total expected winnings for the game is infinite:
\[
\frac{2^1}{2^1} + \frac{2^2}{2^2} + \cdots = 1 + 1 + \cdots = \infty
\]This is not the case in the dice problem. The probability of having longer and longer games does shrink exponentially, but the amount you can win only increases linearly. The result is a finite expected value. The analogy would be if the St. Petersburg game only awarded you $n$ dollars for a game that lasts $n$ turns. In that case, your expected winnings would be:
\[
\frac{1}{2} + \frac{2}{2^2} + \frac{3}{2^3} + \cdots
= \sum_{k=1}^\infty \frac{k}{2^k}
\]It turns out this sum equals $2$. This can be shown in several different ways. The calculation for the actual dice problem is a bit more complicated than this but the basic idea is the same.
That makes sense; thank you so much!