Engineering/Mathematics/Probability and randomness
Discrete Probability for Algorithm Analysis
Randomised algorithms are only as trustworthy as the bounds used to analyse them. Four tools do almost all the work: linearity of expectation, Chebyshev's inequality, the Chernoff bound, and statistical distance — the last being what lets an idealised analysis be transferred to a real implementation.
- Analysis toolkit
- Probability
- Underpins randomised algorithms
- ≈17 min read
- Feeds primality testing
01
Executive summary
A finite probability distribution is a finite sample space with non-negative weights summing to 1. Everything in this page is elementary in that setting; the value lies in knowing which tool answers which question, and how much each costs in tightness.
Three regimes recur. Expectation questions — how many trials until a prime is found — are handled by linearity and geometric distributions. Concentration questions — how likely is the observed count to deviate from its mean — are handled by Chebyshev when only the variance is known and by Chernoff when the summands are independent. Indistinguishability questions — is this sampler close enough to uniform — are handled by statistical distance.
| Question | Tool | Typical bound |
|---|---|---|
| Expected number of trials | linearity, geometric distribution | 1/p trials for success probability p |
| Deviation, only variance known | Chebyshev | Pr[|X − μ| ≥ t] ≤ Var(X)/t2 |
| Deviation, independent indicators | Chernoff / Hoeffding | exponentially small in the deviation |
| Any bad event among many | union bound | Pr[∪Ai] ≤ ∑ Pr[Ai] |
| Collisions among random samples | birthday analysis | collision likely after ≈ √m samples |
| Is this sampler good enough? | statistical distance | advantage of any distinguisher ≤ Δ |
02
Distributions, conditioning and independence
Finite probability distribution
A finite set Ω together with P : Ω → [0,1] summing to 1. An event is a subset, with Pr[A] = ∑ω ∈ A P(ω). The uniform distribution on Ω assigns 1/|Ω| to each point.
- Conditional probability. Pr[A ∣ B] = Pr[A ∩ B]/Pr[B] for Pr[B] > 0. Events are independent when Pr[A ∩ B] = Pr[A]Pr[B].
- Union bound. Pr[∪i Ai] ≤ ∑i Pr[Ai], with no independence assumption. Crude but almost always sufficient for bounding failure across many steps.
- Law of total probability. Conditioning on a partition, Pr[A] = ∑i Pr[A ∣ Bi]Pr[Bi] — the standard way to analyse an algorithm that branches on a random choice.
- Pairwise independence is strictly weaker than full independence and is often enough: Chebyshev's inequality needs only pairwise independence to bound the variance of a sum, which is why pairwise independent hash families are so useful.
03
Random variables, expectation and variance
- Linearity holds unconditionally: E[X + Y] = E[X] + E[Y] even for dependent variables. Most expected-cost analyses are just a careful decomposition into indicators plus linearity.
- Variance is additive for pairwise independent summands, which is the hypothesis Chebyshev actually needs.
- Geometric distribution. Repeating an experiment with success probability p until success takes 1/p trials in expectation, with variance (1−p)/p2. This is the model for random prime generation and for rejection sampling.
- Coupon collector. Collecting all m coupon types takes m Hm ≈ m ln m draws — the model for covering all residue classes or all factor-base elements.
Worked example: expected cost of generating a prime
Sample odd k-bit integers uniformly. Each is prime with probability p ≈ 2/(k ln 2), so the expected number of candidates is 1/p ≈ 0.347k — about 355 at k = 1024. Trial division by small primes rejects roughly 80% of candidates at negligible cost, so the expected number of full Miller–Rabin invocations is closer to 70, and the expected total cost is dominated by those.
A common analysis error
E[1/X] ≠ 1/E[X], and more generally E[f(X)] ≠ f(E[X]) unless f is affine. Jensen's inequality gives the direction of the error for convex or concave f. Substituting an expected value into a non-linear cost formula is one of the most frequent mistakes in informal algorithm analysis.
04
Concentration bounds
Markov, Chebyshev, Chernoff
- Markov. For X ≥ 0 and t > 0: Pr[X ≥ t] ≤ E[X]/t. Requires nothing but non-negativity, and is correspondingly weak.
- Chebyshev. Pr[|X − E[X]| ≥ t] ≤ Var(X)/t2. Polynomial decay; needs only the variance, hence only pairwise independence for sums.
- Chernoff. For X = ∑ Xi a sum of independent indicators with mean μ: Pr[X ≤ (1−ε)μ] ≤ e−ε2μ/2 and Pr[X ≥ (1+ε)μ] ≤ e−ε2μ/3 for 0 < ε < 1. Exponential decay, at the cost of full independence.
Why repetition is the right answer
Independent repetition drives one-sided error down geometrically, so a modest number of rounds reaches a failure probability far below the chance of an undetected hardware fault. For random candidates the true error is much smaller still than the worst-case 4−k bound, because worst-case inputs are astronomically rare among random ones.
05
The birthday paradox and collisions
Collision probability
Drawing t samples uniformly and independently from a set of size m, the probability of at least one repeat is approximately 1 − e−t(t−1)/(2m). A collision becomes likely once t ≈ √m, and the expected number of draws before the first collision is √(πm/2) ≈ 1.253√m.
| Setting | Consequence |
|---|---|
| Hash function security | An n-bit digest gives only 2n/2 collision resistance — 128-bit output means a 64-bit security level |
| Pollard rho factoring | A cycle in a pseudorandom walk modulo p appears after O(√p) = O(n1/4) steps |
| Pollard rho for discrete logs | O(√q) group operations in a group of order q — matching the generic lower bound |
| Baby-step giant-step | Deterministic O(√q) time and space by a meet-in-the-middle table |
| Nonce and IV reuse | Random 64-bit nonces collide after about 232 messages — usually unacceptable |
Every algorithm in this table is an instance of the same counting fact; recognising it saves rederiving the bound each time.
Hash functions and the smoothing of distributions
A family H of functions is universal if for distinct x ≠ y a random h ∈ H gives Pr[h(x) = h(y)] ≤ 1/m. Universal families are cheap to construct — ha,b(x) = ((ax + b) mod p) mod m is the standard example — and they give collision guarantees against an adversary who fixes inputs before the function is chosen.
Leftover hash lemma, in one sentence
Applying a universal hash function to a source with enough min-entropy produces output that is statistically close to uniform, with the closeness governed by the gap between the entropy and the output length. This is the formal justification for entropy extraction in random number generators, and it is the reason a hardware source with imperfect but sufficient entropy can be conditioned into a usable key stream.
06
Statistical distance
Statistical distance
- Data-processing inequality. Δ(f(X), f(Y)) ≤ Δ(X, Y) for any function f. Post-processing cannot increase distinguishability.
- Substitution. If an analysis assumes a uniform input and the real input is at distance Δ, the conclusion holds with an additive loss of Δ in the success probability. This is how idealised proofs are transferred to implementations.
- Hybrid argument. Chaining k substitutions costs k·Δ by the triangle inequality, which is why per-step distances must be kept far below 1/k.
A concrete use: sampling from a range
Generating a uniform value in [0, n) by taking r mod n for a uniform ℓ-bit r introduces a bias of statistical distance at most n/2ℓ. Choosing ℓ to exceed the bit length of n by 64 or more makes the bias negligible; alternatively, rejection sampling removes it exactly at the cost of an expected fraction of a retry.
07
Quick reference and FAQ
| Bound | Statement | Hypothesis |
|---|---|---|
| Markov | Pr[X ≥ t] ≤ E[X]/t | X ≥ 0 |
| Chebyshev | Pr[|X−μ| ≥ t] ≤ σ2/t2 | finite variance |
| Chernoff (lower) | Pr[X ≤ (1−ε)μ] ≤ e−ε2μ/2 | independent indicators |
| Chernoff (upper) | Pr[X ≥ (1+ε)μ] ≤ e−ε2μ/3 | independent indicators |
| Union | Pr[∪Ai] ≤ ∑Pr[Ai] | none |
| Birthday | collision likely at t ≈ √m | uniform independent samples |
| Geometric | E[trials] = 1/p | independent trials |
When is Chebyshev preferable to Chernoff?
Is the worst-case Miller–Rabin bound of 1/4 realistic?
What min-entropy is needed to extract a 256-bit key?
Why insist on statistical rather than computational indistinguishability here?
09
References and further reading
- V. Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge University Press, 2005 — Chapter 6.
- R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge, 1995 — Chapters 3–4 on moments and deviations.
- M. Mitzenmacher and E. Upfal, Probability and Computing, 2nd ed., Cambridge, 2017 — Chernoff bounds and hashing.
- J. L. Carter and M. N. Wegman, 'Universal classes of hash functions', J. Comput. Syst. Sci. 18 (1979) 143–154.
KEVOS® Knowledge LibraryEngineering → MathematicsTaxonomy ID: ENG-MATHPage ID: discrete-probability-for-algorithmsReview cycle: annual