Birthday Problem
by p. Fermat’s little theorem is itself used in cryptography, providing an indirect application of the binomial theorem. One theorem in graph theory states that a graph with n vertices and adjacency matrix A is connected if and only if all the entries in the matrix n−1 (1 + A) are positive. This theorem is proved using the binomial theorem, generalized to certain matrices, and some basic graph theory results. Certain colorings of Pascal’s Triangle produce fractal figures like Sierpinski’s Triangle, named for mathematician Waclaw Sierpinski. In set theory, the regions of a Venn diagram for n distinct sets are in one-to-one correspondence with the binomial coefficients ck for k ranging from 0 to n. Venn diagrams are named for John Venn. Further Reading “The Binomial Theorem.” In Math. http://www.intmath .com/series-binomial-theorem/4-binomial-theorem .php. Chauvenet, William. Binomial Theorem and Logarithms. Self-published: Biblio Bazaar, 2008. Coolridge, J. L. “The Story of the Binomial Theorem.” American Mathematical Monthly 56, no. 3 (March 1949). Friedberg, Stephen H. “Applications of the Binomial Theorem.” International Journal of Mathematical Education in Science and Technology 29, no. 3 (1998). Fulton, C. M. “Classroom Notes: A Simple Proof of the Binomial Theorem.” American Mathematical Monthly 59, no. 4 (1952). Vesta Coufal
See Also: Arabic/Islamic Mathematics; Chinese Mathematics; Cubes and Cube Roots; Permutations and Combinations; Sequences and Series.
Birthday Problem Category: Friendship, Romance, and Religion. Fields of Study: Algebra; Data Analysis and Probability; Measurement; Number and Operations. Summary: The Birthday Problem is a classic example of how probability can reveal counterintuitive truths.
113
The Birthday Problem is a classic probability problem first presented by mathematician and scientist Richard von Mises in 1939, though the fundamental combinatorial concepts involved can be traced back as far as India in the sixth century b.c.e. Today, it is one of the most-explored problems in classrooms, often introduced as early as the middle grades. The problem asks: Given that there is some number of people (n) in a room, what is the probability that at least two of them share the same birthday? One of the aspects that makes this problem so intriguing is that the answer is much different than people intuitively expect. Solving the Birthday Problem The extreme cases of the problem are easy to determine logically. If there are fewer than two people, then it is impossible to have two who share the same birthday, making the probability 0. If there are more people than days in a year, then at least two people must share the same birthday, making the probability 1. Von Mises assumed a fixed 365 days per year, ignoring February 29 as a possible birthday, so the probability is always 1 if there are 366 or more people. More interesting and challenging are the cases for which there are anywhere from 2 to 364 people. For the purposes of modeling and computation, it is assumed that it is equally likely that someone will be born on one day of the year versus another, so there is a 1 chance 365 that a person will be born on any particular day. The Birthday Problem is solved using the mathematical ideas of permutations and combinations, and it is more easily approached if one asks a slightly different but complementary question: What is the probability that everyone in the room has a unique birthday? That is, that no one shares. If there are two people in the room, the first can be born on any of 365 days of the year and the second must be born on any of the remaining 364 days. If there are three people in the room where the first is born on a particular day, the second must be born on one of the remaining 364 days of the year and the third on one of the remaining 363 days. The probability is 365 364 363 . × × 365 365 365
114
Birthday Problem
If there are four people, the probability is 1×
364 363 362 . × × 365 365 365
This pattern can be generalized as P(nomatch) (n) =
P 365 n . 365n
The probability that at least two people in a room of n people share a birthday is 1 minus the probability that there is no match, which can be used to generate the following probabilities.
Number of people in the room 2 10 20 23 30 50 60
Probability that two of these people share a birthday .00274 .117 .411 .507 .706 .970 .995
When there are 23 people in the room, there is slightly more than a 50% chance that two people will share the same birthday, which answers the original question. The probability of at least one match increases quickly and nonlinearly with the number of people, so that when the number reaches 60 (well below the certainty value of 366 people), there is a 99.5% chance that there will be a match—almost certain. For example, as of 2010, there are six pairs of men who share a birthday among the 74 unique winners of the Academy Award for Best Actor. For women, there are three pairs among the 69 unique Best Actress winners. Applications of the Birthday Problem Applications of the Birthday Problem exist in many fields. One is called Class Phenotype Probability. Given six characteristics (blood type, RH positive/negative, sex, mid-digital hair positive/negative, earlobes attached/ unattached, and PTC taste receptor), it is possible to determine the probability that a particular combination exists and also the probability that two people share the same combination. This possibility is quite valuable in
medicine when considering the likelihood of finding matches between donors and recipients. In computer security, a birthday attack is a computationally intensive strategy used to break encrypted digital signatures. A “collision” occurs when different sets of data yield the same cryptographic hash value, which is a function of the input data. The attack repeatedly evaluates a hashgenerating function using random inputs until the output creates a collision with the true hash value it seeks to duplicate. On average, 1.2 × k trials are needed to get a match, where k is the number of possible outputs (for example, a 64-bit hash value has about 1.8 × 1019 outputs). The birthday attack strategy becomes much less efficient as the hash length increases. There are interesting extensions of the Birthday Problem based on slightly altering the question or assumptions. The first comes from considering the chance that three or more people share a birthday (or four, or five, and so forth). The Almost-Birthday Problem expands the problem to finding at least two people whose birthdays are within one day of each other. The Movie Line Problem states that the first person in a line for a movie whose birthday matches someone in front of them wins free tickets, and it seeks to find where someone should stand to have the best chance of winning. The Goldberg Extension computes the expected number of different birthdays in a group, while the Tuesday Birthday Problem is given as, “I have two children, one of whom is a boy born on a Tuesday. What is the probability that my other child is a boy?” Other variations assume unequal distributions of birthdays throughout the year. As with the original problem, solutions usually run contrary to most people’s intuition. The ideas provide the basis for many applied investigations, such as the photon behavior modeling done by mathematical physicist Satyendra Nath Bose, after whom the subatomic particle “boson” is named. Further Reading Borja, Mario Cortina, and John Haigh. “The Birthday Problem.” Significance 4, no. 3 (2007). Goldberg, Samuel. “A Direct Attack on a Birthday Problem.” Mathematics Magazine 49, no. 5 (1976). Mosteller, Frederick. Fifty Challenging Problems in Probability With Solutions. New York: Dover Publications, 1987. Lidia Gonzalez
