Birthday Problem

1. Consider the Birthday Problem. In this problem we calculate the probability that, in a group of n people, at least two have the same birthday. Let E be the event that at least two people share a birthday. In order to calculate P(E), we first need a sample space. A possible sample space consists of n-tuples of the integers 1 . . . 365 (each of n people have a birthday on one of the 365 days of the year; leap years are not considered).
(a) List or otherwise describe the sample space for n = 200. What is the size of the sample space?
(b) For n = 200, propose an algorithm for enumerating the number of tuples in the sample space which satisfy the condition that at least two people have the same birthday. You do not need to code and run the algorithm; just describe it in words or pseudo-code. Note that your algorithm will need to scan each tuple.
(c) Say you have access to one of the fastest computers currently available in the world, benchmarked at 33.86-petaflops (33.86 × 1015 floating point operations per second), and say that a scan of a single tuple in your algorithm uses 1 floating point operation. (You will learn about floating point operations in a later course; for now, rest assured this is an underestimate for the cost required to scan a tuple.) For n = 200, how many seconds will your algorithm use to process all of the tuples in the sample space? How many days? How many years?
2. The results of the previous question should make it clear that solving the birthday problem by scanning the sample space is not computationally feasible for n = 200. In fact, scanning the sample space is not computationally feasible for n much smaller than 200. Fortunately, as we saw in lecture, the problem can be solved easily by first computing the complement probability P(E) . . . the probability that everyone has a distinct birthday. Then P(E) = 1 − P(E). For n = 3, the sample space of approximately 49 million tuples is small enough that it could be scanned. However, for n = 3 the problem could also be solved directly with counting principles. Calculate P(E) for n = 3 using counting principles, and confirm that it is the same as 1 − P(E).
3. Repeat #2 for n = 4. Comment on the complexity of computing P(E) using counting principles as n increases.
4. Consider a variation of the birthday problem: “what is the probability that in a group of n people, at least three have the same birthday?” as with the original birthday problem, for large n is not computationally feasible to solve this variation by setting up and scanning the sample space, nor by using counting principles. However, this variation can easily be solved using complement probability. Solve this variation of the birthday problem using complement probability.