Fundamentals of Probability

Videos

Reading

Connecting Discrete Mathematics and Computer Science by David Liben-Nowell, Chapter 10, pages 1-42

Warmup

Problem 1

Imagine that we form a string of \(5\) characters, with each character chosen randomly and independently from the set \(\{a, b, c, d, e, f\}\). We might get a random string like \(adcca\) or \(fbfcd\).

Please answer the following questions:

Part A

Consider the strings \(aaaaa\) and \(cddeb\). Which of these two strings is more likely to occur from this process, and why?

Part B

What is the probability of obtaining a string which contains no repeated characters?

Part C

What is the probability of obtaining a string which does not contain the substring \(bad\)?

Problem 2

Prove the following theorem:

Let \(A_1, A_2, \ldots, A_n\) be some collection of events. Then,

\[ \begin{aligned} \mathbb{P}\left(\bigcup_{i=1}^n A_i\right) \leq \sum_{i=1}^n \mathbb{P}(A_i). \end{aligned} \]

Hint: The notation \(\bigcup_{i=1}^n A_i\) means \(A_1 \cup A_2 \cup \ldots \cup A_n\) (similar to summation or product notation).

Hint: Use induction on \(n\), the number of events.

Problem 3

Here is a list of probabilities describing the likelihood that a person in the UK was born in each of the 12 months of the year:

probs = [0.083, 0.078, 0.081, 0.081, 0.085, 0.083, 0.087, 0.086, 0.086, 0.084, 0.082, 0.083]
months = ["Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"]

For example, there is an 8.3% chance that a UK individual was born in January, a 7.8% chance that they were born in February, etc.

I compiled this data from a chart produced by Niall McCarthy on the website Statista. Technically, the data describes UK residents born during the 20-year period 1995-2014.

You may answer the following two questions using any tools you wish, although my advice is to write short Python programs.

Part A

Suppose that two random citizens of the UK (born between 1995-2014) meet each other on the street. What is the probability that they were born in the same month?

Part B

Suppose that two people meet and tell you that they have the same birthmonth. What is the probability that their birthmonth is April, given this information?

Part C

Suppose that someone tells you that they share a birthmonth with the first random person they met on the street today. Does that make it more, less, or equally likely that they were born in April?

Part D

Are the events “being born in April” and “sharing a birthmonth with the first person you meet on the street” independent?



© Phil Chodrow, 2024