NYTimes: It’s My Birthday Too, Yeah

I was explaining to my class the other day that given our class sizes it is better than 50-50 that two students have the same birthday.

But hard to explain.

So I give them this article.

Article below By STEVEN STROGATZ

Me, Myself and Math, a six-part series by Steven Strogatz, looks at us through the lens of math.

By an amazing coincidence my sister, Cathy, and my Aunt Vere have the same birthday: April 4.

Actually, it’s not so amazing. In any extended family with enough siblings, aunts, uncles and cousins, you’d expect at least one such birthday coincidence. Certainly, if there are 366 people in the family — more relatives than days of the year — they can’t all have different birthdays, so a match is guaranteed in a family this big. (Or if you’re worried about leap year, make it 367.)

But suppose we don’t insist on absolute certainty. A classic puzzle called the “birthday problem” asks: How many people would be enough to make the odds of a match at least 50-50?

The answer, just 23 people, comes as a shock to most of us the first time we hear it. Partly that’s because it’s so much less than 366. But it’s also because we tend to mistake the question for one aboutourselves. My birthday.

John Allen Paulos gave a vivid example of this error in his trenchant best seller “Innumeracy”:

A couple of years ago, someone on the Johnny Carson show was trying to explain [why 23 is the answer to the birthday problem]. Johnny Carson didn’t believe it, noted that there were about 120 people in the studio audience, and asked how many of them shared his birthday of, say, March 19. No one did, and the guest, who wasn’t a mathematician, said something incomprehensible in his defense.

For years I’ve been dying to see a clip of that scene. It’s become legendary, an iconic moment in mathematical pop culture. Yet I couldn’t find it on YouTube, and none of my colleagues, including Paulos, could remember when it occurred or who the humiliated guest was. Memories have understandably faded over the years.

But fortunately, as of 2010 every surviving tape of “The Tonight Show With Johnny Carson” has been digitized and made publicly available. Thanks to the Carson archives and some ace detective work by a researcher at The Times, we can now watch what really happened when Johnny met the birthday problem. The encounter offers lessons not just about math but about memory as well.
Before we get to the clip, you may be wondering why the birthday problem is worth studying. For one thing, it highlights how wrong our intuition can be about coincidences, and how easily we underestimate the power of chance — a cautionary lesson for anyone working in sports, finance or any other field where fluky things happen a lot.

Second, the reasoning used to solve the birthday problem is transferable. Medical statisticians use it to estimate the likelihood of finding matches within pools of potential transplant donors and recipients on such characteristics as blood type, Rh factors and other immunological markers. Criminologists use it to calculate how many partial matches between DNA profiles they should expect to find — by chance alone — when trawling databases of convicted offenders. Cryptographers use it to analyze malicious “birthday attacks” that adversaries can deploy to subvert digital signatures.

To work our way toward solving the birthday problem, let’s first simplify it by assuming there are 365 days in the year, and that all birthdays are independent and equally likely. Under these assumptions, we want to figure out how many people we need for the odds to be better than 50-50 that at least two of them have the same birthday.

The solution relies on a single principle, used over and over. I’ll call it the combination principle, but it’s just common sense. Anyone who gets dressed in the morning knows it.

Suppose you have 3 pairs of pants and 5 shirts. (I realize you probably have more than this, but pretend you’re a math professor.) How many different outfits can you create? (And don’t worry if some of the shirts and pants don’t go too well together — remember, you’re a math professor!) Say you decide to wear your ratty blue jeans. Then with five shirts to choose from, that gives you 5 outfits right there. Or you could wear those nice polyester khakis you still have from your high school graduation. Combine them with any of the five shirts and that’s another 5 outfits. Finally, you could go casual and wear your Star Trek sweat pants along with any of the five shirts, creating 5 more outfits and bringing the total to 3 times 5, or 15, outfits in all.

That’s the combination principle in action: If you can make Mchoices of one thing (like 3 pairs of pants) and N choices of another (like 5 shirts), you can make M x N combinations of them both (15 outfits). The principle also extends to more than two things. If you want to top off your outfit with a stylish hat and you have 6 to choose from, you can create 3 x 5 x 6 = 90 ensembles of pants, shirts and hats.

Next, let’s apply this principle to a warm-up birthday problem featuring the first three United States presidents. Relative to the New Style (Gregorian) calendar, George Washington was born on Feb. 22, John Adams on Oct. 30, and Thomas Jefferson on April 13. Unsurprisingly, no matches. To figure out the odds of this happening by chance, we imagine alternate realities — all the possible combinations of birthdays that could have occurred — and then calculate what fraction of those combinations involve three distinct birthdays.

According to the combination principle, there are 365 x 365 x 365 combinations of three birthdays, since any day of the year is possible for each of the three presidents. To count how many of these combinations contain no matches, let Washington go first. He has all 365 days at his disposal. But once his birthday is fixed, he leaves Adams with only 364 choices to avoid a match, which in turn leaves Jefferson only 363. So, by the combination principle, there are 365 x 364 x 363 nonmatching combinations of three birthdays, out of a total of 365 x 365 x 365 combinations altogether.

Hence the probability that all three birthdays differ is the ratio of these huge numbers:

which is about 0.9918 or 99.18 percent. In other words, it was almost a sure thing that none of the birthdays would match, as we’d expect by common sense.

To extend this result to four or more people, look again at the fraction above and savor the patterns in it. For three people the fraction has three descending numbers — 365, 364, 363 — in the numerator, and three copies of 365 in the denominator.  So for four people, the natural and correct guess is that the answer becomes

This expression is merely the fraction we found earlier for three people, multiplied by 362/365. Doing the arithmetic then gives 0.9836, or a 98.36 percent chance that four random people have four different birthdays. That means the probability that two or more of them share a birthday is about 1 – 0.9836 = 0.0164, or 1.64 percent.

Continuing in this way, ideally with the help of a spreadsheet, computer or online birthday problem calculator, we can crank out the corresponding probabilities for any number of people. The calculations show that the odds of a match rise sharply as the group gets larger. With 10 people, the odds are almost 12 percent; with 20 people, 41 percent. When we reach the magic number of 23 people, the odds climb above 50 percent for the first time, which is what we were trying to prove.

Intuitively, how can 23 people be enough? It’s because of all the combinations they create, all the opportunities for luck to strike. With 23 people, there are 253 possible pairs of people (see the notes for why), and that turns out to be enough to push the odds of a match above 50 percent.

Incidentally, if you go up to 43 people — the number of individuals who have served as United States president so far — the odds of a match increase to 92 percent. And indeed two of the presidents dohave the same birthday: James Polk and Warren Harding were both born on Nov. 2.

And now… here’s Johnny! On Feb. 6, 1980, about 14 minutes into “The Tonight Show,” Johnny Carson and his sidekick Ed McMahon begin bantering about Ed’s upcoming birthday and famous Americans born in February. Then Johnny changes gears and says, “You know, I’m gonna try something tonight. Now I may get this wrong. I remember this from a long time ago.” He tries to pose the birthday problem, fumbles a bit with the phrasing, and finally comes up with this formulation: “How many people would you think would have to be in a room that your odds would be almost sure that they would have exactly the same birthday on the same day?”

Douglas C. Pizac/Associated PressJohnny Carson, right, and Ed McMahon during the final taping of “The Tonight Show” in 1992. Click here for the birthday problem clip from the episode of Feb. 6, 1980 »

Ed guesses 1,000, which suggests he doesn’t understand the question, since 366 people already ensure a match. Johnny shakes his head slightly and says, “Something like 35 or 40.” “That’s all?” Ed interjects, surprised, and Johnny continues, “the odds are pretty good, if I remember.”

You’ve got to appreciate what a bombshell this is, at least in my world: Contrary to the collective memory of the mathematical community, it wasn’t a guest scientist who posed the puzzle that night — it was Johnny himself! Though in retrospect, our mistake was predictable. As with many other false memories and urban legends, our garbled recollection makes more sense than what actually happened. We don’t normally think of Johnny as someone who’d pose a classic math problem and know its surprising answer.

Then comes the next twist: Ed leads Johnny astray. He says, “Pick a day and see if we have it.” Johnny says, “Lady in the front row, what’s your birthday?” “August 9,” she says. “Anyone else here have a birthday on August 9?” asks Johnny. “No?” He looks baffled. “We have 500 people here.” They try someone else’s birthday, April 9, and again there are no matches. Ed acts vindicated and the audience finds the whole thing hilarious.

What went wrong? Johnny did the wrong experiment! By asking for matches specifically to August 9 (or to April 9), he altered the problem. The original problem asked for a match between any two people on any day. A much larger number of people (253, as it turns out) are required for there to be a better than even chance of finding a match to a specific birthday like Aug. 9.

Let me leave you with one last coincidence to ponder. John Adams and Thomas Jefferson died on the same day — the Fourth of July, 1826, exactly 50 years after the adoption of the Declaration of Independence.

Math can’t explain everything.