Collision Probability
Approximate chance of a collision among n items in space N.
Formula
Variables
Example
n=1000, N=10^9: P ≈ 5×10⁻⁴
How it works
This formula estimates the chance that at least two of n randomly chosen items land in the same bucket when the available space has size N, assuming every item is placed independently and uniformly. The key idea is that collisions are driven by pairs: there are about n(n−1)/2 possible pairs, and each pair matches with probability about 1/N, so the total collision probability is approximately their product, giving n^2/(2N) when n is much smaller than N. It is especially useful as a quick birthday-paradox-style approximation in cryptography, where exact calculations are often unnecessary and the space is enormous.
When to use it
Use this when estimating accidental collisions in hash functions, randomly generated identifiers, nonces, or keys, especially when the number of samples is far smaller than the size of the space. It is a fast back-of-the-envelope check for whether a system is likely to see repeated values.
Worked example, step by step
Suppose a system generates n = 50,000 random IDs uniformly from a space of size N = 2^40. P ≈ n^2 / (2N) P ≈ (50,000)^2 / (2 × 2^40) P ≈ 2.5 × 10^9 / 2.199 × 10^12 P ≈ 1.14 × 10^-3 Final answer: the collision probability is about 0.00114, or 0.114%.
Common mistakes to avoid
- Using the formula when n is not much smaller than N, where the approximation can break down
- Forgetting that this estimates the probability of at least one collision, not the expected number of collisions
- Confusing N with bits of security; if the space has 2^k possibilities, then N = 2^k, not k
Did You Know?
UUID and nonce designers use this bound to pick sizes large enough that duplicates essentially never happen.
Share this formula
More in Cryptography & Security
View allModular Exponentiation
IntermediateCore operation of RSA encryption — raise a message to a power, modulo n.
RSA Decryption
AdvancedRecovers the message using the private exponent d.
Euler's Totient
IntermediateCounts integers below n coprime to it, for n = pq — used to make RSA keys.
Shannon Entropy
AdvancedAverage information content — and the theoretical strength of a random source.
Password Entropy
IntermediateBits of security from password length and character-set size.
Key Space Size
IntermediateNumber of possible keys for a b-bit key.