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
- 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).
- 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.