Lecture 3: Birthday Problem, Properties of Probability | Statistics 110

The speaker begins by introducing the Birthday Problem, a classic probability scenario that is often surprising to those unfamiliar with it. They explain that the problem involves determining the likelihood of at least two people in a group sharing the same birthday. The importance of the problem in probability theory is emphasized, and the speaker expresses their intention to delve into how one should think about and approach the problem, rather than just providing an answer.

The speaker outlines the assumptions necessary for solving the Birthday Problem, such as excluding February 29th and assuming that each of the 365 days is equally likely for a birthday. They also assume independence, meaning one person's birthday does not affect another's. The speaker then sets up the problem mathematically, considering a group of K people and aiming to find the probability of at least two having the same birthday. They touch upon the similarity of this problem to the robberies problem previously discussed in class.

To solve the Birthday Problem, the speaker decides to first calculate the probability of no matches, which is easier to compute. They use the naive definition of probability, given the assumptions of equally likely birthdays. The calculation involves multiplying the number of days available for each subsequent person's birthday, after excluding the birthdays already taken by those before them in the group. The formula for the probability of no match is derived, and the speaker emphasizes the importance of being careful with the number of terms in the product.

The speaker discusses the intuitive understanding of the Birthday Problem when the number of people K exceeds 365, noting that the probability of a match is 100%. They also highlight the relevance of the problem in computer science, particularly in data structures and the occurrence of collisions. The speaker then shares common misconceptions about the number of people needed to reach a 50/50 chance of a birthday match and reveals the surprising answer that only 23 people are needed.

The speaker provides the mathematical computation for the probability of a birthday match as people are added to the group, starting from 23 people and moving up to 50 and then 100. They show that the probability increases significantly as the group size grows. The speaker then offers insight into why the probability is so high with a relatively small number of people, emphasizing the importance of considering the number of pairs rather than just the number of individuals.

The speaker extends the Birthday Problem to consider not just matches but also near-matches, where people have birthdays one day apart. They state that with this new condition, only 14 people are needed to reach a better than 50/50 chance of a coincidence, which is even more surprising. The speaker acknowledges that proving this result is more complex and promises to cover approximation methods for such problems later in the course.

The speaker transitions back to the non-naive definition of probability, which involves two axioms. They review the axioms: the probability of the empty set is 0, and the probability of the full sample space is 1. The speaker also discusses the concept of events as sets and the importance of understanding that the probability of a union of events equals the sum of their individual probabilities, provided the events are disjoint.

The speaker outlines several properties of probability that can be derived from the axioms. They start with the fact that the probability of the complement of an event A equals 1 minus the probability of A. They then discuss the property that if an event A is contained within event B, the probability of A is less than or equal to the probability of B. The speaker also introduces a more complex property regarding the probability of the union of two events, which involves adjusting for the overlap between the events.

The speaker introduces the inclusion-exclusion principle, a method for calculating the probability of the union of more than two events. They explain the principle using the example of three events and then generalize it for n events. The formula involves summing the probabilities of the individual events, subtracting the probabilities of their intersections, and so on, with alternating signs. The speaker emphasizes the utility of this principle in various probability problems.

The speaker presents de Montmort's problem, a classic probability puzzle related to a card game. The game involves turning over cards in sequence and matching their position in the deck with their numerical value. The speaker outlines the problem and indicates that inclusion-exclusion is a suitable method for finding the probability of at least one match occurring in the deck. They set up the problem for solution, defining the events and preparing to apply the inclusion-exclusion principle.

The speaker simplifies the calculations for de Montmort's problem by taking advantage of the symmetry in the game. They calculate the probability of a single match and then the probability of double matches, using factorials to represent the possible arrangements of the deck. The calculations are shown to simplify significantly due to the symmetry and the structure of the problem, leading to a clear pattern in the results.

The speaker concludes the discussion by noting that the exact answer to the probability calculation in de Montmort's problem results in an alternating sum that resembles the Taylor series for e^x. They express surprise at the appearance of the mathematical constant e, highlighting the unexpected connections that can emerge in probability problems. The speaker ends with a reminder of the importance of understanding the underlying concepts and techniques.