WEBVTT

00:00:00.046 --> 00:00:02.879
Twenty three people sounds far
too small for a shared birthday

00:00:02.879 --> 00:00:04.610
to be more likely than not.

00:00:04.714 --> 00:00:08.395
That reaction is sensible,
but it is counting the wrong thing.

00:00:08.707 --> 00:00:12.444
The birthdays are not compared
with the calendar one person at a time.

00:00:12.527 --> 00:00:15.512
They are compared
with one another, pair by pair.

00:00:16.815 --> 00:00:18.546
Start with three people.

00:00:18.743 --> 00:00:23.666
Each blue dot is one person, and each
yellow line will represent one question:

00:00:23.863 --> 00:00:26.847
do the two people
at its ends share a birthday?

00:00:27.551 --> 00:00:30.254
The first person
can be compared with the second.

00:00:30.337 --> 00:00:32.961
The first can also
be compared with the third.

00:00:33.158 --> 00:00:35.968
Finally, the second
can be compared with the third.

00:00:36.165 --> 00:00:39.091
Three people already
make three distinct pairs.

00:00:39.795 --> 00:00:41.677
Now add a fourth person.

00:00:41.873 --> 00:00:44.530
That newcomer creates
three fresh comparisons,

00:00:44.613 --> 00:00:46.831
one with everyone already present.

00:00:47.144 --> 00:00:50.454
Add a fifth person
and the newcomer creates four more.

00:00:50.557 --> 00:00:53.553
We added two people,
but we added seven pairs.

00:00:54.350 --> 00:00:56.882
Five people therefore make ten pairs.

00:00:57.078 --> 00:01:01.677
In general, n people each appear
in n minus one comparisons.

00:01:01.874 --> 00:01:06.727
That counts every pair twice, once
from each end, so we divide by two.

00:01:08.240 --> 00:01:12.592
Now put twenty three people around
the circle. The dots still look sparse.

00:01:12.675 --> 00:01:15.532
That is the picture our intuition notices.

00:01:15.728 --> 00:01:19.212
But every dot must be compared
with every other dot.

00:01:19.637 --> 00:01:23.780
The formula gives twenty three
times twenty two, divided by two.

00:01:23.863 --> 00:01:25.800
That is two hundred fifty three.

00:01:25.883 --> 00:01:29.924
Here is every comparison
the birthday question is actually making.

00:01:30.628 --> 00:01:34.959
So the experiment is not twenty three
lonely attempts to hit one special day.

00:01:35.156 --> 00:01:38.791
It is two hundred fifty three
opportunities for some pair to collide.

00:01:39.243 --> 00:01:41.482
We have not proved
the fifty percent claim yet,

00:01:41.565 --> 00:01:44.561
but now the scale of it
should no longer feel absurd.

00:01:45.649 --> 00:01:50.072
To keep the calculation clean, suppose
there are three hundred sixty five equally

00:01:50.072 --> 00:01:54.993
likely birthdays, ignore leap day, and
treat people's birthdays as independent.

00:01:55.076 --> 00:01:57.304
Real birthdays are not perfectly uniform,

00:01:57.387 --> 00:02:00.766
but this model is close enough
to expose the main effect.

00:02:01.907 --> 00:02:05.063
Counting every possible kind
of match directly is messy.

00:02:05.146 --> 00:02:10.000
Two people might match, three might match,
or two separate pairs might match.

00:02:10.104 --> 00:02:14.969
So turn the question around. What is the
chance that every birthday is different?

00:02:15.510 --> 00:02:17.831
The first person can have any birthday.

00:02:17.914 --> 00:02:22.045
For the second person to avoid
a match, only one day is forbidden.

00:02:22.128 --> 00:02:26.413
That leaves three hundred sixty four
safe days out of three hundred sixty five.

00:02:27.465 --> 00:02:31.979
Bring in a third person. Now two
occupied birthdays must be avoided,

00:02:32.062 --> 00:02:34.884
so only three hundred
sixty three days are safe.

00:02:34.988 --> 00:02:38.785
Both conditions must hold,
which is why the fractions multiply.

00:02:39.582 --> 00:02:42.111
Each new person
contributes another fraction,

00:02:42.194 --> 00:02:44.982
with one fewer safe day in the numerator.

00:02:45.085 --> 00:02:49.486
For n people, multiply from three
hundred sixty four over three hundred

00:02:49.486 --> 00:02:54.931
sixty five down to three hundred sixty
six minus n over three hundred sixty five.

00:02:55.728 --> 00:03:00.336
At twenty three people, that product
is about zero point four nine two seven.

00:03:00.419 --> 00:03:03.807
So the chance that everyone
differs is just under one half.

00:03:03.890 --> 00:03:08.790
Subtract from one, and the chance of at
least one shared birthday is about zero

00:03:08.790 --> 00:03:12.668
point five zero seven
three, just over one half.

00:03:14.065 --> 00:03:17.130
Now view every group size on one graph.

00:03:17.327 --> 00:03:19.092
The horizontal axis is the number

00:03:19.092 --> 00:03:23.818
of people, and the vertical axis is the
chance that some pair shares a birthday.

00:03:24.014 --> 00:03:26.302
The dashed line marks one half.

00:03:27.099 --> 00:03:31.442
With ten people, the chance is only
about eleven point seven percent.

00:03:31.546 --> 00:03:35.854
That feels unsurprising, and it gives
us a low starting point on the curve.

00:03:36.557 --> 00:03:38.532
Move to twenty two people.

00:03:38.636 --> 00:03:41.722
The chance has climbed to about
forty seven point six percent,

00:03:41.805 --> 00:03:44.116
still below the dashed half line.

00:03:44.820 --> 00:03:50.428
Add just one more person. That newcomer
does not create one new chance to match.

00:03:50.625 --> 00:03:54.629
They create twenty two new pair
comparisons. At twenty three,

00:03:54.712 --> 00:03:58.915
the probability reaches fifty point
seven percent and crosses the line.

00:03:59.712 --> 00:04:01.709
The rise continues quickly.

00:04:01.813 --> 00:04:04.958
At thirty people the chance
is about seventy one percent.

00:04:05.041 --> 00:04:08.072
At fifty people it
is about ninety seven percent.

00:04:08.175 --> 00:04:10.869
The curve accelerates
because every new arrival is compared

00:04:10.869 --> 00:04:12.832
with everyone already present.

00:04:13.628 --> 00:04:16.123
That is why twenty three is enough.

00:04:16.206 --> 00:04:19.315
It is not large compared
with three hundred sixty five days,

00:04:19.398 --> 00:04:22.197
but it creates two
hundred fifty three pairs.

00:04:22.394 --> 00:04:25.457
The product calculation
and the graph now say the same thing:

00:04:25.540 --> 00:04:28.339
a shared birthday is more likely than not.

00:04:29.452 --> 00:04:32.344
Now ask a question
that sounds almost identical.

00:04:32.541 --> 00:04:37.116
How many people are needed before someone
probably shares my birthday specifically?

00:04:37.312 --> 00:04:40.599
The word my changes
the comparison structure completely.

00:04:41.210 --> 00:04:45.645
With seven people in the room, only
six comparisons matter for my birthday.

00:04:45.749 --> 00:04:48.745
Each yellow line joins
me to one other person.

00:04:49.058 --> 00:04:53.076
Birthdays shared entirely among the blue
people do not answer this question.

00:04:53.872 --> 00:04:57.136
For the original birthday
problem, every pair matters.

00:04:57.332 --> 00:04:59.932
The same seven people
create twenty one comparisons,

00:04:59.932 --> 00:05:03.625
because every person is checked
against every other person.

00:05:04.422 --> 00:05:07.473
The left count grows one
at a time as people arrive.

00:05:07.556 --> 00:05:10.712
The right count grows
by the whole number already in the room.

00:05:10.795 --> 00:05:15.115
That is why the original any-pair
question reaches one half so much sooner.

00:05:16.512 --> 00:05:19.995
Let n mean the number
of other people, not counting me.

00:05:20.308 --> 00:05:24.811
One person fails to match my birthday
with probability three hundred sixty four

00:05:24.894 --> 00:05:26.961
over three hundred sixty five.

00:05:27.158 --> 00:05:30.816
For nobody to match me,
all n people must fail.

00:05:31.613 --> 00:05:32.657
A match becomes more

00:05:32.657 --> 00:05:36.513
likely than not when the no-match
probability falls below one half.

00:05:36.709 --> 00:05:39.636
So we set the shrinking
power below one half.

00:05:40.432 --> 00:05:43.812
Take logarithms to bring
n down from the exponent.

00:05:43.916 --> 00:05:46.747
Because the logarithm
of three hundred sixty four

00:05:46.830 --> 00:05:52.020
over three hundred sixty five is negative,
dividing by it reverses the inequality.

00:05:52.817 --> 00:05:56.486
The result is n greater than
two hundred fifty two point six.

00:05:56.683 --> 00:06:01.246
Since n must be a whole number, we need
two hundred fifty three other people.

00:06:01.350 --> 00:06:04.753
Including me, that is two hundred
fifty four people in the room.

00:06:06.056 --> 00:06:08.309
Put both questions on one graph.

00:06:08.622 --> 00:06:13.011
The horizontal axis now counts
everyone in the room, including me.

00:06:13.463 --> 00:06:16.657
The dashed line is again
a probability of one half.

00:06:17.570 --> 00:06:20.566
The blue curve asks
whether any pair matches.

00:06:20.879 --> 00:06:23.061
It crosses one half at twenty three people

00:06:23.061 --> 00:06:26.661
because those people create
two hundred fifty three pairs.

00:06:27.876 --> 00:06:31.497
The green curve asks whether
someone matches one fixed birthday.

00:06:31.580 --> 00:06:36.512
It rises far more slowly and crosses one
half at two hundred fifty four people,

00:06:36.595 --> 00:06:39.452
meaning two hundred fifty
three comparisons with me.

00:06:40.852 --> 00:06:44.949
So the intuition that twenty three
feels too small was not foolish.

00:06:45.032 --> 00:06:48.304
It was quietly answering the green
question while the birthday paradox

00:06:48.387 --> 00:06:49.851
asks the blue one.

00:06:50.047 --> 00:06:52.602
Always ask which pairs actually count.

00:06:53.752 --> 00:06:56.875
The birthday idea appears
anywhere many objects are assigned

00:06:56.875 --> 00:06:58.791
to a limited set of labels.

00:06:58.988 --> 00:07:05.153
A hash function turns a file, password,
or message into one fixed-size output.

00:07:05.466 --> 00:07:09.681
Two different inputs that receive
the same output create a collision.

00:07:10.896 --> 00:07:13.636
Here are sixteen possible outputs.

00:07:13.740 --> 00:07:16.895
Send in one item,
then a second, a third, and a fourth.

00:07:16.979 --> 00:07:20.092
So far every item
has landed in a different slot.

00:07:21.004 --> 00:07:25.510
Now send in the fifth. It lands
in the same slot as the second item.

00:07:25.962 --> 00:07:28.493
Sixteen slots sounded
generous for five items,

00:07:28.493 --> 00:07:32.290
but five items already create
ten pairs that might collide.

00:07:32.994 --> 00:07:38.091
Suppose a hash has N equally
likely outputs and we try k inputs.

00:07:38.288 --> 00:07:42.546
The number of input pairs
is k times k minus one over two,

00:07:42.630 --> 00:07:45.173
exactly the same pair count as before.

00:07:45.970 --> 00:07:49.767
Each pair has about one chance
in N of sharing an output.

00:07:49.871 --> 00:07:54.562
Combining all those small risks gives this
standard approximation for no collision.

00:07:54.665 --> 00:07:58.788
Subtracting from one gives
the chance of at least one collision.

00:07:59.492 --> 00:08:02.743
Set that collision chance
to one half and solve.

00:08:02.847 --> 00:08:06.792
The result is about one point one
eight times the square root of N.

00:08:06.876 --> 00:08:09.787
The constant matters
for an exact estimate,

00:08:09.871 --> 00:08:12.589
but the memorable fact is the square root.

00:08:13.985 --> 00:08:16.448
The birthday example checks the scale.

00:08:16.644 --> 00:08:20.357
Three hundred sixty five possible
days have a square root near nineteen,

00:08:20.441 --> 00:08:23.100
and the more accurate
crossing is twenty three.

00:08:23.897 --> 00:08:27.992
A sixty four bit hash has two
to the sixty fourth possible outputs,

00:08:28.076 --> 00:08:32.349
but collisions become likely after
roughly two to the thirty second inputs.

00:08:32.546 --> 00:08:36.703
That is about four billion,
far below the number of available outputs.

00:08:37.499 --> 00:08:40.016
For a one hundred twenty eight bit hash,

00:08:40.100 --> 00:08:43.885
the birthday scale is about
two to the sixty fourth trials.

00:08:44.082 --> 00:08:46.436
For a two hundred fifty six bit hash,

00:08:46.520 --> 00:08:49.226
it is about two to the one
hundred twenty eighth.

00:08:49.422 --> 00:08:53.216
Collision resistance therefore provides
roughly half as many security bits

00:08:53.300 --> 00:08:54.950
as the output length.

00:08:55.746 --> 00:09:00.086
That matters when hashes identify
files, support digital signatures,

00:09:00.170 --> 00:09:01.982
or detect duplicates.

00:09:02.178 --> 00:09:04.210
A real design either chooses enough

00:09:04.210 --> 00:09:08.596
output bits to make accidental
collisions fantastically unlikely,

00:09:08.680 --> 00:09:12.616
or includes a clear plan
for handling collisions when they occur.

00:09:14.013 --> 00:09:17.334
Four ideas now hold
the whole lecture together.

00:09:17.531 --> 00:09:20.399
Count comparisons rather than objects.

00:09:20.596 --> 00:09:23.604
Compute the easier
no-collision probability.

00:09:23.707 --> 00:09:28.248
Check whether every pair counts
or only comparisons with one fixed target.

00:09:28.444 --> 00:09:32.984
And expect collisions near the square
root of the number of possible outcomes.

00:09:33.897 --> 00:09:35.243
Twenty three people are enough

00:09:35.243 --> 00:09:38.321
because they do not create
twenty three chances to match.

00:09:38.517 --> 00:09:41.374
They create two hundred fifty three pairs.

00:09:41.687 --> 00:09:43.808
Once that hidden web is visible,

00:09:43.892 --> 00:09:48.317
the birthday result stops being a trick
and becomes an ordinary collision problem.