Probability

Symptom You need to test whether two arithmetic circuits compute the same polynomial. The deterministic approach is to expand both into normal form, and the expansion is exponentially large. The randomized approach takes four lines. Pick a random point, evaluate both circuits there, compare. If they differ as polynomials, the Schwartz-Zippel lemma says a random point catches it with probability at least $1 - d/|S|$. Repeat a few times and the error is negligible. ...

Symptom Your service went down under a hash collision attack. Somebody noticed your web framework put POST parameters into a hash table, found thousands of distinct keys colliding under its hash function, and posted a form with 20,000 of them. Every insert walked a chain. Quadratic behaviour, one CPU pinned per request, service dead. This actually happened, across PHP, Python, Ruby, Java and .NET in 2011, and again against Rust’s default HashMap before it switched to SipHash. ...

Symptom You have two files, each exactly one megabyte. The first is a megabyte of the byte 0x00. The second is a megabyte from /dev/urandom. Gzip the first and you get a few hundred bytes. Gzip the second and you get slightly more than a megabyte, because the header costs something and there is nothing to exploit. ...

Symptom You have 100 backends and a load balancer hashing request IDs to pick one. Expected load per backend is exactly 1%, and you have checked the hash is good. ...

Symptom Your service handles four billion requests a month and you want the error rate. Computing it exactly means a job over four billion log lines. Someone suggests sampling ten thousand of them. ...

Symptom You are analyzing a hash table. You want the expected number of buckets that end up empty. The bucket occupancies are all tangled together — one key landing in bucket 3 makes every other bucket slightly less likely to be chosen — and the dependencies look like they will make the sum intractable. ...

Symptom You need a short ID for uploads. Eight hex characters feels generous, so you take the first 32 bits of a hash and move on. At about 80,000 uploads, two files collide, and one of them silently overwrites the other, and the bug report says the customer’s invoice contains someone else’s line items. ...