The Birthday Paradox
Solving the 'Birthday Paradox' with a 'Probability Tree'
The Birthday Paradox: How many people do you need in a room, before the probability is greater
than 50% that at least two people in the group share the same birth date?
Assume that birth dates are 100% random (so uniformly distributed throughout the entire year)
and that a year is 365 days.
Answer: The answer is "23 people", resulting in a probability of 50.73% that someone shares
a birthday with another person in the group.
More from Wikipedia.
But this number of people at first glance seems way 'too small' -- hence the 'paradox'.
Note that this is NOT the probability of someone having the same birthday as YOU,
but rather, it is the probability that there is some common birthday in the
entire group of people.
Using a 'probability tree' is a great way to figure out the answer and visualize the solution!
First, what is a probability tree? A probability tree is a great way to visualize all possible
outcomes, and compute of probability of each outcome.
Consider flipping a fair coin twice -- the probability tree for this 'event' looks like:
Notice the following 'facts' about probability trees:
- The sum of all probabilities for lines exiting a node in the tree must equal "1" (in other words, all possible outcomes
are documented in the tree).
- The probability of any event (circle/node) happening is the probability of all lines to that point multiplied together. Namely
the probability is getting heads followed by heads is 1/2 × 1/2, or 1/4.
- The sum of all probabilities of all terminal nodes (eg: in blue above) must equal 1.
- The tree can be 'pruned' (no more leaf nodes) at any point (while other parts of the tree grow) without
impacting other probability tree properties.
The 'Probability tree' for the 'birthday paradox': To build the 'birthday paradox' probability tree, start with
one person in the room.
Then, what is the probability the second person entering the room will have the same birth date as
the first person? The answer is 1/365 (the first blue node in the tree). But this means that 364/365 of
the time, there is still not a birthday collision.
Next, extend by adding a third person. What is the probability that third person will have the same birth
date of any of the first two people? It is 2/365 (second blue node in the tree)? But 363/365 of the time,
there still is no birthday collision.
Repeat this process over and over to build a probability tree, similar to:
The probability of reaching any particular node (circle) in the probability tree is obtained by multiplying
all probabilities along the path to that specific node.
TIP: To help calculate probabilities, build this 'tree' in a spreadsheet.
Each blue node represents a collision in birthdays and the red node represents that there was NO collision in birthdays.
The Goal Achieved:
The entire reason for showing this probability tree is to clearly see and understand that there are TWO
ways of figuring out the birthday paradox probability -- the direct way, and the indirect way.
The DIRECT way: Add up all the probabilities of reaching every blue node, until
you get an answer over 50%, which happens on level 23:
1/365 + 364/365×2/365 + 364/365×363/365×3/365 + ... = 50.73%
The INDIRECT way: Leverage the fact that all terminal nodes in a
probability tree must add up to 1. For the tree above, that means that the probability of all the blue nodes,
plus the one red node, must add up to 1. OR, restating this fact:
the sum of all blue nodes is equal to 1 minus the probability of the red node.
The level 23 answer is:
1 - (364/365 × 363/365 × 362/365 × ... × 344/365 × 343/365) = 50.73%
Why this exercise? Because most solutions to the 'birthday paradox' just blindly state the second indirect
way as the solution. But knowing how to (easily) compute the answer DIRECTLY, using a probability
tree, hopefully should expand your knownledge of how to approach and figure out even very
complex probabilities yourself.
CHALLENGE: A true birthday paradox: You are a bouncer at a club with an infinite number of
rooms and an infinite number of people in line. You keep placing people into a new room until that
room has two people with the same birthday. Then you close off the room and start filling the next
room. What is the average number of people that you will place into each room?
HINT: The answer, interestingly, is not 23.
Copyright © 2023-2025 Duckware
|
|
