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.

I am trying to contact Professor Crilly to ask his opinion. Will give his response if I get one.

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 birthdate.
Post a Comment