diff options
Diffstat (limited to 'content')
| -rw-r--r-- | content/articles/the-birthday-paradox.md | 303 | ||||
| -rw-r--r-- | content/posts/2021-11-11-the-birthday-paradox.md | 56 |
2 files changed, 359 insertions, 0 deletions
diff --git a/content/articles/the-birthday-paradox.md b/content/articles/the-birthday-paradox.md new file mode 100644 index 0000000..1ab1e07 --- /dev/null +++ b/content/articles/the-birthday-paradox.md @@ -0,0 +1,303 @@ +--- +slug: the-birthday-paradox +title: "The Birthday Paradox" + +# date (optional for articles) +date: "2021-11-11T06:46:00-04:00" + +# draft articles are not visible on live site +draft: true + +# show on articles page +show: true + +# uncomment to show table of contents +toc: true + +tables: + probs: + cols: + - id: num_people + name: Number of People + tip: Number of people in room. + - id: probability + name: Probability + tip: Probability that at least two people in a room with this many people share a birthday. + - id: percent + name: Percent + tip: Probability represented as a percentage. + align: right + rows: + - num_people: 1 + probability: 0.0 + percent: 0.00% + - num_people: 2 + probability: 0.00273 + percent: 0.27% + - num_people: 3 + probability: 0.0082 + percent: 0.82% + - num_people: 4 + probability: 0.01635 + percent: 1.64% + - num_people: "..." + - num_people: 22 + probability: 0.47569 + percent: 47.57% + - num_people: 23 + probability: 0.50729 + percent: 50.73% + _css: has-text-weight-bold has-background-info-light + - num_people: 24 + probability: 0.53834 + percent: 53.83% + _css: has-text-weight-bold has-background-info-light + - num_people: 25 + probability: 0.56869 + percent: 56.87% + _css: has-text-weight-bold has-background-info-light +--- + +## Introduction + +I share my birthday with my mom. Yesterday while talking her on ~~my~~ +her birthday I asked if she had heard of the [Birthday Paradox][bp] +(also known as the [Birthday Problem][bp]). + +The [birthday problem][bp] goes like this: + +> How many people have to be in a room before the probability that two +> people in the room share a birthday is greater than 50%? + +Even if you already know the answer, the [birthday problem][bp] is a fun +puzzle because: + +* The answer is counterintuitive (hence the name *birthday paradox*). +* The solution relies on elements of [combinatorics][], [set theory][], + and [probability][]. +* The implications affect security, particularly [cryptographic + hash algorithms][hash]. + +The next section covers the math that you'll need. If you're already +familiar with [probability][], feel free to skip to [Solving the +Birthday Problem][solving]. + +## Probability Crash Course + +Before we get started on the solution to the [Birthday Problem][bp], +here is a brief crash course in [probability][]: + +1. The expression `N!`, where `N` is a non-negative integer, is called a + [factorial][], and it is means "the product of all the numbers from + `N` to `1`". So `5! = 5 × 4 × 3 × 2 × 1 = 120`. To make our lives + easier, `0!` is defined to be `1`. +2. In [probability][], an occurance is called an *event*, and the + probability of an *event* `A` is denoted `P(A)`. +3. The value of a probability is a real number between `0` and `1`, + inclusive (written `P(A) ∈ [0, 1]`). Inclusive means that `0` and + `1` are valid probabilities, where `0` means "this event is + impossible" and `1` means "this event will occur with certainty". +4. You can convert a probability to a percentage by multiplying by + `100` and appending a trailing `%`. So `P(A) = 0.1` means `10%`, + `P(A) = 0.2` means `20%`, and so on. +5. The probability of two [independent][] events `A` and `B` both + occurring is written `P(A ⋂ B)` and read as "the [joint + probability][] of A and B". The value is calculated as `P(A) × + P(B)`. This pattern of multiplication continues, so the probability + of three [independent][] events `A`, `B`, and `C` occurring is `P(A ⋂ + B ⋂ C) = P(A) × P(B) × P(C)`, and so on. The upside-down U symbols + represent an [intersection][intersection]. +6. The probability of an event `A` **not** occurring is written `P(¬A)` + and calculated as `1 - P(A)`. This is useful because sometimes it + is much easier to calculate the probability that an event will not + occur, as we'll see below. + +Here's what all chicanery above like visually: + +{{< figure + src="/files/articles/birthday-paradox/probability-basics.svg" + class="image" + width=492 + height=556 + caption="Visual representation of probability basics." +>}} + +To calculate a [discrete][] (countable) probability, you sum up all the +matching events, then divide the sum by the total number of possible +events. + +For example, if you put one red marble and three blue marbles in a jar +and then randomly choose a single marble out of the jar, then the +probability that you will choose the red marble is: + +``` +P(R) = probability of choosing a red marble +P(R) = number of red marbles / total number of marbles +P(R) = 1/(1 + 3) = 0.25 = 25% +``` + +Here's a more complicated example: Let's say you put 3 red marbles and 5 +blue marbles in a jar, pick a marble from the jar at random, and then +roll a fair, [6-sided die][die]. What is the probability that you will +pick a red marble from the jar **and** roll a 5 or a 6 on the [die][]? + +``` +P(R) = probability of choosing a red marble +P(R) = number of red marbles / total number of marbles +P(R) = 3/(3 + 5) = 0.375 = 37.5% + +P(D) = probability of rolling a 5 or a 6 on the die +P(D) = number of matching die faces / total number of die faces +P(D) = 2/6 = ~0.333 = ~33.3% + +P(R ⋂ D) = P(R) × P(D) +P(R ⋂ D) = 3/8 × 1/3 = 0.125 = 12.5% +``` + +## Solving the Birthday Problem + +Let's get back to the problem at hand. I'll save you a bit of time and +a lot of headache by telling you now that the [birthday problem][bp] is +one of those pesky probability problems where it easier to calculate the +opposite; that is, the [probability][] that everyone in the room has a +*unique* birthday. + +Now that that piece of bookkeeping is out of the way, let's get started. + +Ff there is one person in the room, then the probability that everyone +has a unique birthday is `1.0` (`100%`). + +``` +P1 = P(one person) = 365/365 +P1 = 1.0 = 100% +``` + +If there are two people in the room, the probability that everyone has a +unique birthday can be calculated by multiplying the probability from +the previous step by the probability that the second person's birthday +is not the same as the first person's birthday. Algebraically: + +``` +P2 = P(second person has a unique birthday) +P2 = P1 × 364/365 +P2 = 365/365 × 364/365 = (365 × 364)/(365^2) = 364/365 +P2 = ~0.9972 = 99.7% +``` + +When we a third person, a pattern begins to emerge: + +``` +P2 = P(third person has a unique birthday) +P3 = P2 × 363/365 +P3 = 365/365 × 364/365 × 363/365 = (365 × 364 × 363)/(365^3) +P3 = ~0.9917 = ~99.2% +``` + +Do you see the pattern? + +The probability that everyone in a room of `N` people has a unique +birthday is the product of the numbers between `365` and `365 - N` +(inclusive), divided by `365^N` (365 to the Nth power). In other words: + +``` +B(N) = P(everyone in a room of N people has a unique birthday) +B(N) = 365!/((365 - N)! * 365^N) +``` + +At this point you can continue and find a precise algebraic solution, +but often for discrete propabilities it's convenient to write a script +to do the work for you. + +So I wrote a [Ruby][] script which uses the complement of the algorithm +derived above to calculate the probability of shared birthdays in a room +containing `N` for `N ∈ [1, 50]`, and render the results as a table and +a chart. + +The full script a bit unwieldy for this article, but it is available in +the [GitHub repository for this article][github]. + +Here is the portion of the script for the derived equasion: + +```ruby +# memoize 365! +F365 = 365.factorial + +# +# Return the probability that at least one pair of people in a room of N +# people share a birthday. +# +# (This is the formula that we derived in the original article). +# +def shared_birthdays(v) + 1 - F365 / (365 - v).factorial * (365 ** -v) +end +``` + + +Below is are the script results with the relevant chart bars and table +rows highlighted: + +{{< figure + src="/files/articles/birthday-paradox/people-vs-probability.svg" + class="image" + width=614 + height=461 + caption="Number of People versus Probability of Shared Birthday." +>}} + +{{< table "probs" >}} + +So the answer to the birthday problem is as follows: **If there are 23 +people in the room, then the probability of at least one shared birthday +is greater than 50%**. + +## Implications + +This result is called the *birthday paradox* is because it doesn't feel +intuitive. When asked, most people will guess that a much higher +number of people (50 or 130) are needed before the probability is +greater than 50%. + +*TODO:* segue into hash algorithms. + +## Further Reading + +* [GitHub repository for the scripts used in this article][github] +* [The Birthday Problem (Wikipedia)][bp] + +[bp]: https://en.wikipedia.org/wiki/Birthday_problem + "The birthday problem." +[combinatorics]: https://en.wikipedia.org/wiki/Combinatorics + "The mathematics of counting." +[set theory]: https://en.wikipedia.org/wiki/Set_theory + "The mathematics of sets." +[probability]: https://en.wikipedia.org/wiki/Probability + "The mathematics of determining how likely an event is to occur." +[hash]: https://en.wikipedia.org/wiki/Cryptographic_hash_function + "Cryptographic hash algorithm." +[intersection]: https://en.wikipedia.org/wiki/Intersection_(set_theory) + "Intersection." +[independent]: https://en.wikipedia.org/wiki/Probability#Independent_events + "Independent events in probability theory." +[discrete]: https://en.wikipedia.org/wiki/Random_variable#Discrete_random_variable + "A random value with a countable number of possible values." +[joint probability]: https://en.wikipedia.org/wiki/Joint_probability_distribution#Coin_flips + "Joint probability." +[die]: https://en.wikipedia.org/wiki/Dice + "Dice." +[factorial]: https://en.wikipedia.org/wiki/Factorial + "Factorial unary operator." +[ruby]: https://ruby-lang.org/ + "Ruby programming language." +[csv]: https://en.wikipedia.org/wiki/Comma-separated_values + "Comma-separated values." +[html]: https://en.wikipedia.org/wiki/HTML + "HyperText Markup Language" +[yaml]: https://en.wikipedia.org/wiki/YAML + "YAML Ain't a Markup Language" +[hugo-table-shortcode]: https://github.com/pablotron/hugo-shortcode-table + "Table shortcode for Hugo." +[github]: https://github.com/pablotron/birthday-paradox + "GitHub repository for scripts used in this article." +[solving]: #solving-the-birthday-problem + "Solving the Birthday Problem" diff --git a/content/posts/2021-11-11-the-birthday-paradox.md b/content/posts/2021-11-11-the-birthday-paradox.md new file mode 100644 index 0000000..df1abd6 --- /dev/null +++ b/content/posts/2021-11-11-the-birthday-paradox.md @@ -0,0 +1,56 @@ +--- +slug: the-birthday-paradox +title: "The Birthday Paradox" +date: "2021-11-11T06:46:00-04:00" +draft: true +--- +> How many people have to be in a room before the probability that two +> or more people in the room share a birthday is greater than 50%? + +This is called the [Birthday Problem][bp], and the solution is known as +the *birthday paradox*. It is a fun puzzle because: + +* The answer is counterintuitive (hence the name *birthday paradox*). +* The solution relies on elements of [combinatorics][], [set theory][], + and [probability][]. +* The implications affect security, particularly [cryptographic + hash algorithms][hash]. + +The explanation started as a blog post but got too long, so I moved it +to a full article instead. You can read the full article at the +following link: + +[The Birthday Problem][bp] + +[bp]: {{< relref "/content/articles/the-birthday-paradox.md" >}} + "The birthday problem." +[combinatorics]: https://en.wikipedia.org/wiki/Combinatorics + "The mathematics of counting." +[set theory]: https://en.wikipedia.org/wiki/Set_theory + "The mathematics of sets." +[probability]: https://en.wikipedia.org/wiki/Probability + "The mathematics of determining how likely an event is to occur." +[hash]: https://en.wikipedia.org/wiki/Cryptographic_hash_function + "Cryptographic hash algorithm." +[intersection]: https://en.wikipedia.org/wiki/Intersection_(set_theory) + "Intersection." +[independent]: https://en.wikipedia.org/wiki/Probability#Independent_events + "Independent events in probability theory." +[discrete]: https://en.wikipedia.org/wiki/Random_variable#Discrete_random_variable + "A random value with a countable number of possible values." +[joint probability]: https://en.wikipedia.org/wiki/Joint_probability_distribution#Coin_flips + "Joint probability." +[die]: https://en.wikipedia.org/wiki/Dice + "Dice." +[factorial]: https://en.wikipedia.org/wiki/Factorial + "Factorial unary operator." +[ruby]: https://ruby-lang.org/ + "Ruby programming language." +[csv]: https://en.wikipedia.org/wiki/Comma-separated_values + "Comma-separated values." +[html]: https://en.wikipedia.org/wiki/HTML + "HyperText Markup Language" +[yaml]: https://en.wikipedia.org/wiki/YAML + "YAML Ain't a Markup Language" +[hugo-table-shortcode]: https://github.com/pablotron/hugo-shortcode-table + "Table shortcode for Hugo." |