Tuesday, 5 January 2010

Lotteries and Math

Strange how often problems pop up in two or three different ways at once.. recently I was asked by another teacher how often consecutive numbers showed up in the lottery... He had noticed that it seemed to happen pretty often and he thought it might indicate a problem with the way they were being drawn. He was assuming a lottery with 45 numbers, (other places use other numbers)... Fortunately, I had come across the solution only a few days before in two different journal articles dated about 50 years apart.

I have often heard (yes and even said) that the lottery is a tax on the mathematically ignorant. Lately I have been changing my mind a little. I think they are still a VERY bad gamble. The probability of winning, as one pundit put it, is about the same whether you buy a ticket or not. My new appreciation for them is in the way they have contributed to math, and perhaps along the way, to some good social causes also.

My interest was rekindled recently when I came across a letter in the Library of St. Johns College in Cambridge from Brook Taylor, the guy in the calculus theorem, to his friend, the Reverend Newcome in November of 1711 (almost 400 years ago now). What surprised me about the letter was not what he wrote, but what he included... a lottery ticket. I had no idea that the "money prize" kind of lotteries went back so far. Ok, I'm not totally unread. I knew about the soldiers drawing lots from Agamemnon’s helmet During the Persian Wars, but that was not a pay-to-win-a-prize thing... That was a draw-the-lucky-straw and get to fight against the champion kind of lottery. It turns out that except for rare exceptions, most lotteries were of this sort until around the 14-15 th century. The Chinese apparently had one of some form to build their Great Wall, and Augustus Caesar held one to fund public improvements in Rome, but regular lotteries of the modern type began to appear in the middle ages.... the first recorded official lottery was chartered by Queen Elizabeth I, in the year 1566, and was drawn in 1569. Benjamin Franklin organized one to fund the purchase a cannon to defend the state of Philadelphia. THEN?? They got so corrupt and unsavory that they were literally banned by almost every government in the world. Around 1892 the US passed a federal law that lotteries could not use the public mail, and by 1900 they seemed to be totally gone...... until recently. I was simply not aware of their hundreds of years of popularity in the US and England.

Any game that becomes that popular, will find its way into math, and Lotteries did too. In Genoa in the 1500's they used a lottery to replace members of the ninety man Republic Council. Every six months the ninety names would be placed in a bowl and five names drawn would be replaced with new members. Later the process of buying insurance against their loss of position by members, and others who might have depended on their presence on the council, led to the idea of a lottery with a cash pay-off.

The Genoese lottery problem came to the attention of Leonhard Euler, most probably, at the interest of Frederick the Great who implemented a lottery to rebuild the state revenues after the Seven Years War. Euler wrote ," On the Probability of Sequences in the Genoese Lottery" and calculated the probability that if five numbers were selected at random from the interval [1, 90], there would be two or more consecutive numbers. With the kind of magical inductive work he is known for, he came up with $\frac{\dbinom{n-m+1}{m}}{\dbinom{n}{m}}$.. Ok, If Euler felt lotteries were worth his mathematical time... I'll consider them worthy of study... but I won't be buying a ticket this week....

I found another article that spelled out a recursive way to create a table to find the number of ways to NOT get two adjacent.

If we define the number of ways of picking m objects from n objects without getting adjacent values as f(n,m) then we can state that f(n,1) = n and f(1,p)=0 for any p>1..
[It is also easy to show that f(n,2)=$\dbinom{n}{2}$-n+1).. all the ways of picking two except the n-1 ways that have two adjacent numbers]

All the members of f(n,m) are of two kinds, then. One kind is those which include item one, but not item two, and there must be f(n-2,m-1) of these.. (if you have a pattern that doesn't include adjacent values when picking 5 things out of 12 for example, then you can make one that works picking 6 things out of 14 by picking the first and not the second and then the remaining pattern from any successful f(12,5) solution).
There are others which do not include ball 1 but do include ball 2; f(n-1,m) of them... SOO the number of solutions for f(n,m)= f(n-2,m-1) + f(n-1,m) Now we can start to make a table,

N ...1...2...3...4...5...6...7...8...9




3 ......0.....0...0...0...1...4...10..20..35..


Note that each new entry is the entry to its left, added to the entry two to the left in the previous row...

For example, the 4 found for f(6,3) is the one to its left f(5,3) plus the 3 in the location for f(4,2)...

Now we can quickly extend the table for any number of values...

So by either method, the number of ways to NOT get two consecutive numbers (or more) in drawing five balls from a sequence of 45 is given by $\dbinom{45-5+1}{5}$ To find the number of draws that do include adjacent values we subtract this from $\dbinom{45}{5}$ which gives 472,361 ways to get at least one adjacent pair out of the 1,221,759 possible sets of five, a probability of about 38%... so you should expect it pretty often.

No comments: