On The Game Masters Of Triskelion

| 0 Comments

The Baron's last game pitted Sir R----- against him in a duel of dice. At each turn the Baron would add a token to a pile, initially containing four tokens, and he would roll a six sided die and Sir R----- would roll a four sided die. If Sir R-----'s roll equalled or exceeded the Baron's he could remove two tokens from the pile. The game cost Sir R----- a single coin to play and should he have ever exhausted the tokens would have won four coins from the Baron.
Now each turn will end with either one token more or one less in the pile. Referring to the Baron's die as \(\mathrm{d}6\) and Sir R-----'s as \(\mathrm{d}4\), the probability of the former is given by
\[ \begin{align*} p &= \Pr(\mathrm{d}6 = 6) + \Pr(\mathrm{d}6 = 5) + \Pr(\mathrm{d}6 = 4 \; \mathrm{and} \; \mathrm{d}4 < 4)\\ &+ \Pr(\mathrm{d}6 = 3 \; \mathrm{and} \; \mathrm{d}4 < 3) + \Pr(\mathrm{d}6 = 2 \; \mathrm{and} \; \mathrm{d}4 < 2)\\ &= \tfrac{1}{6} + \tfrac{1}{6} + \tfrac{1}{6} \times \tfrac{3}{4} + \tfrac{1}{6} \times \tfrac{2}{4} + \tfrac{1}{6} \times \tfrac{1}{4}\\ &= \tfrac{4}{24} + \tfrac{4}{24} + \tfrac{3}{24} + \tfrac{2}{24} + \tfrac{1}{24}\\ &= \tfrac{14}{24}\\ &= \tfrac{7}{12} \end{align*} \]
This is a classic problem in the theory of wager known as the gambler's ruin problem; what is the probability that a gambler starting with \(n\) coins will be ruined in a game in which he wins one coin with probability \(p\) and loses one coin with probability \(1-p\) at each turn. This can be modelled as a random walk with an absorbing barrier at zero; that is to say a walk along the integers in which steps are taken up or down at random and which stops if it ever reaches zero. Indeed, I explained as much to the Baron, but I fear that he may not have entirely understood.

Figuring the probability of ruin is made somewhat tricky by the fact that it is possible for a step away from zero to be followed by a step toward it, or for a step toward zero to be followed by a step away from it, so that the probability that zero is reached from any given value depends upon both the probability that it is reached from the value above it and the probability that it is reached from the value below it. These in turn depend upon the probabilities from their neighbours, one of which is that given value, and so on and so forth ad infinitum.
We can, however, easily deduce a formula that the probability of ruin starting from \(n\) coins, \(p_n\), must satisfy. Specifically, it must equal the sum of \(p\) times the probability of ruin starting from one more coin and \(1-p\) times the probability starting from one less coin
\[ p_n = p \times p_{n+1} + (1-p) \times p_{n-1} \]
A trivial solution to this is \(p_n=1\), as can be shown with
\[ 1 = p \times 1 + (1-p) \times 1 = p + 1 - p = 1 \]
To find another we should note that the probabilities \(p\) and \(1-p\) accumulate multiplicatively and we should likely want the former to cancel out a term and the latter to reinforce one. A reasonable first guess is therefore
\[ p_n = \frac{(1-p)^n}{p^n} \]
Substituting this back into our formula yields
\[ \begin{align*} \frac{(1-p)^n}{p^n} &= p \times \frac{(1-p)^{n+1}}{p^{n+1}} + (1-p) \times \frac{(1-p)^{n-1}}{p^{n-1}}\\ &= \frac{(1-p)^{n+1}}{p^n} + \frac{(1-p)^n}{p^{n-1}}\\ &= (1-p) \times \frac{(1-p)^n}{p^n} + p \times \frac{(1-p)^n}{p^n}\\ &= (1-p+p) \times \frac{(1-p)^n}{p^n}\\ &= \frac{(1-p)^n}{p^n} \end{align*} \]
and so, as luck would have it, our first guess is another solution.

We have two known cases, being that in which the gambler is already ruined and that in which he never is
\[ \begin{align*} p_0 &= 1\\ p_\infty &= 0 \end{align*} \]
so these two solutions can be combined into a general solution that can match them
\[ p_n = a \times 1 + b \times \left(\frac{1-p}{p}\right)^n \]
which, provided that
\[ \begin{align*} \left(\frac{1-p}{p}\right)^\infty &= 0\\ \frac{1-p}{p} &< 1\\ 1-p &< p\\ p &> \tfrac{1}{2} \end{align*} \]
as is the case in the Baron's wager, is done with \(a=0\) and \(b=1\)
\[ \begin{align*} p_n &= \left(\frac{1-p}{p}\right)^n\\ p_0 &= \left(\frac{1-p}{p}\right)^0 = 1\\ p_\infty &= \left(\frac{1-p}{p}\right)^\infty = 0 \end{align*} \]
That this solution is unique can be proven by first assuming that it is not; that there is another solution \(p_n^\prime\). We can fit our solution to any two known cases, so let us choose \(p_0^\prime\) and \(p_1^\prime\)
\[ \begin{align*} p_0 &= p_0^\prime\\ p_1 &= p_1^\prime \end{align*} \]
Rearranging our original formula yields
\[ p_{n+1} = \frac{1}{p} \times p_n - \frac{(1-p)}{p} \times p_{n-1} \]
and so if the two solutions agree for the first two cases, they must agree for every case and are consequently the same solution after all!

Finally, putting the Baron's probability of coming out ahead at the end of a turn into our solution yields a probability that a pile of \(n\) tokens will ultimately be exhausted of
\[ p_n = \left(\frac{1-\frac{7}{12}}{\frac{7}{12}}\right)^n = \left(\frac{\frac{5}{12}}{\frac{7}{12}}\right)^n = \left(\frac{5}{7}\right)^n \]
For \(n=4\) this equates to
\[ p_4 = \left(\frac{5}{7}\right)^4 = \left(\left(\frac{5}{7}\right)^2\right)^2 = \left(\frac{25}{49}\right)^2 > \left(\frac{1}{2}\right)^2 = \frac{1}{4} \]
and so Sir R-----'s profit should be
\[ 4 \times p_4 -1 > 4 \times \frac{1}{4} - 1 = 0 \]
and I should therefore have had no compunction whatsoever in advising him to take up the Baron's wager!
\(\Box\)

Leave a comment

 
This site requires HTML5, CSS 2.1 and JavaScript 5 and has been tested with

Chrome Chrome 26+
Firefox Firefox 20+
Internet Explorer Internet Explorer 9+