City Picks, Euler, and the Ditsy Coat Check Girl

One of the interesting things about doing gaming analysis is that every now and then I discover a clever piece of mathematics that is just the thing I need to complete a job.  Unfortunately, I don't always discover the mathematics I need.  A year or so ago I was asked to look at a video game that was based on both geometry and Poker hands.  Try as I did, I just couldn't see a way to analyze the game nor did I recall any mathematics that I felt would help me out.  To this day I'm baffled by this game and occasionally I go back and take another look at it -- frustrating.  Happily, this doesn't happen that often, usually things work out.  Here is just such a story.

   I am writing a book about state lotteries which should be published sometime this spring.  The title is The Lottery Book, The Truth Behind the Numbers and it is being published by Bonus Books of Chicago.  The Foreword to the book is by Frank Scoblete.  In it I analyze just about every state lottery game in the country and explain to the reader just how such analyses are carried out.  As you might imagine, I ran into some unusual games whose analyses required some serious thought.  To my mind, the most notable of these was provided by the state of Wisconsin.

   Wisconsin has a lottery game called City Picks.  Here is how it is played.  The player is provided with nine Wisconsin cities: Chippewa Falls, Dodgeville, Green Bay, Kenosha, Madison, Milwaukee, Superior, Two Rivers, and Wisconsin Rapids.  To play City Picks the bettor simply arranges these nine cities in order 1 through 9.  The Wisconsin State Lottery then randomly arranges these same cities in a different order, again 1 through 9.  The player is paid according to how many of his numbered choices match the lottery's numbered choices.  Since I cover the game in detail in my book, I'm not going to repeat the complete analysis here.  Suffice it to say, however, that in order to carry out such an analysis one must determine how many of the 9! or 362,880 permutations of these cities occur as no matches, one match, two matches, and so on.  Let me show you an example.

   Suppose for a given lottery ordering we want to determine how many ways we can produce an ordering of ours that has exactly 5 matches.  Well, we first have to choose which 5 of the 9 numbers will be our matches.  This is old stuff to us by now; it is just the number of way of picking 5 things from a set of 9 and is the number 9!/(4!5!) or 126.  Now for each such choice the remaining 4 numbers have to not match those of the same remaining 4 lottery choices.  In mathematical jargon, they have to be a derangement of the lottery's choices.  Let's take a closer look at this.

   Consider the integers 1 2 3 4 in that order.  How many ways can we rearrange these numbers so that there are no matches in the rearrangement?  For a small number like 4 this is relatively easy, we can just list them.  The derangements are:

                   2 3 4 1                3 4 2 1                2 1 4 3
                   2 4 1 3                4 1 2 3                3 1 4 2
                   3 4 1 2                4 3 1 2                4 3 2 1

There are 9 of them.  Thus the number of ways of getting exactly 5 matches in the City Picks game is 126 x 9 or 1,134.

       For larger numbers it is not feasible to list all of the derangements.  For example, if we consider the derangements of 1 2 3 4 5 6, there are 265 of them and these derangements increase rapidly as the number of integers increases.  So, in general,  how do we determine derangements?  The answer goes all the way back to the Swiss mathematician Leonhard Euler (1707 - 1783).  Euler gave a simple recursion relation for generating the number of derangements.  Here's how it works.

   Let d_n denote the number of derangements of the integers 1, 2, 3, ..., n.  Clearly if n = 1 then d₁ = 0.  If n = 2 then the only derangement of 1 2  is 2 1 so d₂= 1.  Euler's recursion relation is

If we let n = 3 in (1) then we have

Since we now have d₃and d₂we can let n = 4 in (1) and obtain

which, as we saw in our example, is exactly right.  One can continue with this "bootstrap" operation as long as one wants.  I won't prove to you that (1) is correct, but you can contact me by email (just click on Technigame at the end of this article) if you would like to see a proof.

   By doing a bit of algebra using (1) and recalling some calculus, one can show that the expression d_n / n! gets arbitrarily close to the number 1/e as n gets large, e being the ubiquitous base of the natural logarithms. It is approximately 2.7182818.  The number 1/e therefore is approximately 0.3678794.  I mention this for the following reason.

   Consider a restaurant with a ditsy coat check girl.  She constantly gets the coat checks mixed up so that some patrons get back someone else's coat when they leave the restaurant.  What is the probability that no one gets back his or her coat?  Well, for 4 patrons this number is clearly the number of derangements of the 4 coats divided by the total number of permutations, that is, d₄ / 4!.  This number is 9/24 or 0.375.  Well now, with only 4 patrons you would think that it is reasonably likely that no one gets back the same coat.  With more patrons, however, it seems intuitive that it is more than likely that at least one person gets back his or her coat, that is, it is very unlikely that no one gets back the same coat.  Sounds right to me, but guess what?  It just isn't so.  Here is a table showing the probabilities for n = 4 through 10.
 
 

As you can see, as n grows the probability, which is just d _n / n!, gets closer and closer to the number 1/e just as I mentioned in the previous paragraph.  For 7 or more patrons the probabilities are almost constant.  As I have learned throughout the years, and as this example shows, intuition is a fickle friend.

See you next month.