Maths IA · Statistics and probability · topic 47 of 97
The birthday problem: how safe are hash codes? · IB Maths IA idea: guide, sample graph and step-by-step plan
match with anyone, not with meIn a room of just 23 people, the chance that two share a birthday is already about one half. The same arithmetic decides how long a digital fingerprint must be. Your job is to explain why the number is so small and then use it.
- ✓ you like results that feel wrong until you calculate them
- ✓ you want to turn a quick approximation into a result you can defend
- ✓ you are curious how a digital fingerprint can fail
The big idea
The chance that n people all have different birthdays is a product: 365/365 × 364/365 × 363/365 and so on. Subtract it from 1 for the chance of a match. That is exact but awkward. Replace each factor 1 − i/N by e^(−i/N), which comes from the first term of the Maclaurin series for ln(1 − x), and the product collapses to e^(−n(n−1)/2N). Test how good that is, not just whether it looks right. Now let N be the number of possible values of a hash code, which is 2^b for a b-bit code. A clash is likely after about √N items, so the code gives only about b/2 bits of protection against collisions. Real birthdays are not evenly spread, which changes the answer. Decide what to include and defend it.
Make it yours: pick one twist
Copying a classic won't show your choices. Pick one of these (or invent your own) and your IA becomes yours.
Swipe for more twists →
Take logs of the product, replace each ln(1 − i/N) by its Maclaurin series, and sum the first one or two terms.
→ A chain of justified steps, with the error of each term estimated. At HL, show the next term and measure how much it improves the result.Solve e^(−n²/2N) = ½ for n and compare with exact values for several N.
→ A formula n ≈ 1.18√N that you test against exact calculations, with a measured error.For a b-bit hash, find how many items give a 50% and a 1-in-a-million chance of some collision.
→ Logarithms turn huge numbers into usable bit counts. State what b you would need for a given use.Use real birth statistics for a country and compute the chance of a match with unequal probabilities.
→ The equal-chance model meets data. Show whether unevenness raises or lowers the match chance, and by how much.Draw many random groups, estimate the match probability and compare it with your formulas.
→ A check that does not rely on your algebra. Give a margin of error for the simulated values.Find how large a group must be for three people to share a birthday.
→ The product no longer works, so you need a new model or a simulation. Say what changes and why.Your Maths IA research question: run the check
which N? which chance?Write your own question first. Then make sure it ticks every box:
- Names the model: the number of possible values N and the assumption that they are equally likely, or a stated alternative.
- Names the quantity you find: a probability, the size of group for a given chance, or the bits of protection.
- Says how the approximation is tested: exact values, simulation or real data.
- Includes a step that is justified, not just calculated: the series, the error or the solved equation.
- States what you leave out: leap days, twins, seasonal birth patterns and the way real hash functions are attacked.
The model
Inputs go through a function into one of N possible values. A clash is two different inputs in the same slot. Draw your own with the value of N you will test.
How your Maths IA could be laid out
The usual order for a topic like this, what each part needs to show, and roughly how much of your 12 to 20 pages it takes. The words are all yours.
What a collision is, where it matters, and what you expect before calculating.
The product for no match, defined with every symbol, checked against a small case by listing outcomes.
Logs, the Maclaurin series, the collapsed formula, and the error measured against exact values.
Replace 365 by N = 2^b, find the √N rule and what it says about the length of a hash code.
Real birth data or a simulation, and what changes when the values are not equally likely.
Back to your aim: the exact value, the approximation and the rule for sizing a code.
Equal-chance and independence assumptions, the cost of approximating, and how real attacks differ. Say which assumption matters most.
Where every dataset and result came from.
What your Maths IA graph could look like
mark the 50% levelMade-up values to show the form of a strong graph, not the answer: the match probability against group size, exact and approximate on one set of axes. Yours will use your own N. example only
- Exact and approximate values on one set of axes, so the gap is visible.
- Axis labels give units: a count of people and a probability.
- Mark the 50% level and read the group size off, then calculate it.
- A second graph of the relative error shows where the approximation is weakest.
- Another graph to consider: group size for 50% against N on log-log axes.
The maths in action
worked through, not sketched!The graph above was a sketch with made-up numbers. This figure works the idea through from the model itself, so you can see what a finished figure looks like. The source line under it says where every number comes from.
How fast does a match become likely?
Work out the chance of a shared birthday for several group sizes and explain why it climbs so quickly at first and then levels off.
Your game plan
Tick steps off as you go. We'll remember on this device.
0 of 10 done
- Read and predictBefore any calculation, guess how many people give a 50% chance of a shared birthday. Write the guess down.
- Set up the modelState your assumptions: 365 equally likely days, independent birthdays. Define the event 'no two share' and write its probability as a product.
- Check small casesCompute n = 2 and n = 3 by listing outcomes, and compare with your product. Fix any slip now.
- Trial run (1 lesson)Build a table of exact probabilities for n = 1 to 60 in a spreadsheet or program, and find where it first passes one half.
- Derive the approximationTake logs, use the Maclaurin series of ln(1 − x) and sum the resulting series. Write the formula and show the steps.
- Measure the errorCompare exact and approximate values over a range of n. Find the largest relative error and say where it is.
- Move to hash codesPut N = 2^b in your formula and find the number of items for a 50% chance. Compare with simulated collisions on a small b.
- Go further, with a reasonTest unequal probabilities with real data, or go to three-way matches. HL: use a second series term and bound the error.
- Reflect as you goAfter every result, write one line on what it means and what it assumes. These lines become your evaluation.
- Cut, check, then sendCheck every graph has labelled axes, every symbol is defined once and the conclusion answers your aim. Then send your teacher one draft.
The maths you'll use
- Probability of the complement – Write the chance of no match as and subtract from 1; check small cases by listing outcomes.
- Logarithms and series – Take of the product, use from the Maclaurin series, and sum an arithmetic series.
- Exponential equations – Solve for to get about .
- Approximation error – Compute the relative error against exact values and compare one-term and two-term series.
- Simulation – Simulate random groups to estimate probabilities and give a margin of error for them.
Key equations
Syllabus links
- 1.7Rational exponents and laws of logarithms
- 2.9Exponential and logarithmic functions
- 4.5Basic probability and expected frequency
- 5.19Maclaurin seriesHL
- 1.6Approximation, bounds and percentage error
- 4.5Basic probability and expected frequency
- 4.6Venn and tree diagrams, conditional probability
- 4.12Designing data collection; reliability and validityHL
Read up first
- Probability (AA HL) →
- Maclaurin series (AA HL) →
- Exponentials and logarithms (AA HL) →
- Approximation and error (AI HL) →
Data and sources to start from
Exact calculation and simulation, with national birth statistics (births per day of the year) to test the equal-chance assumption.
- CDC National Center for Health Statistics (United States births)
- Office for National Statistics (UK births)
- The first collision for full SHA-1 (project page)
References to cite
- Feller, W. (1968). An introduction to probability theory and its applications (Vol. 1, 3rd ed.). Wiley.
- Stevens, M., Bursztein, E., Karpman, P., Albertini, A., & Markov, Y. (2017). The first collision for full SHA-1. In Advances in Cryptology: CRYPTO 2017. Springer.
- Diaconis, P., & Mosteller, F. (1989). Methods for studying coincidences. Journal of the American Statistical Association, 84(408), 853-861.
Cite what you actually use, in your own format, and say where each number came from.
Traps to avoid in this Maths IA
measure the error!- Calculating the chance that someone shares your birthday. That is a different and much smaller probability.
- Writing the approximation without saying where it comes from or how large its error is.
- Using n² instead of n(n − 1), and then not noticing a small difference for small n.
- Treating 'a collision is likely' as meaning 'a given hash can be attacked'. The attacker also has to choose the inputs.
- Leaving out the equal-chance assumption, or claiming real birthdays satisfy it without checking.
- Reporting a simulation result with no number of trials and no margin of error.
More Maths IA ideas like this
RSA: why can nobody read your messages?●●●
How many confirmations are safe? The double-spend race●●●
Benford's law: does your data follow it?●●○
Check digits: how do barcodes catch mistakes?●●○
This guide shows how a topic like this is usually approached. It is not an IA. Your question, choices, data, analysis and words must be your own: change something, tell your teacher where the idea came from, and follow your school's rules on outside help.