Friday 14 January 2011

Who Created the Birthday Problem, and Even One More Version

Steven Coyler who blogs at Multiplication by Infinity sent me a nice comment on my last blog that included a time line of big moments in the development of the birthday problem. It was, I believe, part of a larger work that he blogged here on conjoining the time lines from the book "50 Things You Really Should Know About Mathematics."

The last part of his time line on the birthday problem said, "1939 - Richard von Mises proposes the birthday problem." You can search almost anywhere and find that confirmed...but being the contrary guy I am, I will disagree. I realize that in disagreeing with Crilly I am disagreeing with an established world class Math Historian (his biography of Arthur Cayley is classic work)..... and yet I press on.

I think it may be that
A)the birthday problem as we know it was not first given by von Mises and
B) the typical version may have appeared over twelve years before von Mises publication.....(but von Mises may have published first).

For support I call upon that great historian of mathematical recreations, David Singmaster. In his "Chronology of Recreational Mathematics" he has:

1927 Davenport invents Birthday Problem.

1939 von Mises first studies Birthday Problems, but not the usual version.
1939 Ball-Coxeter: Mathematical Recreations and Essays, 11th ed. - first publication of Davenport's version of the Birthday Problem

In another note he gives source information:
Richard von Mises. Ueber Aufteilungs und Besetzungs Wahrscheinlichkeiten. Rev. Fac. Sci. Univ. Istanbul (NS) 4 (1938 39) 145 163. = Selected Papers of Richard von Mises; Amer. Math. Soc., 1964, vol. 2, pp. 313 334. Says the question arose when a group of 60 persons found three had the same birthday. He obtains expected number of repetitions as a function of the number of people. He finds the expected number of pairs with the same birthday is about 1 when the group has 29 people, while the expected number of triples with the same birthday is about 1 when there are 103 people. He doesn't solve the usual problem, contrary to Feller's 1957 citation of this paper.

and another:
Ball. MRE, 11th ed., 1939, p. 45. Says problem is due to H. Davenport. Says "more than 23" and this is repeated in the 12th and 13th editions.

Regarding Davenport, he has :
George Tyson was a retired mathematics teacher when he enrolled in the MSc course in mathematical education at South Bank in about 1980 and I taught him. He once remarked that he had known Davenport and Mordell, so I asked him about these people and mentioned the attribution of the Birthday Problem to Davenport. He told me that he had been shown it by Davenport. I later asked him to write this down.
George Tyson. Letter of 27 Sep 1983 to me. "This was communicated to me personally by Davenport about 1927, when he was an undergraduate at Manchester. He did not claim originality, but I assumed it. Knowing the man, I should think otherwise he would have mentioned his source, .... Almost certainly he communicated it to Coxeter, with whom he became friendly a few years later, in the same way." He then says the result is in Davenport's The Higher Arithmetic of 1952. When I talked with Tyson about this, he said Davenport seemed pleased with the result, in such a way that Tyson felt sure it was Davenport's own idea. However, I could not find it in The Higher Arithmetic and asked Tyson about this, but I have no record of his response.
Anne Davenport. Letter of 23 Feb 1984 to me in response to my writing her about Tyson's report. "I once asked my husband about this. The impression that both my son and I had was that my husband did not claim to have been the 'discoverer' of it because he could not believe that it had not been stated earlier. But that he had never seen it formulated."
I have discussed this with Coxeter (who edited the 1939 edition of Ball in which the problem was first published) and C. A. Rogers (who was a student of Davenport's and wrote his obituary for the Royal Society), and neither of them believe that Davenport invented the problem. I don't seem to have any correspondence with Coxeter or Rogers with their opinions and I think I had them verbally.

So my spin on all this is that probably Harold Davenport came up with the version, "How many people are needed for the probability of a match to be greater than 1/2?", but did not publish it anywhere. This is not uncommon in recreational problems. Consider the Collatz problem which seemed to circulate around and across college campuses for years with multiple names. In or around 1939 von Mises was at a party and came up with a slightly different version, "How many pairs of birthday matches would you expect for a collection of n people?" This is the inverse relationship to the common birthday problem today which asked, given an expected value of 1/2, what is the probability of a match.

I also found an interesting variation of the problem that should be of interest to Steven Coyler. The book he quoted in the comment post is authored by Tony Crilly from Manchester here in the UK. As I was checking some notes in Dr. Singmaster's sources, I came across this citation:
Tony Crilly & Shekhar Nandy. The birthday problem for boys and girls. MG 71 (No. 455) (Mar 1987) 19 22. In a group of 16 boys and 16 girls, there is a probability greater than ½ of a boy and a girl having the same birthday and 16 is the minimal number.

Folks who like probability might try to derive that result.

The problem, I am told, is in this book

A few years after I wrote this, I came across yet another version of the birthday problem I had never considered.
How many people needed so probability is 50% that everyone shares a birthday with at least one other?
The strong birthday problem has applications to the interesting problem of look-alikes, which is of interest to criminologists and sociologists.

The answer, it seems, is 3,064.
Amazingly, with 2000 people in the room, the probability is only 1/10000, but by the time you get 4000 the probability is .9334. In even a pretty small village, there is a pretty good chance that someone else shares your birth date.


Steven Colyer said...

It's Colyer not Crolyer, but Crolyer seems more interesting; makes one wonder which ethnicity I am. :-)

Actually, I'm not sure of the origin of my own name. Possibly the Dutch version of the English Collier? Not worried what anyone calls me, as long as they don't call me late to dinner. American Muttski is fine, and quite properly descriptive.

In any event, my 4 high school Maths were Algebra 1, Geometry, Analytic Geometry, and Calculus. It was on the first day of our sophomore year that our Geometry teacher posed the Birthday problem. We didn't believe it! But he asked around the class of 23 and sure enough, 2 had the same date!

He was also a fine baseball coach, but years later did prison time for being a professional football bookie (quite illegal in the USA), indeed the largest in our state! And they said Maths doesn't pay! :-)

Steven Colyer said...

There are 4 pages in Crilly's book, 17 paragraphs, the last 4 of which I retype below:

The birthday calculation makes the assumption that birthdays are uniformly distributed and that each birthday has an equal chance of occurring for a person selected at random. Experimental results show this is not exactly true (more are born during the summer months) but it is close enough for the solution to be applicable.

Birthday problems are examples of occupancy problems, in which mathematicians think about placing balls in cells. In the birthday problem, the number of cells is 365 (these are identified with possible birthdays) and the balls to be be placed at random in the cells are the people. The problem can be simplified to investigate the probability of two balls falling in the same cell. For the boys-and-girls problem, the balls are of two colours.

It is not only mathematicians who are interested in the birthday problem. Satyendra Nath Bose was attracted to Albert Einstein's theory of light based on photons. He stepped out of the traditional lines of research and considered the physical setup in terms of an occupancy problem. For him, the cells were not days of the year as in the birthday problem but energy levels of the photons. Instead of people being put into cells as in the birthday problem he distributed numbers of photons. There are many applications of occupancy problems in other sciences. In biology, for instance, the spread of epidemics can be modelled as an occupancy problem - the cells in this case are geographical areas, the balls are diseases and the problem is to figure out how the diseases are clustered.

The world is full of amazing coincidences but only mathematics gives us the way of calculating their probability. The classical birthday problem is just the tip of the iceberg in this respect and it is a great entry into serious mathematics with important applications.

Pat's Blog said...

Steven, Mia Culpa,
Hope I corrected it everywhere. About the fact that birth dates are not equally distributed, I have a graph of the day by day births in 1978. You can obviously see every weekend and major holidays in the data. Not sure if it will show here , maybe I'll put an addendum to the graph. or another short blog.