Combinatorics with Blitzstein and Hwang

Also from Blitzstein and Hwang, seven chess matches are played between players A and B.  How many ways can the final result be 4-3 to A?

In doing this question, I am reminded about how almost all of the difficult work in maths questions comes in unpacking the question.  This unpacking is also the act of modelling.  And it isn't easy when you're doing it from scratch.

So my initial thinking was to transform the problem into a counting problem.  We don't need to model B at all here - it can all be done in modelling how A gets those 4 points.  This is because each game has precisely one point to distribute, and that will certainly happen at the end of each game.  So B disappears from the analysis.  This is like the 'degrees of freedom' idea in statistics 

With only seven games, there's no way A could have finished with 4 points without at least one clear victory.  At the other end of chess playing competence is the possibility that A won 4 (and therefore lost 3).  Note also that the number of draws must always be 0 or some multiple of 2.

Now that B has been dispatched, we look at the triplet which is a result.  In general, there are the following four ways that 4-3 can result, were W=A win, D=draw, L=A loss:

• 1W 6D 0L
• 2W 4D 1L
• 3W 2D 2L
• 4W 0D 3L

Now we can use the 'degrees of freedom' trick one more time.  If you know two elements of this triplet, then you'll know for sure what the third element is.  So we don't need to model three distinct values for D,W and L. We only need two, but which two?

I always prefer to go for smaller numbers, and on that basis, I'd go for W + L.  We shall henceforth model only A's wins and losses, since A's draws are implied.

Now we have a sum of 4 possibilities.  Let's take them one by one. ${7} \choose {1}$  represents all 7 locations where that one win would happen.  We don't have losses since by implication all the six other slots were draws.  So for this sub-case, we're done.  Once we place the  win, we have no more variations to deal with.

  ${{7} \choose {2}} { {5} \choose {1}}$ represents first how we can distribute two wins among the seven games, then when that's done we have 5 unfilled slots which we need to drop one loss into.  We multiply those two together (choices multiply).

Similarly,   ${{7} \choose {3}} { {4} \choose {2}}$ represents 3W + 2L.  And finally   ${{7} \choose {4}} { {3} \choose {3}}$ represents the case where we drop in four wins, then all remaining slots contain the full set of 3 losses.

The final answer to the question is: ${{7} \choose {1}} + {{7} \choose {2}} { {5} \choose {1}}  + {{7} \choose {3}} { {4} \choose {2}} + {{7} \choose {4}} { {3} \choose {3}}$

R thinks this amounts to 357 different possible ways to arrive at a 4-3 result for A.

MISSISSIPPI scramble

How many ways are there, Blitzstein and Hwang ask, to permute the word Mississippi?  There are two approaches.  Broadly, we're in the 'naive probability' world where all possibilities are equally likely, so counting methods are going to be useful.

First, and this is generally a good strategy, we give all 11 letters a unique identity.  That is to say, the first s must be thought of as distinct to the second, third and fourth, and so on.  This is analogous to understanding that when you throw a pair of dice, logically there's always a first and second identity for each die. 

There are $11!$ ways (39,916,800) to permute the 11 'distinct' letters (multiplication rule, based on sampling without replacement).  That's more ways than there are actual people currently residing in Mississippi:

Looks like it would take another 500 years, at the current rate of population growth, before we'd run out of basic ways of sharing all the permutations of Mississippi with its inhabitants.

But at this point we want to throw away (divide out) certain permutations.  From a schoolteacher point of view, wherever those four s's landed up, we don't care about their particular order now.  In other words, we're making the conscious decision to consider an s like any other s.  And an i like any other i.  And a p like any other p.  A kind of homogenisation.  The m stands unique and proud at the head of the word.  But in terms of permutations, the m is the unmodelled case, since, when you've decided how to fill the 10 other slots using all your s's, i's and p's, then the m just has to go where it is told.  What a come down - tables turned on the m.

There are four s's, and four i's.  And we need to know how much not to care about their order.  If we did care for their order, then we could permute them $4!$ ways.  Similarly there are $2!$ orderings of p.  So we want to throw away in total  $4!4!2!$ of the $11!$, meaning that the 'schoolteacher's answer' (were all letters are considered homogeneous) is $\frac{11!}{4!4!2!}$.

The second solution is to break it down into 3 sections, each with a binomial 'n chose k' element.

Let's start with the s.  We have 11 slots and 4 of them.  So $11 \choose 4$.  Using the multiplication rule, you then could drop your 4 i's into any of the remaining 7 slots, $7 \choose 4$ and finally our two p's can take up any of the three remaining slots, $3 \choose 2$.  Again, m is the unmodelled, bossed about letter who must take the last slot, wherever that is.  

So,  it must be the case that $11!/4!4!2! = {11 \choose 4}{7 \choose 4}{3 \choose 2}$.

What does R have to say about that?

It agrees, and gives us the final (schoolteacher's) answer, 34,650 versus the 'radical identity' answer of 39,916,800.

So perhaps we could give the school teacher permutations just to the Hispanic residents (excluding Puerto Ricans, sorry).

Problem of Points - The Solution

The solution to the problem of points tells you how you would divide up the stakes in a fair game (fair in the sense of each step outcome being equally likely to favour any player) between two players A and B if A needed $n_A$ more wins and B needs $n_B$.  Pascal and Fermat both end up counting the set of all possibilities and comparing the respective counts to each other and come up with the ratio 

$\sum_{k=0}^{n_B-1}\frac{(n_A+n_B-1)!}{k!(n_A+n_B-1-k)!}$ to $\sum_{k=n_B}^{n_A+n_B-1}\frac{(n_A+n_B-1)!}{k!(n_A+n_B-1-k)!}$.  

This rather ugly looking formulation is something I'll be looking at over the next couple of posts, in a way mathematicians usually don't.  Enamoured of Euclid, they think interesting maths involves proof and concise statement.  That does not work for me.  I want to unpack it and see some examples with real numbers.  Get a feel for it in use.  And after those posts, I'll be doing the same for gambler's ruin, which I personally think has caused me to think a lot more generally than this solution to the problem of points.

Before I finish on this short post, I'd like to say that this solution to the problem of the division of stakes, if you think about it, is the price of the seat if somebody wanted to buy you out of the game.  This is the fair price of your seat at that moment, or the fair price of your position in the same.  And given that the moment in question can analysed at any point in the game, including the moment before the game starts, it also represents an algorithm for working out the fair price of the game for both players, at all points.  That is, it tells you fully at all moments in the game the expected value of each hand.

If the stakes are a value of S then the expected value of one player is 

$S\frac{\sum_{k=0}^{n_B-1}\frac{(n_A+n_B-1)!}{k!(n_A+n_B-1-k)!}}{\sum_{k=0}^{n_B-1}\frac{(n_A+n_B-1)!}{k!(n_A+n_B-1-k)!} + \sum_{k=n_B}^{n_A+n_B-1}\frac{(n_A+n_B-1)!}{k!(n_A+n_B-1-k)!}}$

and for the other just has the other sum on the numerator.

Musical Chairs

Most of the histories of probability trace their facts back to Hacking and David, and I agree these two books are the best of the bunch I have read.  The Hacking book itself references David.  I love the Bernstein book series but I noticed his page 43-44 has some musings on why the Greeks didn't bother with working out odds behind dice games.  I bet they did.  Anyway, he offers an example of the so-called sloppiness of the Greek observations of dice probabilities by mentioning some facts he gleans from David - namely that when using the astragali they valued the Venus throw (1,3,4,6) higher than (6,6,6,6) or (1,1,1,1). which are, he states "... equally probable".

 No, they are not.  David clearly states that the probability of throwing a six as one in ten; likewise with throwing a one.  And threes and fours are about four in ten events.  This means that even if  order is important, the Venus is indeed more likely.  Second mistake, there's only one permutation of four sixes, and only one permutation of four ones.  But there are many permutations of the four Venus numbers, meaning the probability of (1,3,4,6) in any permutation is even higher again than the strictly ordered (1,3,4,6).

It is this partition/permutation dilemma of probability theory, even today, which is so easy to get wrong.  I just re-read some earlier postings I made on equivalence classes and their information content and key milestones in probability theory, and I still like what I wrote.  Also check out a posting on combinatorics in Cardano and Lull.

It is just a throwaway comment in Bernstein's book and hardly invalidates his wonderful sweeping history of risk but is nicely illustrates the problems of thinking about event space and equivalence class.

Tossing away information

Continuing from my initial analysis I would like to model the consequences of sheep bones (just like all other animals' bones) being white.

The crucial human animation in using sheep heel bones as random event generators is the act of tossing.  In the act of tossing, you loose knowledge of the order in which your four bones will lie.  This wouldn't be an issue if all four bones were of a different colour.  Or perhaps if the bones were marked not with 1,3,4,6 on each of the four bones, but with 16 different numbers.  If humans had etched 16 different numbers (pips) on their bones, they'd be using the maximum amount of information possible in that act, namely 6.88 bits.  But that doesn't happen.  Instead we humans make 4 more or less similar sets of markings on the bones.  Then, when we toss, we toss away some information.  But how much?

To answer this question, consider the die.  One die has 2.6 bits per roll.  With two dice, if order is important, then you have 5.16 bits (imagine each of the dice had a different colour).  With three, 7.75 bits (again, imagine each of the three dice a different colour).  You can see how when you run this experiment, information is additive as the sample space size grows multiplicatively.  You can also see that, with the addition of colour, your parallel toss does not lose track of which die had which value.  This parallel toss is the same as if you had tossed one die two (or three) times, and taken note of each result.  It is a kind of 'sampling with replacement' activity in so far as the probability of any single outcome is independent of earlier throws.  (The Markov property).

But bones are white.  And there's a pre-existing tradition of making each bone contain the same number and type of markings as each of the others.  Most likely early dice were crafted out of the astragalus, and they would have inherited this feature of being practically indistinguishable from each other.  That means, when two or three are tossed, information is lost, in comparison to the 'order important' experiment.  Of course, the lost information is precisely that of ordering.  But how much?  For two indistinguishable tossed dice you now only have 4.3 bits of information. When you do the 'order unimportant' analysis on four astragali, the information content drops from 6.88 to 4.3 bits.

Isn't that amazing?  Given what we know about the colour of bones, the number of sheep legs and the casual act of tossing collections of indistinguishable objects, we  built up a randomisation machine which would conveniently deliver for us 4.3 bits.  When we smooth and chip away at a sheep-load of astragalli and make them into 6 sided dice, we manufacture a convenient randomisation machine which delivers 4.3 bits of information to us using only two dice.  That is impressively close to the original.  All those religious-oracular rule books, all those long-forgotten games could still be randomised by a machine of approximately the same degree.  One die would not have been enough, three too much.  But two would have been just right.  Our culture got to keep the innovations built up around the astragali.

My guess as to why each bone (and, later, die) was marked identically is because in the beginning was the single astragalus.  It was a much easier step to make a second instance of that same pip-marked bone.  And a third, and a fourth.  

But why did humans go to the bother of crafting a die if their main practice of four-bone tossing is equivalently replaced with two dice tossing?  Was it a matter of aesthetics?  Did the cubic astragalus with only 4 landable sides present an affront to our sense of symmetry?  Surely it couldn't be to make any kind of mathematical analysis more amenable, though it isn't impossible that some people might have worked out the possibilities of dice.  My money's on our desire to manufacture a symmetric, crafted, more aesthetically pleasing randomiser machine.  The uniform distribution perhaps also made the construction of new equivalence classes and interpretive games based on that uniform element of randomness easier to plan and design.