On The Rich Get Richer

| 0 Comments

The Baron's latest wager set Sir R----- the task of surpassing his score before he reached eight points as they each cast an eight sided die, each adding one point to their score should the roll of their die be less than or equal to it. The cost to play for Sir R------ was one coin and he should have had a prize of five coins had he succeeded.

A key observation when figuring the fairness of this wager is that if both Sir R----- and the Baron cast greater than their present score then the state of play remains unchanged. We may therefore ignore such outcomes, provided that we adjust the probabilities of those that we have not to reflect the fact that we have done so.
Specifically, if we label Sir R-----'s and the Baron's scores as \(r\) and \(b\) respectively then we might represent the state of play before the \(n^\mathrm{th}\) change in either of them as the ordered pair
\[ S_n = \{r, b\} \]
and so the probabilities of the possible states after a change should consequently be
\[ \begin{align*} \Pr\left(S_{n+1} = \{r+1, b\} | S_n = \{r, b\}\right) &= \frac{\Pr\left(d_r \leqslant r\right) \wedge \Pr\left(d_b > b\right)}{1 - \Pr\left(d_r > r \wedge d_b > b\right)}\\ \Pr\left(S_{n+1} = \{r, b+1\} | S_n = \{r, b\}\right) &= \frac{\Pr\left(d_r > r\right) \wedge \Pr\left(d_b \leqslant b\right)}{1 - \Pr\left(d_r > r \wedge d_b > b\right)}\\ \Pr\left(S_{n+1} = \{r+1, b+1\} | S_n = \{r, b\}\right) &= \frac{\Pr\left(d_r \leqslant r\right) \wedge \Pr\left(d_b \leqslant b\right)}{1 - \Pr\left(d_r > r \wedge d_b > b\right)} \end{align*} \]
where \(\Pr(E|C)\) is the probability that an event \(E\) might occur given a condition \(C\), \(d_r\) represents the outcome of Sir R-----'s roll, \(d_b\) that of the Baron's, and \(\wedge\) means and. These resolve to
\[ \begin{align*} \Pr\left(S_{n+1} = \{r+1, b\} | S_n = \{r, b\}\right) &= \frac{\frac{r}{8} \times \frac{8-b}{8}}{1 - \frac{8-r}{8} \times \frac{8-b}{8}} = \frac{8 \times r - r \times b}{8 \times r + 8 \times b - r \times b}\\ \Pr\left(S_{n+1} = \{r, b+1\} | S_n = \{r, b\}\right) &= \frac{\frac{8-r}{8} \times \frac{b}{8}}{1 - \frac{8-r}{8} \times \frac{8-b}{8}} = \frac{8 \times b - r \times b}{8 \times r + 8 \times b - r \times b}\\ \Pr\left(S_{n+1} = \{r+1, b+1\} | S_n = \{r, b\}\right) &= \frac{\frac{r}{8} \times \frac{b}{8}}{1 - \frac{8-r}{8} \times \frac{8-b}{8}} = \frac{r \times b}{8 \times r + 8 \times b - r \times b} \end{align*} \]
We can transform these into unconditional probabilities by noting that
\[ \begin{align*} \Pr\left(S_1 = \{1, 2\}\right) =& 1\\ \\ \Pr\left(S_n = \{r, b\}\right) =&\Pr\left(S_n = \{r, b\} | S_{n-1} = \{r-1, b\}\right) \times \Pr\left(S_{n-1} = \{r-1, b\}\right)\\ +& \Pr\left(S_n = \{r, b\} | S_{n-1} = \{r, b-1\}\right) \times \Pr\left(S_{n-1} = \{r, b-1\}\right)\\ +& \Pr\left(S_n = \{r, b\} | S_{n-1} = \{r-1, b-1\}\right) \times \Pr\left(S_{n-1} = \{r-1, b-1\}\right) \end{align*} \]
provided that we remain mindful of the fact that if Sir R-----'s score ever exceeds the Baron's then the game should be at an end so that
\[ \begin{align*} \Pr\left(S_n = \{r, r\}\right) =&\Pr\left(S_n = \{r, r\} | S_{n-1} = \{r-1, r\}\right) \times \Pr\left(S_{n-1} = \{r-1, r\}\right)\\ +& \Pr\left(S_n = \{r, r\} | S_{n-1} = \{r-1, r-1\}\right) \times \Pr\left(S_{n-1} = \{r-1, r-1\}\right) \end{align*} \]
We should therefore conclude that
\[ \begin{align*} \Pr\left(S_2 = \{2, 2\}\right) =& \Pr\left(S_2 = \{2, 2\} | S_1 = \{1, 2\}\right) \times \Pr\left(S_1 = \{1, 2\}\right)\\ +& \Pr\left(S_2 = \{2, 2\} | S_1 = \{2, 1\}\right) \times \Pr\left(S_1 = \{2, 1\}\right)\\ +& \Pr\left(S_2 = \{2, 2\} | S_1 = \{1, 1\}\right) \times \Pr\left(S_1 = \{1, 1\}\right)\\ \\ =& \Pr\left(S_2 = \{2, 2\} | S_1 = \{1, 2\}\right) \times 1\\ +& \Pr\left(S_2 = \{2, 2\} | S_1 = \{2, 1\}\right) \times 0\\ +& \Pr\left(S_2 = \{2, 2\} | S_1 = \{1, 1\}\right) \times 0\\ \\ =& \Pr\left(S_2 = \{2, 2\} | S_1 = \{1, 2\}\right) = \frac{8 \times 1 - 1 \times 2}{8 \times 1 + 8 \times 2 - 1 \times 2} = \frac{6}{22} = \frac{3}{11} \end{align*} \]
Similarly, we must have
\[ \Pr\left(S_2 = \{1, 3\}\right) = \Pr\left(S_2 = \{1, 3\} | S_1 = \{1, 2\}\right) = \frac{8 \times 2 - 1 \times 2}{8 \times 1 + 8 \times 2 - 1 \times 2} = \frac{14}{22} = \frac{7}{11} \]
and
\[ \Pr\left(S_2 = \{2, 3\}\right) = \Pr\left(S_2 = \{2, 3\} | S_1 = \{1, 2\}\right) = \frac{1 \times 2}{8 \times 1 + 8 \times 2 - 1 \times 2} = \frac{2}{22} = \frac{1}{11} \]
To figure the probabilities of the scores after their second change we need simply repeat these calculations using those that we have deduced for the first, yielding
\[ \begin{align*} \Pr\left(S_3 = \{3, 2\}\right) =& \Pr\left(S_3 = \{3, 2\} | S_2 = \{2, 2\}\right) \times \Pr\left(S_2 = \{2, 2\}\right)\\ =& \frac{8 \times 2 - 2 \times 2}{8 \times 2 + 8 \times 2 - 2 \times 2} \times \frac{3}{11} = \frac{12}{28} \times \frac{3}{11} = \frac{3}{7} \times \frac{3}{11} = \frac{9}{77}\\ \\ \Pr\left(S_3 = \{2, 3\}\right) =& \Pr\left(S_3 = \{2, 3\} | S_2 = \{2, 2\}\right) \times \Pr\left(S_2 = \{2, 2\}\right)\\ +& \Pr\left(S_3 = \{2, 3\} | S_2 = \{1, 3\}\right) \times \Pr\left(S_2 = \{1, 3\}\right)\\ \\ =& \frac{8 \times 2 - 2 \times 2}{8 \times 2 + 8 \times 2 - 2 \times 2} \times \frac{3}{11} + \frac{8 \times 1 - 1 \times 3}{8 \times 1 + 8 \times 3 - 1 \times 3} \times \frac{7}{11}\\ \\ =& \frac{12}{28} \times \frac{3}{11} + \frac{5}{29} \times \frac{7}{11} = \frac{36}{308} + \frac{35}{319} = \frac{9}{77} + \frac{35}{319}\\ \\ =& \frac{9 \times 319 + 35 \times 77}{77 \times 319} = \frac{2,871 + 2,695}{24,563} = \frac{5,566}{24,563} = \frac{46}{203}\\ \\ \Pr\left(S_3 = \{3, 3\}\right) =& \Pr\left(S_3 = \{3, 3\} | S_2 = \{2, 2\}\right) \times \Pr\left(S_2 = \{2, 2\}\right)\\ +& \Pr\left(S_3 = \{3, 3\} | S_2 = \{2, 3\}\right) \times \Pr\left(S_2 = \{2, 3\}\right)\\ \\ =& \frac{2 \times 2}{8 \times 2 + 8 \times 2 - 2 \times 2} \times \frac{3}{11} + \frac{8 \times 2 - 2 \times 3}{8 \times 2 + 8 \times 3 - 2 \times 3} \times \frac{1}{11}\\ \\ =& \frac{4}{28} \times \frac{3}{11} + \frac{10}{34} \times \frac{1}{11} = \frac{1}{7} \times \frac{3}{11} + \frac{5}{17} \times \frac{1}{11} = \frac{3}{77} + \frac{5}{187}\\ \\ =& \frac{3 \times 187 + 5 \times 77}{77 \times 187} = \frac{561+385}{14,399} = \frac{946}{14,399} = \frac{86}{1,309} \\ \\ \Pr\left(S_3 = \{1, 4\}\right) =& \Pr\left(S_3 = \{1, 4\} | S_2 = \{1, 3\}\right) \times \Pr\left(S_2 = \{1, 3\}\right)\\ =& \frac{8 \times 3 - 1 \times 3}{8 \times 1 + 8 \times 3 - 1 \times 3} \times \frac{7}{11} = \frac{21}{29} \times \frac{7}{11} = \frac{147}{319}\\ \\ \Pr\left(S_3 = \{2, 4\}\right) =& \Pr\left(S_3 = \{2, 4\} | S_2 = \{1, 3\}\right) \times \Pr\left(S_2 = \{1, 3\}\right)\\ +& \Pr\left(S_3 = \{2, 4\} | S_2 = \{2, 3\}\right) \times \Pr\left(S_2 = \{2, 3\}\right)\\ \\ =& \frac{1 \times 3}{8 \times 1 + 8 \times 3 - 1 \times 3} \times \frac{7}{11} + \frac{8 \times 3 - 2 \times 3}{8 \times 2 + 8 \times 3 - 2 \times 3} \times \frac{1}{11}\\ \\ =& \frac{3}{29} \times \frac{7}{11} + \frac{18}{34} \times \frac{1}{11} = \frac{3}{29} \times \frac{7}{11} + \frac{9}{17} \times \frac{1}{11} = \frac{21}{319} + \frac{9}{187}\\ \\ =& \frac{21 \times 187 + 9 \times 319}{319 \times 187} = \frac{3,927+2,871}{59,653} = \frac{6,798}{59,653} = \frac{618}{5,423}\\ \\ \Pr\left(S_3 = \{3, 4\}\right) =& \Pr\left(S_3 = \{3, 4\} | S_2 = \{2, 3\}\right) \times \Pr\left(S_2 = \{2, 3\}\right)\\ =& \frac{2 \times 3 }{2 \times 8 + 3 \times 8 - 2 \times 3} \times \frac{1}{11} = \frac{6}{34} \times \frac{1}{11} = \frac{3}{17} \times \frac{1}{11} = \frac{3}{187} \end{align*} \]
It is, therefore, but a simple matter of arithmetic to recursively construct the probabilities of the scores after any change in them by employing the expressions for their conditional probabilities and those of the scores that we have already calculated. I said as much to the Baron, in fact, but I suspect that he didn't wholly appreciate my point.

It is also, unfortunately, a tremendously tedious business and so one of my fellow students put together a deck of cards for the Experimental Clockwork Mathematical Apparatus to perform the calculation upon our behalf using its facility for arbitrary precision arithmetic, furnished in listing 1.

Listing 1: Figuring The Probabilities
function hcf(i, j) {
 var zero = ak.bignum(0);
 var r;

 if(ak.lt(i,j)) {r=i; i=j; j=r;}

 while(ak.gt(j,zero)) {
  r = ak.mod(i,j);
  i = j;
  j = ak.lt(ak.add(r, r), j) ? r : ak.sub(j, r);
 }
 return i;
}

function add(l, r) {
 var n = ak.add(ak.mul(l.num,r.den), ak.mul(r.num,l.den));
 var d = ak.mul(l.den,r.den);
 var f = hcf(n,d);
 return {num: ak.div(n, f), den: ak.div(d, f)};
}

function mul(l, r) {
 var n = ak.mul(l.num,r.num);
 var d = ak.mul(l.den,r.den);
 var f = hcf(n,d);
 return {num: ak.div(n, f), den: ak.div(d, f)};
}

var cache = [];

function pr(t, r, b) {
 var zero = ak.bignum(0);
 var one  = ak.bignum(1);
 var r1b0, r0b1, r1b1;

 if(t<1 || r<1 || b<2 || r>b+1) return {num: zero, den: one};
 if(t===1) return {num: r===1 && b===2 ? one : zero, den: one};

 if(!cache[t])    cache[t] = [];
 if(!cache[t][r]) cache[t][r] = [];
 if(!cache[t][r][b]) {
  r1b0 = mul(pr(t-1, r-1, b),   {num:ak.bignum(8*(r-1)-(r-1)*b),
                                 den:ak.bignum(8*(r-1)+8*b-(r-1)*b)});
  r1b1 = mul(pr(t-1, r-1, b-1), {num:ak.bignum((r-1)*(b-1)),
                                 den:ak.bignum(8*(r-1)+8*(b-1)-(r-1)*(b-1))});

  if(r!==b) {
   r0b1 = mul(pr(t-1, r, b-1), {num:ak.bignum(8*(b-1)-r*(b-1)),
                                den:ak.bignum(8*r+8*(b-1)-r*(b-1))});
   cache[t][r][b] = add(r0b1, add(r1b0,r1b1));
  }
  else {
   cache[t][r][b] = add(r1b0,r1b1);
  }
 }
 return cache[t][r][b];
};

Here, fractions are represented as objects with num properties holding their numerators and den properties holding the denominators and their common factors are erased by dividing both by their highest comment factor, as calculated by the hcf function using Euclid's algorithm[1].
Deck 1 demonstrates that the pr function recovers the probabilities of the scores after the second change that we have already deduced.

Deck 1: After The Second Change

Now the easiest way to figure the fairness of this wager is to reckon the chances that the Baron should win it. The soonest that he could have done so would have been with six successful rolls of his die so that Sir R----- could not possibly overtake him. Furthermore, the latest that he could have done so would have been after twelve rolls of the dice with Sir R----- catching up upon one roll and consequently falling behind upon the next, perhaps moving in concert upon the very last cast of the dice.
If the Baron should have won upon the seventh roll of the dice then it must have been the case that he failed upon a cast at which Sir R----- had succeeded and so Sir R-----'s final score could have been no less than two. By the same reasoning we can conclude that if the Baron prevailed upon the \(n^\mathrm{th}\) roll then Sir R----- could not have had a score less than \(n-5\).
The probability of his victory is consequently
\[ \sum_{t=7}^{13} \sum_{r=t-6}^8 \Pr\left(S_t=\{r,8\}\right) \]
where \(\sum\) is the summation sign, which resolves to
\[ \frac{4,015,564,972,198,614,671,468}{5,118,010,397,325,726,685,785} \]
as demonstrated by deck 2.

Deck 2: The Baron's Chances

He should consequently have expected a return of
\[ \begin{align*} 1 - 5 \times \left(1 - \frac{4,015,564,972,198,614,671,468}{5,118,010,397,325,726,685,785}\;\;\right) &= 1 - 5 \times \frac{1,102,445,425,127,112,014,317}{5,118,010,397,325,726,685,785}\\ &= 1 - \frac{1,102,445,425,127,112,014,317}{1,023,602,079,465,145,337,157}\\ &= -\frac{78,843,345,661,966,677,160}{1,023,602,079,465,145,337,157} \end{align*} \]
and I should have had no qualms in advising Sir R----- to agree to the wager!
\(\Box\)

References

[1] You're Going To Have To Think! Why Rational Arithmetic Won't Cure Your Floating Point Blues, www.thusspakeak.com, 2013.

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+