# The probability of winning a peculiar dice game

I'm a high school teacher, and students in my probability class created the following fun conundrum. We've been stuck on it for a couple of weeks:

• Consider this dice game played with one fair $$n$$-sided dice.
• On the first turn, a roll of $$n$$ wins, while a roll of $$1$$ loses. On any other result, the player rolls again.
• On the 2nd roll, a roll of $$n$$ wins, while a roll of $$1$$ or $$2$$ loses. On any other roll, the game continues.
• On roll $$k$$, the player wins with a roll of $$n$$ and loses with a roll of $$k$$ or below.
• What is the probability of winning as $$n \to \infty$$ ?.

The game must be won in no more than $$n - 1$$ turns, and for any given $$n$$ , $$\mathrm{P}\left(win\right) = {1 \over n} + \sum_{i = 2}^{n - 1}\frac{\left(n - 2\right)!}{\left(n - i - 1\right)!\, n^{i}}$$

Here is where I'm stuck. Does: $$\lim_{n \to \infty}\mathrm{P}\left(win\right) = 0?$$ or does $$\mathrm{P}\left(win\right)$$ converge on some other nonzero probability as $$n \to \infty$$ ?. How might one show this ?.

• I think $P(win) \lt \dfrac{1}{\sqrt{n}}$. If so, it does tend to $0$ but fairly slowly – Henry Jun 13 '19 at 17:01
• @InterstellarProbe - You are probably right, though TravisJ suggests it is not far away – Henry Jun 13 '19 at 20:30
• @Henry - Guided by your guess and TravisJ's simulations, I was above to prove $2 / \sqrt{n}$ (see my answer). But how did you come up with the $1 / \sqrt{n}$ guess in the first place? I probably would not have succeeded without your inspired guess. – antkam Jun 13 '19 at 21:13
• @antkam - I tried to calculate some values and spot the pattern - apparently not well enough – Henry Jun 13 '19 at 21:40
• @antkam - trying again, I think $P(win) \times n^{n-1}$ may be OEIS A001863 and $P(win) \times (n-1)n^{n-1}$ may be OEIS A000435; the second of these is special as it started the OEIS – Henry Jun 13 '19 at 23:34

I cannot prove that $$P(win) \approx {1 \over \sqrt{n}}$$, but here is a proof that:

Claim: $$P(win) \le {2 \over \sqrt{n}}$$

which of course implies $$P(win) \to 0$$, answering the OP question.

Proof: For convenience, let $$G =$$ the OP's original game. Consider some large, fixed $$n$$. Define:

• event $$A =$$ win $$G$$ on or before $$\sqrt{n}$$ turns

• event $$B =$$ win $$G$$ after $$\sqrt{n}$$ turns

We will separately bound $$P(A), P(B)$$ both $$\le {1 \over \sqrt{n}}$$. The main claim then follows because $$P(win) = P(A)+P(B)$$.

Lemma: $$P(A) \le {1\over \sqrt{n}}$$: Imagine a modified game $$G'$$ where the die is always rolled for all $$n$$ rounds, and the game result is the first winning or losing roll. This modified game $$G'$$ is clearly equivalent to the OP's truncated version $$G$$.

Let random variable $$X=$$ no. of winning rolls among the initial $$\sqrt{n}$$ rounds of $$G'$$. To win on or before $$\sqrt{n}$$ rounds, it is necessary (though not sufficient) that $$X\ge 1$$, i.e. $$P(A) \le P(X\ge 1)$$. Meanwhile, for any non-negative integer r.v.s, we have:

$$P(X\ge 1) = \sum_{k=1}^\infty P(X=k) \le \sum_{k=1}^\infty kP(X=k) = E[X]$$

In this case, by linearity, $$E[X] = {1\over n} \sqrt{n} = {1 \over \sqrt{n}}.$$ Combining, we have:

$$P(A) \le P(X\ge 1) \le E[X] = {1 \over \sqrt{n}} \;\;\; \square$$

Lemma: $$P(B) \le {1 \over \sqrt{n}}$$: First, define:

• event $$E=$$ game $$G$$ is inconclusive (neither won nor lost) after $$\sqrt{n}$$ rounds

Note that event $$B$$ requires event $$E$$, i.e. $$P(B) = P(B \cap E) = P(E) P(B \mid E)$$.

Now imagine two different modified games. In $$G_1$$, the game starts with $$1$$ to $$\sqrt{n}$$ as the losing numbers and adds one more losing number every round. By construction, $$P(\text{win }G_1) = P(B \mid E)$$.

In $$G_2$$, the game starts with $$1$$ to $$\sqrt{n}$$ as the losing numbers and the set of losing numbers doesn't change for the rest of the game. Clearly, $$G_2$$ is easier to win than $$G_1$$ (e.g. via a sample-point by sample-point dominance argument).

The modified game $$G_2$$ is not limited to $$n$$ rounds, but it does terminate with probability $$1$$. Therefore, the ratio:

$${P(\text{win }G_2) \over P(\text{lose }G_2)} = {P(\text{win }G_2 \mid G_2 \text{ terminates}) \over P(\text{lose }G_2 \mid G_2 \text{ terminates})} = {\text{no. of winning rolls} \over \text{no. of losing rolls}} = {1 \over \sqrt{n}}$$

The easiest proof of the above is to consider $$G_2$$ as a $$3$$-state Markov chain with $$2$$ absorbing states, for win and loss. Alternately one can consider there to be $$1+\sqrt{n}$$ terminating states, by symmetry all equally likely, and then color exactly $$1$$ of them as "winning" and the others as "losing".

Combining everything, we have:

$$P(B) = P(E) P(B \mid E) \le P(B \mid E) = P(\text{win }G_1) \le P(\text{win }G_2) = {1 \over 1 + \sqrt{n}} < {1 \over \sqrt{n}} \;\;\; \square$$

This isn't a complete answer, but it suggests @Henry is approximately correct with the $$P(win) \approx \frac{1}{\sqrt{n}}$$.

If $$p(n, k)$$ is the probability of winning when $$k$$ is the largest "losing" value then

$$p(n,k) = \frac{1}{n} + \left(1 - \frac{k+1}{n}\right)p(n, k+1)$$

Using this easy recurrence it's straightforward to compute many values. I plotted the first 1000 values of $$p(n,1)$$ along with $$\frac{1}{\sqrt{n}}$$. They follow pretty closely (albeit not identical): Using python, I hit max recursion depth at around $$n=2750$$. At that point $$p(2750,1)=0.02342415256724741$$ and $$\frac{1}{\sqrt{2750}}\approx 0.019069251784911846$$.