Probability in algorithms and security
Randomness is a powerful tool in computing. It speeds up algorithms, protects secrets, and explains surprising collisions.
The birthday paradox
With 23 people, the probability of a shared birthday exceeds 50%. In computing, if a hash function has \(N\) possible outputs, collisions become likely after about \(\sqrt{N}\) inputs. For a 64-bit hash, that is around 4 billion items, which is why secure systems use much longer hashes.
Randomised algorithms
Las Vegas algorithms always give correct answers but have random running time, like randomised quicksort. Monte Carlo algorithms run in fixed time but may give a wrong answer with small probability, like primality tests used to generate encryption keys. Repeating a Monte Carlo test makes the error probability vanishingly small.
Primality testing
Large primes are needed for encryption. The Miller-Rabin test checks a number using random bases; a composite number passes each round with probability at most \(\frac{1}{4}\), so after 40 rounds the chance of a mistake is below \(4^{-40}\), far less likely than a hardware error.
Random sampling and estimation
To estimate a quantity, sample randomly. Estimating \(\pi\) by throwing random points into a square and counting those inside a quarter-circle is a classic Monte Carlo method. Tail bounds such as Chebyshev's inequality guarantee that averages of many samples are close to expected values.
Chebyshev's inequality
For any random variable with mean \(\mu\) and standard deviation \(\sigma\), \(P(|X - \mu| \ge k\sigma) \le \frac{1}{k^2}\). At least 75% of values lie within 2 standard deviations of the mean, for any distribution. It is weaker than the normal's 95% but requires no assumptions.
P(|X - \mu| \ge k\sigma) \le \frac{1}{k^2}Randomness and passwords
Password strength is measured in bits of entropy: a password chosen uniformly from \(N\) possibilities has \(\log_2 N\) bits. Four random common words from a list of 7,776 give about \(4 \times 12.9 \approx 52\) bits, much stronger than a short complex password that people choose predictably.
Pseudorandom numbers
Computers generate pseudorandom numbers with deterministic algorithms that look random. They are fine for simulations and games but not always for security, where cryptographically secure generators must be used so that attackers cannot predict future outputs.
Common mistakes
Underestimating collision probabilities. Using ordinary random generators for security. Confusing Las Vegas and Monte Carlo guarantees. Assuming human-chosen passwords are random.
Key takeaways
Collisions appear after about \(\sqrt{N}\) random items. Randomised algorithms trade certainty or running time for speed and simplicity. Repeated tests shrink error probability exponentially. Chebyshev's inequality bounds deviations for any distribution. Security needs true or cryptographic randomness.
Flashcard
23 people: over 50% share a birthday
Check your understanding
By Chebyshev's inequality, at least what fraction of any distribution lies within 3 standard deviations of the mean?