← All Cracked Math projects
PM-B02NOT STARTEDBEGINNERMATHPYTHONIMPACT ★☆☆☆☆

How short can a git hash be? Birthday bounds tested on real repos

Use only combinatorics to predict how many hex characters a git hash needs to stay unique in the Linux kernel. Then check your prediction against git itself.

EST.4 h
REWARD+200 XP
AFTERgit-config documentation

ML-ARENA BENCHMARKS

PROOF: BENCH
METRICINDUSTRYMINE
How far the predicted shortest unique prefix length is from the observed one, |predicted - observed|; and how well the analytic collision probability agrees with the simulated one
GOAL · Prediction within +/-1 hex char on 5/5 repos. At every prefix length k, the analytic P(collision) must fall inside the 95% CI (confidence interval: the range that should contain the true value 95% of the time, given the simulation's random noise) of a 10^5-trial simulation.
git's own choice under core.abbrev=auto · measured locally—
no results yet
YOUR RESULTS

Your recorded results appear here.

Brief

Git names every object with a long hex hash and usually shows only its first few characters (a prefix). Work out the chance that two of n objects share the same k-hex-character prefix. Derive both the exact collision probability and the standard approximation 1 - e^(-n^2/2N), where N = 16^k is the number of possible prefixes. Compute everything in log space (work with logarithms of probabilities so very small or very large numbers do not overflow or round to zero), so it still works for n up to 10^7 objects. Predict the shortest unique prefix length for 5 real repositories. Then measure it from `git rev-list --objects --all` (which lists every object in a repository) and compare it with the length git picks for itself under its core.abbrev=auto setting. Finally, back up the analytic numbers with a Monte Carlo simulation: generate random hashes many times and count how often prefixes collide.

VICTORY CONDITIONS

  1. Prediction within +/-1 hex char on 5/5 repos. At every prefix length k, the analytic P(collision) must fall inside the 95% CI (confidence interval: the range that should contain the true value 95% of the time, given the simulation's random noise) of a 10^5-trial simulation. (How far the predicted shortest unique prefix length is from the observed one, |predicted - observed|; and how well the analytic collision probability agrees with the simulated one).
  2. A public repository with a README that shows your result and how to reproduce it.

Terms in plain words

Birthday bound
The rule that collisions among n random items drawn from N possibilities become likely once n reaches roughly the square root of N, as with shared birthdays in a room.
Log space
Doing calculations on the logarithms of numbers instead of the numbers themselves, so products become sums and tiny probabilities do not round to zero.
Monte Carlo simulation
Estimating a probability by running a random experiment many times and counting how often the event happens.
core.abbrev=auto
The git setting that lets git choose the abbreviated hash length automatically from the size of the repository.

Why it rates ★☆☆☆☆

A neat combinatorics exercise. It proves you can do undergraduate probability, and nothing beyond that.