Home > Birthday Problem | Poker Problem | Needle Problem

1. The Birthday Problem



Introduction

The birthday problem is one of the most famous problems in combinatorial probability. The classical statement of the problem is to find the probability that among n students in a classroom, at least two will have the same birthday. The problem is famous, in part, because the answer is a bit surprising.

As in most mathematical problems, we first have to make some simplifying assumptions, and then find the natural mathematical home for the problem. First, we ignore leap years, so that there are 365 possible birthdays. Next, and most importantly, we assume that birthdays are more or less uniformly distributed throughout the year. With these assumptions, the birthday problem is really a sampling problem. Thus, more generally, suppose that we have a population of N objects (in the birthday problem the objects are the days of the year and thus N = 365). We select n objects from the population, at random, and with replacement. That is, on each selection, independently of the others, we are equally likely to get any of the N objects in the population. This more general version of the birthday problem, then, is to compute the probability p(N, n) that at least two of the objects in the sample are the same.

Mathematical Analysis

Now let us analyze the problem mathematically. First, we will let D denote the population of the N objects. Since we are selecting our sample with replacement, the sample space (the set of all possible samples) is

S = Dn = {(x1, x2, ..., xn): xi in D for each i}.

That is, a sample is simply an ordered sequence of n objects from the population. The birthday event B is the subset of the sample space consisting of all sequences containing at least one duplication. Actually (and this is often the case in probability), it is easier to describe the complementary event Bc, that the sample values are all distinct:

Bc = {(x1, x2, ..., xn): xi in D for each i and xixj for ij}.

That is, the elements in Bc are permutations of size n drawn from the population of size N.

Our basic assumption is that the elements of the sample space are equally likely. Thus, the probability of an arbitrary event A is simply the ratio of the number of elements in A to the number of elements in S:

P(A) = #(A) / #(S).

The counting that we need to do for the birthday problem is easy, using the multiplication principle of combinatorics.

Thus, P(Bc) = (N)n / Nn and hence the probability of the birthday event B is

P(B) = p(N, n) = 1 − (N)n / Nn.

The fact that the p(N, n) = 1 for n > N is an example of the pigeonhole principle: if more than N pigeons are placed into N holes then at least one hole has 2 or more pigeons.

The Birthday Problem Applet

The applet at the top of the page simulates the birthday experiment. The population consists of balls, numbered from 1 to N. The balls in the sample are colored green, except when a ball duplicates a previous ball; in this case the duplicate is colored red. The parameters of the problem, the population size N and the sample size n, can be varied with scrollbars. An indicator variable I indicates on each run whether or not the birthday event B occurs. As you run the experiment, the values of I are recorded in the first table (1 if B occurs and 0 if it does not). The graph shows the probability of the event and its complement in blue. As the experiment runs, the relative frequency of the event and its complement are shown in red. The second table gives the same information as the graph, but in numerical form.

Simulation Exercise 1. Try running the applet with various values of N and n. Make sure that you understand the information that is being displayed.

Mathematical Exercise 2. Let N = 365 (the standard birthday problem). Simplify numerically to verify the following:

  1. p(365, 10) = 0.117
  2. p(365, 20) = 0.411
  3. p(365, 30) = 0.706
  4. p(365, 40) = 0.891
  5. p(365, 50) = 0.970
  6. p(365, 60) = 0.994

The graph of p(365, n), as a function of n, (smoothed for the sake of appearance) is given below.

Probability of a duplication

Simulation Exercise 3. In the birthday experiment, set N = 365. For n = 10, 20, 30, 40, 50, and 60 run the experiment 1000 times each with an update frequency of 10. Note the apparent convergence of the relative frequencies to the probabilities.

In spite of its easy solution, the birthday problem is famous because, numerically, the probabilities can be a bit surprising. Note that with a just 60 people, the event is almost certain! Mathematically, the rapid increase in p(N, n), as n increases and with N fixed, is due to the fact that the Nn grows much faster than the (N)n.

Mathematical Exercise 4. Ten persons are chosen at random. Find the probability that at least 2 have the same birth week.

Simulation Exercise 5. In the birthday experiment, set N = 52. Vary n with the scrollbar and note graphically how the probability changes. Now with n = 10, run the experiment 1000 times with an update frequency of 10. Note the apparent convergence of the relative frequencies to the probabilities.

Mathematical Exercise 6. Four fair dice are rolled. Find the probability that the scores are distinct.

Simulation Exercise 7. In the birthday experiment, set N = 6. Vary n with the scrollbar and note graphically how the probability changes. Now with n = 4, run the experiment 1000 times with an update frequency of 10. Note the apparent convergence of the relative frequencies to the probabilities.

Mathematical Exercise 8. Five persons are chosen at random. Find the probability that at least 2 have the same birth month.

Simulation Exercise 9. In the birthday experiment, set N = 12. Vary n with the scrollbar and note graphically how the probability changes. Now with n = 5, run the experiment 1000 times with an update frequency of 10. Note the apparent convergence of the relative frequencies to the probabilities.

Mathematical Exercise 10. A fast-food restaurant gives away one of 10 different toys with the purchase of a kid's meal. A family with 5 children buys 5 kid's meals. Find the probability that the 5 toys are different.

Simulation Exercise 11. In the birthday experiment, set N = 10. Vary n with the scrollbar and note graphically how the probability changes. Now with n = 5, run the experiment 1000 times with an update frequency of 10. Note the apparent convergence of the relative frequencies to the probabilities.

Mathematical Exercise 12. Let N = 52 (corresponding to birth weeks). Find the smallest value of n such that the probability of a duplication is at least 1/2.

Simulation Exercise 13. Run the birthday experiment 1000 times with N = 52 and the value of n that you found in the previous exercise. Note the apparent convergence of the relative frequencies to the probabilities.


Home > Birthday Problem | Poker Problem | Needle Problem