On Divisions

| 0 Comments

The Baron's game most recent game consisted of a series of some six wagers upon the toss of an unfair coin that turned up one side nine times out of twenty and the other eleven times out of twenty at a cost of one fifth part of a coin. Sir R----- was to wager three coins from his purse upon the outcome of each toss, freely divided between heads and tails, and was to return to it twice the value he wagered correctly.

Clearly, our first task in reckoning the fairness of this game is to figure Sir R-----'s optimal strategy for placing his coins. To do this we shall need to know his expected winnings in any given round for any given placement of his coins.
Let us suppose that sir R----- knew that there was a probability \(p\) that the coin was biased towards heads. If he wagered a sum \(x\) upon heads he should therefore have expected to win
\[ -3 + p \times \left(\frac{11}{20} \times 2 \times x + \frac{9}{20} \times 2 \times (3-x)\right) + (1-p) \times \left(\frac{9}{20} \times 2 \times x + \frac{11}{20} \times 2 \times (3-x)\right) \]
since the formula in the first pair of brackets yields his expected winnings should the coin have been biased for heads and that in the second his winnings should it have been biased for tails.
Rearranging this yields
\[ -3 + \left(\frac{9}{10}+\frac{2}{10}p\right) \times x + \left(\frac{11}{10}-\frac{2}{10}p\right) \times (3-x) \]
If Sir R----- had no evidence as to which way the coin is biased then \(p\) is trivially equal to one half and his expected winnings should have been three coins, no matter how he divided his wager.
If, however, he had evidence that it was biased towards, or indeed away from, heads then \(p\) will differ from one half by some quantity, say \(q\), and his expected winnings should have been
\[ \begin{align*} &-3 + \left(\frac{9}{10} + \frac{2}{10} \times \left(\frac12 + q\right)\right) \times x + \left(\frac{11}{10}-\frac{2}{10} \times \left(\frac12 + q\right)\right) \times (3-x)\\ &\quad\quad= -3 + 3 + \frac{4}{10} \times q \times x - \frac{6}{10} \times q\\ &\quad\quad= \frac25 \times q \times \left(x - 1\frac12\right) \end{align*} \]
From this it is evident that if Sir R----- believed the coin to be biased towards heads, and that \(q\) was consequently positive, he should have wagered as much as possible on heads if he desired the greatest possible expected winnings.
Likewise, if he believed it to be biased towards tails, and that \(q\) was therefore negative, he should have wagered thusly as little as possible.
Now, because of this we need not figure the actual probability that the coin is biased towards heads, just which side it is more likely biased towards. This we can do by simply observing which side has come up the more often.
To figure the expected winnings over the course of the game we should therefore assume that Sir R----- would have wagered all of his coins on whichever side had done so.
If we also assume that he divided his coins equally if each side had come up the same number of times then we are free to declare which side the coin is biased towards before we perform our calculations for, whichever side we choose, the strategy and consequently the workings are the same. We shall therefore assume that the coin is biased towards heads.

The number of ways in which we can observe some specific numbers of heads and tails in a series of tosses of a coin is governed by Pascal's triangle

1
11
121
1331
14641
15101051

Here we may consider a move down and to the left as representing a toss of heads and down and to the right as a toss of tails. The values in each row are equal to the sum of the values to the left and right of it in the preceding row.
I made these observations known to the Baron when he described to me the rules of this game, but I fear I may not have done so with sufficient clarity.

Now, there is a simple formula, known as a combination, that expresses these values in terms of the row, say \(n\), and the position in that row, say \(r\), both of which we start counting from zero.
\[ ^nC_r = \frac{n!}{r! \times (n-r)!} \]
Note that the exclamation marks do not indicate that we should perform the calculation with exceptional vigour, but rather stand for the product of every integer from one up to and including that to its left.
For example, consider the second value in the fifth row
\[ ^5C_2 = \frac{1 \times 2 \times 3 \times 4 \times 5}{(1 \times 2) \times (1 \times 2 \times 3)} = \frac{4 \times 5}{1 \times 2} = \frac{20}{2} = 10 \]
From here it is but a small step to figuring the probability of observing \(r\) heads in \(n\) tosses; we simply multiply the number of ways we might do so by the probability of one such example
\[ p^n_r = {^nC_r} \times \left(\frac{11}{20}\right)^r \times \left(\frac{9}{20}\right)^{n-r} \]
In the first round, Sir R-----'s expected winnings would trivially have been zero, for he would have had no knowledge whatsoever of how the coin was biased.
If Sir R----- had already played an odd number of rounds, let us say \(2n-1\), then one side of the coin must surely have had come up the more often and his expected winnings should consequently be
\[ \begin{align*} E_{2n-1} &= \left(\sum_{0 \leqslant r \leqslant n-1} p_r^{2n-1} \times \left(\frac{9}{20} \times 3 - \frac{11}{20} \times 3\right)\right) + \left(\sum_{n \leqslant r \leqslant 2n-1} p_r^{2n-1} \times \left(\frac{11}{20} \times 3 - \frac{9}{20} \times 3\right)\right)\\ &= \left(\sum_{n \leqslant r \leqslant 2n-1} \frac{3}{10} \times p_r^{2n-1}\right) - \left(\sum_{0 \leqslant r \leqslant n-1} \frac{3}{10} \times p_r^{2n-1}\right) \end{align*} \]
Note that here the capital sigmas stand for the sum of the expressions to their right over the integer values satisfying the conditions beneath them.
Now, if Sir R----- had played an even number of games, let us say \(2n\), there is the possibility that both sides of the coin had turned up an equal number of times, giving expected winnings of
\[ \begin{align*} E_{2n} &= \left(\sum_{0 \leqslant r \leqslant n-1} p_r^{2n}\times \left(\frac{9}{20} \times 3 - \frac{11}{20} \times 3\right)\right) + \left(p_n^{2n} \times 0\right) + \left(\sum_{n+1 \leqslant r \leqslant 2n} p_r^{2n} \times \left(\frac{11}{20} \times 3 - \frac{9}{20} \times 3\right)\right)\\ &= \left(\sum_{n+1 \leqslant r \leqslant 2n} \frac{3}{10} \times p_r^{2n}\right) - \left(\sum_{0 \leqslant r \leqslant n-1} \frac{3}{10} \times p_r^{2n}\right) \end{align*} \]
There is a surprising relationship between these two formulae, which can be revealed by multiplying the first by unity!
Specifically, we shall consider the result of the expression
\[ E_{2n+1} \times \left(\frac{9}{20} + \frac{11}{20}\right) \]
On the face of it this might not seem particularly illuminating, but if we consider the relationship between our expectation formulae and Pascal's triangle, all will become clear.
First, we define
\[ e^n_r = \frac{3}{10} \times p^n_r \]
We can then arrange these in a triangle whose rows represent our expectation formulae

\(\phantom{-}0\)
\(-e^1_0\)\(\phantom{-}e^1_1\)
\(-e^2_0\)\(\phantom{-}0\)\(\phantom{-}e^2_2\)
\(-e^3_0\)\(-e^3_1\)\(\phantom{-}e^3_2\)\(\phantom{-}e^3_3\)
\(-e^4_0\)\(-e^4_1\)\(\phantom{-}0\)\(\phantom{-}e^4_3\)\(\phantom{-}e^4_4\)
\(-e^5_0\)\(-e^5_1\)\(-e^5_2\)\(\phantom{-}e^5_3\)\(\phantom{-}e^5_4\)\(\phantom{-}e^5_5\)

Obviously we can't figure the value of an element by simply adding those either side of it in the row above, but we can exploit the relationships between these elements.
Let us begin by considering those elements of \(E_{2n-1}\) and \(E_{2n}\) for which there are fewer heads than tails

\(-e^{2n-1}_0\)\(-e^{2n-1}_1\)\(-e^{2n-1}_{n-2}\)\(-e^{2n-1}_{n-1}\)
\(\frac{9}{20}\)\(\frac{11}{20}\)\(\frac{9}{20}\)\(\dots\)\(\frac{11}{20}\)\(\frac{9}{20}\)
\(-e^{2n}_0\)\(-e^{2n}_1\)\(-e^{2n}_{n-1}\)

Note that to figure the value of an element in the second row, we must multiply those either side of it in the first row by the probability on the line between it and the element in question before adding them. It is self-evident that this is equivalent to those terms in our product for which there are fewer heads than tails.
Through an identical argument we find that the same is true for terms where the heads outnumber the tails.
All that remains, therefore, is to figure the term in our product which corresponds to that in \(E_{2n}\) for which there are an equal number of heads and tails.
Now the formula for combinations is symmetric in \(r\) about \(\frac12n\), which is plain from inspection of either the formula itself or of Pascal's triangle. As a consequence, we have
\[ \begin{align*} &\frac{9}{20} \times e_n^{2n-1} - \frac{11}{20} \times e_{n-1}^{2n-1}\\ &\quad\quad= \frac{9}{20} \times \frac{3}{10} \times p_n^{2n-1} - \frac{11}{20} \times \frac{3}{10} \times p_{n-1}^{2n-1}\\ &\quad\quad= \frac{9}{20} \times \frac{3}{10} \times {^{2n-1}C_n} \times \left(\frac{9}{20}\right)^{n-1} \times \left(\frac{11}{20}\right)^n - \frac{11}{20} \times \frac{3}{10} \times {^{2n-1}C_{n-1}} \times \left(\frac{9}{20}\right)^n \times \left(\frac{11}{20}\right)^{n-1}\\ &\quad\quad= \frac{3}{10} \times {^{2n-1}C_n} \times \left(\frac{9}{20}\right)^n \times \left(\frac{11}{20}\right)^n - \frac{3}{10} \times {^{2n-1}C_n} \times \left(\frac{9}{20}\right)^n \times \left(\frac{11}{20}\right)^n\\ &\quad\quad= 0 \end{align*} \]
which, to our very great fortune, is exactly the expected winnings that we require!
We can hence assert with full confidence that
\[ E_{2n-1} = E_{2n} \]
and Sir R-----'s expected winnings over the entire contest were determined by
\[ 2 \times E_1 + 2 \times E_3 + E_5 \]
With sufficiently careful arithmetic, we can show this to be equal to
\[ \begin{align*} 2 \times \frac{3}{100} + 2 \times \frac{897}{20,000} + \frac{447,009}{8,000,000} &= \frac{1,644,609}{8,000,000}\\ &= \frac{1,600,000}{8,000,000} + \frac{44,609}{8,000,000}\\ &= \frac{20}{100} + \frac{44,609}{8,000,000} \end{align*} \]
The game is therefore slightly biased in Sir R-----'s favour and I should consequently have had no compunction whatsoever in recommending that he take up the Baron's wager!
\(\Box\)


Based upon an article I wrote for ACCU's CVu magazine.

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+