On this page

Probability & Expected Value for Algorithms

Shuffle a deck of cards. How many cards do you expect to land back in their original position? Scan a random array and update best every time you see a bigger number. How many times does that assignment run? Hash strings into a 32-bit table. How likely is it that two different strings get the same hash? Throw jobs onto servers at random. How loaded is the busiest server, and what happens if each job looks at two random servers and picks the emptier one?

Every one of these has a short, exact answer: 1, , about 69%, and versus . None needs a dynamic program, a table or a simulation. They need four or five ideas from probability, used the way an algorithm designer uses them: to count what you expect, to bound what can go wrong, and to prove that something good exists.

This lesson is the algorithm-analysis side of probability. Three other Archon pages cover the neighbouring ground, and this page links to them instead of repeating them:

  • Probability for System Design covers the engineering side: base rates for alerts, correlated failures, the distributions behind retries and latency, UUID math, Bloom filters, reliability and quorum math.
  • Probability & Expected-Value DP covers the cases where you must build a table over states: dice boards, knights, self-loops, cycles.
  • Randomized Algorithms covers algorithms that flip coins: quicksort, quickselect, Fisher–Yates, reservoir sampling, Karger, Freivalds.

Here we go one level deeper on the math those pages lean on: where linearity of expectation comes from and the classic tricks it unlocks, why the geometric distribution is the waiting-time workhorse, how Markov, Chebyshev, Chernoff and the union bound turn an expectation into a guarantee "with high probability", and the two famous collision models (birthdays and balls in bins) that decide how hash tables and load balancers behave.

Why this exists

Most algorithms are analysed for the worst case: the input is chosen by an adversary. That is safe, but it hides two important facts.

First, many algorithms are much better on average than in the worst case, and "average" needs a precise meaning. Insertion sort does swaps on reversed input but about half that on a random one. Quicksort with a first-element pivot is quadratic on sorted input but about comparisons on a random one. To make "on average" a theorem you need a probability space (what is random, and how) and expectation.

Second, many algorithms use randomness on purpose, so even on a fixed input their running time is a random variable. For those you want two kinds of statement: "the expected time is " and "the time is with high probability", meaning the chance of failure shrinks like or faster. The second is stronger, and getting it needs tail bounds.

The history is short and recent. Knuth's The Art of Computer Programming (1968 onwards) made average-case analysis a discipline; its first analysed algorithm (Algorithm M, finding the maximum) asks exactly the records question in this lesson. Rabin's 1976 primality test and Solovay–Strassen's 1977 test made randomized algorithms respectable. Erdős had used the probabilistic method to prove the existence of combinatorial objects since 1947. Today the toolkit is standard: Motwani and Raghavan's Randomized Algorithms (1995) and Mitzenmacher and Upfal's Probability and Computing (2nd ed., 2017) are built around exactly the tools below.

Pattern triggers

If the problem says or has…Think of…
"expected number of …", "expected count"Indicator variables + linearity of expectation
"expected sum / total cost / total score"Linearity: split the total into per-item or per-pair contributions
"random permutation", "shuffled", "random order"Symmetry: each position/element is equally likely to be anything; fixed points 1, records , inversions
"repeat until success", "rejection sampling", "retry"Geometric distribution: expected attempts
"until every type has been seen", "collect all"Coupon collector:
"two items share a slot / hash / birthday"Birthday paradox: first collision near
"throw items into buckets at random", "busiest server"Balls into bins: max load
"pick the less loaded of two random choices"Power of two choices: max load
"with high probability", "fails with probability at most…"Markov → Chebyshev → Chernoff, plus the union bound
"show that some object with property exists"Probabilistic method: a random object has large enough
"print the answer as "Same reasoning, with exact fractions mapped to a prime field
"given that…", "probability that if we know "Conditional probability and Bayes' rule
The expectation depends on a state that evolves step by stepA DP over states instead: Probability & Expected-Value DP

The meta-trigger: before you design a DP for an expected value, try to write the quantity as a sum of simple 0/1 pieces. If each piece's probability is easy, you are done in one line.

Intuition & first principles

Sample spaces, events and probability

A sample space is the set of all possible outcomes of a random experiment. Shuffling 3 cards has all orders. An event is a subset of outcomes, such as "card 1 is still on top" (2 of the 6 orders). A probability assigns each event a number in such that and the probabilities of disjoint events add up.

In algorithm analysis the sample space is almost always finite and uniform: every permutation, every hash value, every coin-flip sequence is equally likely. Then

and probability is just counting. "Card 1 is on top" has probability . Whenever a result in this lesson looks surprising, you can check it by listing all outcomes for a small , and every number below was checked that way.

Conditional probability and independence

The conditional probability of given is the fraction of 's outcomes that are also in :

Think of it as "shrink the world to , then measure ". Rearranged, it gives the chain rule , which is how you compute the probability of a sequence of steps: multiply the probability of each step given everything before it. The birthday calculation below is exactly this.

Two events are independent if , i.e. knowing does not change the chance of . Independence is an assumption you must earn. Two hash values computed with the same seed on the same key are not independent; neither are "server 1 fails" and "server 2 fails" if they share a power supply. The system-design page has real examples of what goes wrong when you assume it.

Bayes' rule, the algorithm designer's version

Bayes' rule turns a conditional probability around:

Read as a hypothesis and as evidence. The denominator is the law of total probability: the evidence can arise with true or with false.

An algorithmic example. A bag holds 100 coins; exactly one is two-headed. You pick a coin at random, flip it 10 times, and see 10 heads. How sure can you be that you hold the trick coin?

  • Prior: .
  • Likelihoods: , .
  • Posterior: .

Only 91%, not 99.9%, because the prior was small. With 5 heads the posterior is 24%; with 15 heads it is 99.7%. This is exactly the reasoning behind one-sided Monte Carlo tests such as Freivalds' matrix check or Miller–Rabin: each passed round multiplies the odds in favour of "correct" by a fixed factor (2 for Freivalds, at least 4 for Miller–Rabin), so rounds drive the error below or regardless of the prior. See Randomized Algorithms for those tests.

flowchart LR
    S["Pick a coin"] -->|"1/100"| T["Two-headed"]
    S -->|"99/100"| F["Fair"]
    T -->|"P(10 heads) = 1"| E1["10 heads: weight 1/100"]
    F -->|"P(10 heads) = 1/1024"| E2["10 heads: weight 99/102400"]
    E1 --> P["Posterior = 1024/1123, about 0.912"]
    E2 --> P

Random variables and expectation

A random variable is a number computed from the outcome: the number of fixed points of a permutation, the number of comparisons quicksort makes, the load of the busiest bin. Its expectation (mean) is the probability-weighted average of its values:

The variance measures spread; its square root is the standard deviation .

Computing from the definition needs the full distribution , which is often hard. The next two ideas let you skip it almost every time.

Indicator variables

An indicator variable for an event is 1 if happens and 0 otherwise. Its expectation is the probability of the event:

Indicators turn "count the things that happen" into "add up 0/1 values", and that is where the magic starts.

Linearity of expectation

For any random variables and on the same space, and constants :

The word that matters is any. and may be wildly dependent and it still holds. (Variance does not behave this way: needs and uncorrelated.)

Put the two ideas together. If counts how many of the events happen, then and

You need the probability of each event on its own. You never need to know how they interact. That one line is the source of every closed form in the next section.

The recipe

  1. Name the thing you are counting. 2. Write it as a sum of indicators, one per item, position or pair. 3. Find the probability of one indicator, usually by symmetry. 4. Add. If step 3 is hard, you have at least split one hard problem into many easy ones.

Mechanics

1. Fixed points of a random permutation: expected value exactly 1

Shuffle distinct cards uniformly. A fixed point is a card that ends where it started. Let be the number of fixed points.

Indicators. Let if card is at position . By symmetry card is equally likely to be at any of the positions, so . Then

The events are clearly dependent (if cards are fixed, the last one must be too), and it does not matter.

Trace on . All six permutations, written as the card at positions 1, 2, 3:

PermutationFixed points
1 2 31113
1 3 21001
2 1 30011
2 3 10000
3 1 20000
3 2 10101
column sums2226

Each column sums to , and the average of the last column is . Linearity is nothing more than adding this table by columns instead of by rows.

Variance. Expand . A pair is fixed together with probability , and there are ordered pairs, so and for all . (Exhaustive enumeration for confirms mean 1 and variance 1.) The distribution of tends to a Poisson with mean 1; in particular the chance of no fixed point (a derangement) tends to .

2. Records (left-to-right maxima): expected value

Scan a sequence of distinct numbers in random order. Position is a record (or left-to-right maximum) if its value is larger than everything before it. The first element is always a record. This is exactly the number of times the line best = x runs in

best = -infinity
for x in a:
    if x > best:
        best = x      # how many times does this run?

Indicators. Let if position is a record. Look only at the first values. In a random permutation they are in random relative order, so the largest of them is equally likely to sit at any of the positions. Position is a record exactly when the largest of the first is at position :

the -th harmonic number. , where is the Euler–Mascheroni constant. So the assignment runs about times: , , and for a million elements about times.

Trace. Take the permutation 2 0 3 1 (values 0..3):

valuemax of first record?
122yes1
202no1/2
333yes1/3
413no1/4

This permutation has 2 records. Averaged over all 24 permutations of 4 values the count is . The full distribution is 6, 11, 6 and 1 permutations with 1, 2, 3 and 4 records (these are the unsigned Stirling numbers of the first kind), and . ✓

Bonus: the indicators here are independent. Whether position is a record depends only on where the maximum of the first sits, and those events turn out to be mutually independent (a classic result, Rényi 1962). So the variance adds: , where . For that is , matching enumeration.

The same quantity reappears all over algorithms:

  • The left spine of a random binary search tree (or a treap) is the sequence of prefix minima of the insertion order, so its expected length is . Summing the same argument over all nodes gives an expected node depth of about , the reason treaps are balanced in expectation.
  • In the hiring problem (CLRS §5.1), you interview candidates in random order and hire whenever someone beats the current best. The expected number of hires is .

3. Inversions: expected value

An inversion is a pair of positions with . Insertion sort performs exactly one swap per inversion, and bubble sort too, so inversions are their running time.

Indicators over pairs. For each pair , let if it is inverted. Swapping the two values gives a bijection between permutations where the pair is inverted and where it is not, so . There are pairs:

On a random array of 1,000 elements insertion sort does swaps on average, exactly half of the worst case . Average-case insertion sort is still ; the average only buys a factor of 2. That is why the algorithms in Elementary Sorts are only competitive on tiny or nearly-sorted arrays.

The pairwise indicators are not independent, but they are "almost" so, and the variance works out to (3 cases checked by enumeration: , , for ). The standard deviation is about , tiny next to the mean , so a random array's inversion count is sharply concentrated.

4. Randomized quicksort: comparisons

This is the most famous indicator argument in computer science, and it is worked out in full in Randomized Algorithms and Quick Sort. In one paragraph: name the elements in sorted order ; and are compared iff the first pivot chosen from is one of the two ends, which has probability ; summing over pairs gives

We checked the closed form against the exact recurrence in exact fractions: , , , , all equal. For the expectation is about comparisons, against for the leading term .

The lesson to carry away: the hard object (the random recursion tree) never has to be analysed. Only pairs do.

5. Geometric waiting times: expected trials

Repeat an experiment that succeeds with probability each time, independently, until the first success. The number of trials has the geometric distribution: for

Expected value by a one-line argument. Condition on the first trial. With probability you are done after 1 trial; otherwise you have used 1 trial and the future looks exactly like the start (the process has no memory). So

This "first-step analysis" is the same self-loop algebra as in Probability DP. The variance is , and the tail is : it decays exponentially.

Examples:

  • Roll a die until you see a 6: , standard deviation , and .
  • Rejection sampling. LeetCode's "Implement Rand10() using Rand7()" combines two calls into a uniform number in and accepts it only if it is at most 40. One attempt costs 2 calls and succeeds with , so the expected cost is calls.
  • Las Vegas algorithms that retry until a random choice is "good" (a good pivot in quickselect, a collision-free seed in perfect hashing): if a good choice has probability at least , the expected number of attempts is at most 2.

Memoryless means "no progress"

"I have already rolled 20 times without a 6, so a 6 is due" is false. The geometric distribution forgets: . A retry loop that has failed 20 times expects exactly as many more attempts as a fresh one.

6. The coupon collector:

There are coupon types; each draw gives a uniformly random type. How many draws until you own every type?

Split into phases. Phase (for ) starts when you own types and ends at the next new one. During phase each draw is new with probability , so the phase length is geometric with mean . The total time is the sum of the phase lengths, and linearity adds their means:

Trace for (rolling a die until every face has appeared):

Phase (types owned) = chance a roll is newExpected rolls Running total
06/611
15/61.22.2
24/61.53.7
33/625.7
42/638.7
51/6614.7

The last face alone costs 6 rolls on average, as much as the first four together. That is the shape of the coupon collector: the end dominates.

The phases are independent, so the variances add too: . For that is (standard deviation 6.2); for the mean is and the standard deviation .

A sharp tail with the union bound. After draws, a specific type is still missing with probability . "Some type is missing" is the union of such events, so

Set and the bound becomes . For :

union bound exact (inclusion–exclusion)
15610.3560.3680.302
26610.1300.1350.123
37610.0480.0500.047

The union bound is nearly exact here because "type missing" and "type missing" rarely happen together. The coupon collector is concentrated in a window of width around . For the cache-warming application, see Probability for System Design.

7. From expectation to guarantees: Markov, Chebyshev, Chernoff, union bound

An expectation alone does not tell you how often you will be unlucky. Tail bounds convert what you know about a variable into an upper bound on the chance it is far from its mean. The more you know, the sharper the bound.

flowchart LR
    U["Union bound<br/>needs: each event's probability"] --> M["Markov<br/>needs: E[X], X at least 0"]
    M --> C["Chebyshev<br/>needs: E[X] and Var[X]"]
    C --> H["Chernoff / Hoeffding<br/>needs: sum of independent bounded pieces"]

Markov's inequality. For and : . Proof: . One line, no assumptions beyond non-negativity.

The algorithmic use: turning a Las Vegas algorithm into a Monte Carlo one. If an algorithm runs in expected time , stop it after steps; by Markov it has finished with probability at least . Run independent copies (or restart times) and the chance all fail is at most .

Chebyshev's inequality. . Proof: apply Markov to the non-negative variable with threshold .

Chernoff bounds. If is a sum of independent 0/1 variables with , then for :

The matching lower tail is . Proof idea: apply Markov not to but to . Independence makes , a product of small factors, and choosing the best gives the bound. The Hoeffding form holds for independent variables in and is often the easiest to remember.

The intuition is the one sentence to keep: sums of many independent small pieces are exponentially concentrated around their mean. Markov and Chebyshev give polynomial tails; Chernoff gives exponential ones.

Comparing them on one question. Flip 1,000 fair coins. How likely are 600 or more heads? (, .)

MethodBound on
Markov
Chebyshev ()
Chernoff, simple form ()
Chernoff, full form
Hoeffding ()
Exact binomial tail

Each rung buys orders of magnitude. (The full Chernoff form loses to Hoeffding here only because it is written for the general case of small ; for fair coins Hoeffding's constant is better.)

The union bound. For any events, . No independence needed. It is the glue that turns a bound for one thing into a bound for all things: one bin, one coupon, one recursion path, one pair of strings.

"With high probability". An event holds w.h.p. if it fails with probability at most for some constant . The standard recipe:

  1. Use Chernoff to show one bad event (one bin overloaded, one root-to-leaf path in quicksort's recursion too long) has probability at most .
  2. There are at most such events, so the union bound gives total failure probability at most .

This is how one proves, for example, that randomized quicksort's recursion depth is , and therefore its running time , w.h.p. (a standard Chernoff exercise; see Mitzenmacher & Upfal, Chapter 4): along any root-to-leaf path, each level is "good" (shrinks the subproblem by a constant factor) with probability at least independently, so a long path with few good levels is a Chernoff-unlikely event, and there are only paths.

Markov versus Chebyshev versus the truth, coupon collector edition (, ): Markov says . Chebyshev says . The exact probability of is .

8. The birthday paradox and hash collisions

Put items into equally likely slots independently. What is the probability that two share a slot?

Exact, via the chain rule. The items are all distinct if item 2 avoids item 1, item 3 avoids both, and so on:

Approximation. Using (and for small ):

So collisions become likely once , far earlier than the intuition suggests. The 50% point is , and the expected number of items until the first collision is about .

Linearity view. The expected number of colliding pairs is simply : each pair collides with probability . For 23 people that is pairs. This form is often what you actually need ("how many false matches will my hash comparison produce?"), and it needs no approximation at all.

Numbers for (exact product, then the exponential approximation):

People exact
100.11690.1160
200.41140.4058
230.50730.5000
300.70630.6963
400.89120.8820
500.97040.9651
570.99010.9874

23 is the first above 50% and 57 the first above 99%. The expected number of people until the first shared birthday is 24.62.

Hash collisions. The same table, with = number of possible hash values, tells you how far a hash can be trusted:

Hash space 1% collision chance at50% atExpected colliding pairs among items
9,292 items77,164 items1.16
(one polynomial hash mod )about 4,500about 37,0005.0
about 609 millionabout
(two independent mods)about 141 millionabout

The row is the reason the String Hashing lesson recommends double hashing or a 61-bit Mersenne modulus: if you compare substring hashes against each other (deduplication, counting distinct substrings), a single prime around gives about 5 false matches on average. If you only compare each hash with one target (pattern matching), the expected false matches are , tiny. The birthday bound bites when every pair is compared. (These numbers assume the hash behaves like a random function on your inputs; an adversary who knows a fixed modulus and base can do far worse, which is why the base must be random.)

Where 64 bits stops being enough

A 64-bit hash reaches a 50% collision chance at about 5 billion items. That is why content-addressed systems use 128 to 256 bits: Git object ids are 160-bit SHA-1 (with SHA-256 support since Git 2.29), and UUID v4 has 122 random bits. The system-design page does the UUID arithmetic.

9. Balls into bins and the power of two choices

Throw balls into bins, each ball to a uniformly random bin. This is the model for hashing with chaining (balls = keys, bins = buckets) and for random load balancing (balls = requests, bins = servers).

Expected load and empty bins (linearity). Each bin gets balls on average. A given bin is empty with probability , so the expected number of empty bins is . With , about of bins stay empty. In our simulation with balls and bins, 368,368 bins were empty against a prediction of 367,879.

Maximum load. The busiest bin is the interesting quantity: it is the longest hash chain, the hottest server. For the maximum load is

more precisely (Gonnet 1981; Raab and Steger 1998).

Why (upper bound sketch). A fixed bin gets at least balls with probability at most . Choose ; then for large . Union bound over bins: the probability that any bin reaches is at most .

The power of two choices. Now let each ball pick two random bins and go to the less loaded one (ties either way). The maximum load collapses to

(Azar, Broder, Karlin and Upfal, 1994/1999). With choices it is , so going from 1 to 2 choices is an exponential improvement and going from 2 to 3 only a constant factor. Intuition: to get load , a ball must find two bins that both already have load . If a fraction of bins has load at least , that happens with probability , so : the fractions square at each level and fall below after levels.

Our simulation (, five seeds each):

one choice: max load (5 runs)two choices: max load (5 runs)
5, 5, 6, 6, 53.573, 3, 3, 3, 32.79
8, 6, 6, 7, 74.153, 3, 3, 3, 33.20
8, 7, 8, 7, 84.714, 4, 3, 3, 43.53
9, 8, 9, 9, 95.264, 4, 4, 4, 43.79

The asymptotic formulas only give the order of growth (the hidden constants and lower-order terms matter at these sizes), but the shape is unmistakable: one choice keeps creeping up, two choices sit flat at 3 to 4.

This is not just theory. Envoy's least-request load balancer and NGINX's random two upstream method both sample two backends and pick the less loaded; see Load Balancing Algorithms. Cuckoo hashing, where each key has two possible slots, is the same idea applied to hash tables.

10. The probabilistic method: proving that something exists

Linearity has a corollary that sounds like a trick: a random variable takes a value at least its expectation with positive probability. So if a random object has , then some object has quality at least . You prove existence without constructing anything.

Max-cut. Split the vertices of a graph with edges into two sides by fair coin flips. Each edge crosses the cut with probability , so the expected cut size is . Therefore every graph has a cut with at least edges. Even better, the proof hints at an algorithm: a random cut achieves at least the expectation with decent probability, and the method of conditional expectations (fix the coins one by one, each time keeping the conditional expectation at least ) turns it into a deterministic greedy -approximation.

MAX-3SAT. A random assignment satisfies each clause of three distinct literals with probability , so some assignment satisfies at least of the clauses. Håstad (2001) proved that doing better than in polynomial time is NP-hard, so this naive argument is optimal unless P = NP.

Ramsey numbers (Erdős, 1947). Colour the edges of a complete graph on vertices red or blue at random. The expected number of single-coloured -cliques is , which is below 1 when (). So some colouring has none, proving . Nobody knows how to construct such colourings explicitly for large ; this gap between "exists" and "can build" is a theme in complexity theory.

11. Expected values modulo a prime

Contest problems often say "the expected value is a rational ; print ". Every derivation in this lesson works unchanged: expectations are sums and products of fractions, and those can be computed in the field of integers modulo a prime , where dividing by means multiplying by the modular inverse (Fermat's little theorem; theory in Modular Arithmetic).

Example: the expected number of records for is . Mod :

and indeed . To compute , add for , or precompute all inverses in with .

Two rules: you may only divide by numbers not divisible by (fine for when ), and you cannot compare residues, so "which expectation is larger?" questions need real numbers. Probability DP shows the same technique inside a DP.

The ladder: brute force → better → optimal

Take one question and climb: the expected number of records in a random permutation of .

Rung 1: enumerate the sample space

List all permutations, count records in each, average. Exact, and the right way to check a formula for or so. Cost: . At that is 36 million steps; at , about .

Rung 2: Monte Carlo simulation

Draw random permutations and average. Cost . The error shrinks like : for , , so trials give about (one standard error). Good for sanity checks, useless for exact answers or answers mod . Our implementation below does exactly this.

Rung 3: a DP over states

Process positions left to right. Position is a record with probability , independently of the earlier positions, so a DP over "records so far" gives the full distribution in : . The counts it produces are the Stirling numbers of the first kind. This is the Probability DP approach, and it is what you do when you need , not just the mean.

Rung 4: linearity of expectation

. Cost to evaluate (or with as an approximation), exact as a fraction, exact mod .

RungGivesTimeExact?When to use
Enumeratemean, full distributionyeschecking formulas for tiny
Monte Carlomean ± noisenosanity checks; models too messy for math
DP over statesfull distributionyeswhen you need or for non-linear
Linearitymeanyesany "expected count/sum" with easy per-item probabilities

The ladder also shows the limits of linearity: it gives , and via pairs, but not or directly. For those you need a DP, a tail bound, or a cleverer decomposition such as for non-negative integers (the trick behind CSES "Candy Lottery" in the practice ladder).

Correctness

Linearity of expectation (finite sample space). . Nothing about independence was used: we summed over outcomes, not over values. (For infinite spaces the same holds whenever the expectations exist.)

Records are . Condition on the set of the first values. Every ordering of that set is equally likely (a uniform permutation restricted to a prefix is uniform), and in exactly a fraction of orderings the maximum is last.

Coupon collector. The phase decomposition writes with geometric of mean . Linearity needs nothing more. (For the variance we used that the are independent, which holds because each phase's length depends only on draws inside that phase.)

Union bound. , because the indicator of a union is at most the sum of the indicators, pointwise.

Birthday product. Chain rule: .

Balls-into-bins upper bound. by the union bound over all -subsets of balls (each subset lands entirely in bin with probability ). Then using .

The probabilistic method. If every outcome had then . Contrapositive: implies some outcome has .

Expected values mod . The map from rationals with denominators coprime to into preserves , , and division (it is a ring homomorphism), so computing the formula in gives the image of the true rational.

Complexity

The analysis tools have no running time of their own, but the computations around them do:

TaskTimeNotes
in floating point, or via relative error of the approximation below for
with linear-time inverses, or with Fermat
Exact birthday productuse for large to avoid underflow
Expected colliding pairs
Monte Carlo estimate with trialsstandard error : 4× trials for 2× precision
Exact enumeration permutations, coin sequences
Coupon tail by inclusion–exclusion big-number termsalternating sum: needs exact or high-precision arithmetic

How many Monte Carlo trials do you need? To estimate a probability to within with 95% confidence you need about ; for and that is trials. A Chernoff/Hoeffding bound gives the worst-case version: trials guarantee error at most with probability .

Implementation

The program below confirms three results of this lesson by simulation and compares each against the exact formula:

  1. Records: random permutations of 10 elements have on average records.
  2. Birthday: 23 random birthdays out of 365 contain a repeat with probability .
  3. Coupon collector: collecting all 50 coupon types takes on average draws.

All four versions use the same tiny pseudo-random generator, xorshift32 (Marsaglia, 2003), with the same seed, so they print exactly the same simulated numbers. Language RNGs differ (Python's Mersenne Twister, Java's LCG, C++'s mt19937, V8's xorshift128+), and a shared generator makes the outputs comparable line for line. For real work use your language's library generator; xorshift32 is fine for a demo but fails modern statistical test suites. below(n) uses next() % n, which is biased by at most , under here.

Expected output (identical in all four languages):

records  n=10: simulated 2.9284  exact H_10 = 2.9290
birthday k=23: simulated 0.5102  exact = 0.5073
coupons  n=50: simulated 224.85  exact 50*H_50 = 224.96
all simulations agree with the formulas

The birthday estimate is off by 0.0029, about 1.8 standard errors (), which is ordinary sampling noise. The asserts use tolerances of roughly 4–6 standard errors so they never fail by bad luck.

"""Simulations that confirm three expectation results.

All four language versions use the same xorshift32 generator and seed,
so they print exactly the same simulated numbers.
"""


class XorShift32:
    def __init__(self, seed: int) -> None:
        self.x = seed & 0xFFFFFFFF

    def next(self) -> int:
        x = self.x
        x ^= (x << 13) & 0xFFFFFFFF
        x ^= x >> 17
        x ^= (x << 5) & 0xFFFFFFFF
        self.x = x
        return x

    def below(self, n: int) -> int:
        """Integer in [0, n). The modulo bias is below n / 2**32: negligible here."""
        return self.next() % n


def harmonic(n: int) -> float:
    return sum(1.0 / k for k in range(1, n + 1))


def simulate_records(rng: XorShift32, n: int, trials: int) -> float:
    """Average number of left-to-right maxima in a uniformly random permutation."""
    total = 0
    for _ in range(trials):
        perm = list(range(n))
        for i in range(n - 1, 0, -1):          # Fisher-Yates shuffle
            j = rng.below(i + 1)
            perm[i], perm[j] = perm[j], perm[i]
        best = -1
        for v in perm:
            if v > best:                        # a new record
                best = v
                total += 1
    return total / trials


def birthday_exact(k: int, days: int) -> float:
    p_distinct = 1.0
    for i in range(k):
        p_distinct *= (days - i) / days
    return 1.0 - p_distinct


def simulate_birthday(rng: XorShift32, k: int, days: int, trials: int) -> float:
    """Fraction of trials in which k random birthdays contain a repeat."""
    hits = 0
    for _ in range(trials):
        seen = [False] * days
        for _ in range(k):
            d = rng.below(days)
            if seen[d]:
                hits += 1
                break
            seen[d] = True
    return hits / trials


def simulate_coupons(rng: XorShift32, n: int, trials: int) -> float:
    """Average number of uniform draws until all n coupon types are seen."""
    total = 0
    for _ in range(trials):
        seen = [False] * n
        distinct = draws = 0
        while distinct < n:
            c = rng.below(n)
            draws += 1
            if not seen[c]:
                seen[c] = True
                distinct += 1
        total += draws
    return total / trials


def main() -> None:
    rng = XorShift32(2463534242)

    rec = simulate_records(rng, 10, 100_000)
    rec_exact = harmonic(10)                    # H_10 = 2.928968...
    print(f"records  n=10: simulated {rec:.4f}  exact H_10 = {rec_exact:.4f}")
    assert abs(rec - rec_exact) < 0.02

    bd = simulate_birthday(rng, 23, 365, 100_000)
    bd_exact = birthday_exact(23, 365)          # 0.507297...
    print(f"birthday k=23: simulated {bd:.4f}  exact = {bd_exact:.4f}")
    assert abs(bd - bd_exact) < 0.01

    cc = simulate_coupons(rng, 50, 20_000)
    cc_exact = 50 * harmonic(50)                # 224.96...
    print(f"coupons  n=50: simulated {cc:.2f}  exact 50*H_50 = {cc_exact:.2f}")
    assert abs(cc - cc_exact) < 2.5
    print("all simulations agree with the formulas")


if __name__ == "__main__":
    main()
public class Main {
    // Same xorshift32 generator and seed as the other versions: identical output.
    static int state = (int) 2463534242L;

    static int next() {
        int x = state;
        x ^= x << 13;
        x ^= x >>> 17;
        x ^= x << 5;
        state = x;
        return x;
    }

    static int below(int n) {
        return Integer.remainderUnsigned(next(), n);   // treat the 32 bits as unsigned
    }

    static double harmonic(int n) {
        double h = 0;
        for (int k = 1; k <= n; k++) h += 1.0 / k;
        return h;
    }

    static double simulateRecords(int n, int trials) {
        long total = 0;
        int[] perm = new int[n];
        for (int t = 0; t < trials; t++) {
            for (int i = 0; i < n; i++) perm[i] = i;
            for (int i = n - 1; i > 0; i--) {             // Fisher-Yates shuffle
                int j = below(i + 1);
                int tmp = perm[i]; perm[i] = perm[j]; perm[j] = tmp;
            }
            int best = -1;
            for (int v : perm) {
                if (v > best) { best = v; total++; }      // a new record
            }
        }
        return (double) total / trials;
    }

    static double birthdayExact(int k, int days) {
        double pDistinct = 1.0;
        for (int i = 0; i < k; i++) pDistinct *= (double) (days - i) / days;
        return 1.0 - pDistinct;
    }

    static double simulateBirthday(int k, int days, int trials) {
        int hits = 0;
        for (int t = 0; t < trials; t++) {
            boolean[] seen = new boolean[days];
            for (int i = 0; i < k; i++) {
                int d = below(days);
                if (seen[d]) { hits++; break; }
                seen[d] = true;
            }
        }
        return (double) hits / trials;
    }

    static double simulateCoupons(int n, int trials) {
        long total = 0;
        for (int t = 0; t < trials; t++) {
            boolean[] seen = new boolean[n];
            int distinct = 0, draws = 0;
            while (distinct < n) {
                int c = below(n);
                draws++;
                if (!seen[c]) { seen[c] = true; distinct++; }
            }
            total += draws;
        }
        return (double) total / trials;
    }

    public static void main(String[] args) {
        double rec = simulateRecords(10, 100_000);
        double recExact = harmonic(10);
        System.out.printf("records  n=10: simulated %.4f  exact H_10 = %.4f%n", rec, recExact);
        if (Math.abs(rec - recExact) >= 0.02) throw new AssertionError("records");

        double bd = simulateBirthday(23, 365, 100_000);
        double bdExact = birthdayExact(23, 365);
        System.out.printf("birthday k=23: simulated %.4f  exact = %.4f%n", bd, bdExact);
        if (Math.abs(bd - bdExact) >= 0.01) throw new AssertionError("birthday");

        double cc = simulateCoupons(50, 20_000);
        double ccExact = 50 * harmonic(50);
        System.out.printf("coupons  n=50: simulated %.2f  exact 50*H_50 = %.2f%n", cc, ccExact);
        if (Math.abs(cc - ccExact) >= 2.5) throw new AssertionError("coupons");
        System.out.println("all simulations agree with the formulas");
    }
}
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <utility>
#include <vector>

// Same xorshift32 generator and seed as the other versions: identical output.
struct XorShift32 {
    uint32_t x;
    explicit XorShift32(uint32_t seed) : x(seed) {}
    uint32_t next() {
        x ^= x << 13;
        x ^= x >> 17;
        x ^= x << 5;
        return x;
    }
    uint32_t below(uint32_t n) { return next() % n; }
};

double harmonic(int n) {
    double h = 0;
    for (int k = 1; k <= n; k++) h += 1.0 / k;
    return h;
}

double simulateRecords(XorShift32& rng, int n, int trials) {
    long long total = 0;
    std::vector<int> perm(n);
    for (int t = 0; t < trials; t++) {
        for (int i = 0; i < n; i++) perm[i] = i;
        for (int i = n - 1; i > 0; i--) {                 // Fisher-Yates shuffle
            int j = static_cast<int>(rng.below(i + 1));
            std::swap(perm[i], perm[j]);
        }
        int best = -1;
        for (int v : perm)
            if (v > best) { best = v; total++; }          // a new record
    }
    return static_cast<double>(total) / trials;
}

double birthdayExact(int k, int days) {
    double pDistinct = 1.0;
    for (int i = 0; i < k; i++) pDistinct *= static_cast<double>(days - i) / days;
    return 1.0 - pDistinct;
}

double simulateBirthday(XorShift32& rng, int k, int days, int trials) {
    int hits = 0;
    for (int t = 0; t < trials; t++) {
        std::vector<bool> seen(days, false);
        for (int i = 0; i < k; i++) {
            uint32_t d = rng.below(days);
            if (seen[d]) { hits++; break; }
            seen[d] = true;
        }
    }
    return static_cast<double>(hits) / trials;
}

double simulateCoupons(XorShift32& rng, int n, int trials) {
    long long total = 0;
    for (int t = 0; t < trials; t++) {
        std::vector<bool> seen(n, false);
        int distinct = 0, draws = 0;
        while (distinct < n) {
            uint32_t c = rng.below(n);
            draws++;
            if (!seen[c]) { seen[c] = true; distinct++; }
        }
        total += draws;
    }
    return static_cast<double>(total) / trials;
}

int main() {
    XorShift32 rng(2463534242u);

    double rec = simulateRecords(rng, 10, 100000);
    double recExact = harmonic(10);
    std::printf("records  n=10: simulated %.4f  exact H_10 = %.4f\n", rec, recExact);
    assert(std::fabs(rec - recExact) < 0.02);

    double bd = simulateBirthday(rng, 23, 365, 100000);
    double bdExact = birthdayExact(23, 365);
    std::printf("birthday k=23: simulated %.4f  exact = %.4f\n", bd, bdExact);
    assert(std::fabs(bd - bdExact) < 0.01);

    double cc = simulateCoupons(rng, 50, 20000);
    double ccExact = 50 * harmonic(50);
    std::printf("coupons  n=50: simulated %.2f  exact 50*H_50 = %.2f\n", cc, ccExact);
    assert(std::fabs(cc - ccExact) < 2.5);
    std::printf("all simulations agree with the formulas\n");
    return 0;
}
// Same xorshift32 generator and seed as the other versions: identical output.
class XorShift32 {
  private x: number;
  constructor(seed: number) {
    this.x = seed | 0;
  }
  next(): number {
    let x = this.x;
    x ^= x << 13;
    x ^= x >>> 17;
    x ^= x << 5;
    this.x = x;
    return x >>> 0; // as an unsigned 32-bit value
  }
  below(n: number): number {
    return this.next() % n;
  }
}

function harmonic(n: number): number {
  let h = 0;
  for (let k = 1; k <= n; k++) h += 1 / k;
  return h;
}

function simulateRecords(rng: XorShift32, n: number, trials: number): number {
  let total = 0;
  const perm = new Array<number>(n);
  for (let t = 0; t < trials; t++) {
    for (let i = 0; i < n; i++) perm[i] = i;
    for (let i = n - 1; i > 0; i--) { // Fisher-Yates shuffle
      const j = rng.below(i + 1);
      [perm[i], perm[j]] = [perm[j], perm[i]];
    }
    let best = -1;
    for (const v of perm) {
      if (v > best) { best = v; total++; } // a new record
    }
  }
  return total / trials;
}

function birthdayExact(k: number, days: number): number {
  let pDistinct = 1;
  for (let i = 0; i < k; i++) pDistinct *= (days - i) / days;
  return 1 - pDistinct;
}

function simulateBirthday(rng: XorShift32, k: number, days: number, trials: number): number {
  let hits = 0;
  for (let t = 0; t < trials; t++) {
    const seen = new Array<boolean>(days).fill(false);
    for (let i = 0; i < k; i++) {
      const d = rng.below(days);
      if (seen[d]) { hits++; break; }
      seen[d] = true;
    }
  }
  return hits / trials;
}

function simulateCoupons(rng: XorShift32, n: number, trials: number): number {
  let total = 0;
  for (let t = 0; t < trials; t++) {
    const seen = new Array<boolean>(n).fill(false);
    let distinct = 0;
    let draws = 0;
    while (distinct < n) {
      const c = rng.below(n);
      draws++;
      if (!seen[c]) { seen[c] = true; distinct++; }
    }
    total += draws;
  }
  return total / trials;
}

function check(cond: boolean, msg: string): void {
  if (!cond) throw new Error("check failed: " + msg);
}

const rng = new XorShift32(2463534242);

const rec = simulateRecords(rng, 10, 100000);
const recExact = harmonic(10);
console.log(`records  n=10: simulated ${rec.toFixed(4)}  exact H_10 = ${recExact.toFixed(4)}`);
check(Math.abs(rec - recExact) < 0.02, "records");

const bd = simulateBirthday(rng, 23, 365, 100000);
const bdExact = birthdayExact(23, 365);
console.log(`birthday k=23: simulated ${bd.toFixed(4)}  exact = ${bdExact.toFixed(4)}`);
check(Math.abs(bd - bdExact) < 0.01, "birthday");

const cc = simulateCoupons(rng, 50, 20000);
const ccExact = 50 * harmonic(50);
console.log(`coupons  n=50: simulated ${cc.toFixed(2)}  exact 50*H_50 = ${ccExact.toFixed(2)}`);
check(Math.abs(cc - ccExact) < 2.5, "coupons");
console.log("all simulations agree with the formulas");

A few implementation notes:

  • Fisher–Yates must draw from , inclusive. Drawing from at every step is the classic biased shuffle; it would skew the records count. See Randomized Algorithms.
  • Unsigned arithmetic. Java has no unsigned int, so Integer.remainderUnsigned treats the 32 bits as unsigned before %. TypeScript's bitwise operators work on signed 32-bit integers, and >>> 0 reinterprets the result as unsigned. Forgetting either gives negative indices.
  • The birthday loop breaks at the first repeat. That is correct for the probability but changes how many random numbers are consumed, which is why sharing the generator across the three experiments only works because all four versions do exactly the same thing in the same order.

Real-world uses

  • Hash tables. Expected chain length (load factor) for a successful search, the worst chain under random hashing, and universal hashing's guarantee that any two keys collide with probability at most (Carter and Wegman, 1979) are all indicator-variable arguments. See Hash Tables.
  • Load balancers. Envoy's LEAST_REQUEST policy samples two hosts by default and picks the one with fewer active requests; NGINX offers random two least_conn in its upstream module. Both are the power of two choices. Mitzenmacher's thesis (1996) and his survey "The Power of Two Choices in Randomized Load Balancing" (IEEE TPDS, 2001) are the standard references.
  • Content addressing and deduplication. Git, backup systems and CDNs pick hash widths with the birthday bound in mind. Git shortens object ids to a prefix whose default length grows with the repository size (since Git 2.11), precisely to keep the expected number of prefix collisions small.
  • String algorithms. Rabin–Karp and polynomial hashing rely on the probability that two different strings collide being about per comparison; the birthday bound tells you when single-modulus hashing breaks. See String Hashing.
  • Randomized data structures. Treaps and skip lists have expected height by record/indicator arguments, and height w.h.p. by Chernoff. See Treaps, Splay Trees & Skip Lists.
  • Sketches and sampling. Count-Min sketches, HyperLogLog and random sampling for A/B tests all quote error bounds of the form "within with probability ", proved with Markov, Chebyshev or Chernoff plus "take the median of copies". See Bloom Filters and Statistics & A/B Testing.
  • Approximation algorithms. Randomized rounding of linear programs, random cuts for MAX-CUT and random assignments for MAX-SAT come from the probabilistic method, often then derandomized with conditional expectations.

Pitfalls & edge cases

  • Assuming independence for variance. Linearity of expectation is free; additivity of variance is not. The inversion indicators and are correlated, so you must include covariance terms.
  • Confusing "expected" with "typical". The coupon collector for has mean 519, but nearly 5% of runs (exactly 4.7%) need more than 761 draws. For latency-critical code, quote a tail bound, not a mean.
  • and . Linearity is only about sums. Jensen's inequality ( for convex ) tells you which way the error goes.
  • Using the birthday approximation far outside its range. is accurate when . For close to , compute the exact product (in log space).
  • Comparing against one target versus all pairs. Expected false matches are for one-vs-many but for all-pairs. Mixing the two up is the most common hashing mistake in contests.
  • Applying Chernoff to dependent variables. Chernoff needs independence (or negative dependence, which balls-into-bins loads have). A single heavy key in a sharded store is one big variable, not many small ones.
  • Union bound giving a probability above 1. It is still a true statement, just useless. Tighten each term (Chernoff) or reduce the number of events (bucket them).
  • Modulo bias and bad generators in simulations. rand() % n with a small RAND_MAX is visibly biased; Math.random() cannot be seeded. Use a seeded, documented generator so results reproduce.
  • Expected values mod with a denominator divisible by . Happens when a probability you divide by is itself 0 mod ; reformulate.

Variations

  • Higher moments by pairs. . This is how the fixed-point variance (1) and inversion variance came out, and how CF "Let's Play Osu!" computes expected squared run lengths.
  • for non-negative integer : the tail-sum formula, ideal for expected maxima and expected waiting times.
  • Wald's identity. If you add a random number of i.i.d. values and is a stopping time, . Useful for "keep drawing until…" costs.
  • Negative binomial. Waiting for the -th success: mean .
  • Coupon collector variants. Collecting only of types takes draws; unequal probabilities need inclusion–exclusion or the integral .
  • Generalised birthday. Probability of a triple collision becomes likely around items; birthday attacks on -bit hashes cost about work.
  • Balls into bins with . Max load is with one choice but with two (Berenbrink, Czumaj, Steger, Vöcking 2000): two choices keep the gap constant no matter how many balls.
  • Lovász Local Lemma. A sharpening of the probabilistic method for many events that are each rare and only locally dependent; Moser and Tardos (2010) made it algorithmic.
  • Martingales and Azuma's inequality. Concentration for dependent processes with bounded differences, used for chromatic numbers of random graphs and online algorithms.

Practice ladder

Each problem is described in my own words; follow the link for the full statement.

1. HSI (AtCoder ABC 078 C / ARC 085 A) — A program has hard test cases that each pass with probability and take 1900 ms, plus easy ones that always pass and take 100 ms. You resubmit until everything passes at once. Expected total time? Teaches the geometric distribution.

Solution

One submission takes ms and passes with probability , so the expected number of submissions is .

def hsi(n: int, m: int) -> int:
    return (1900 * m + 100 * (n - m)) * 2 ** m


assert hsi(1, 1) == 3800
assert hsi(10, 2) == 18400
assert hsi(100, 5) == 608000

2. Implement Rand10() Using Rand7() (LeetCode 470) — Build a uniform 1..10 generator from a uniform 1..7 generator. Teaches rejection sampling and its expected cost.

Hint

Two calls give a uniform value in . Accept and return (v - 1) % 10 + 1; otherwise retry. Expected calls . The follow-up asks you to recycle the rejected values (41..49 give a uniform 1..9) to lower the expected cost further.

3. Airplane Seat Assignment Probability (LeetCode 1227) — The first of passengers sits in a random seat; each later passenger takes their own seat if free, otherwise a random free one. What is the chance the last passenger gets their own seat? Teaches symmetry arguments.

Hint

Answer: 1 for , otherwise . The game ends the moment someone sits in seat 1 or seat ; at every random choice those two seats are equally likely to be picked first, and which one decides the outcome.

4. Candy Lottery (CSES 1727) — Each of children gets a uniform random number of candies from 1 to . Find the expected maximum. Teaches the tail-sum formula.

Solution

.

def candy_lottery(n: int, k: int) -> float:
    return sum(1 - ((x - 1) / k) ** n for x in range(1, k + 1))


assert f"{candy_lottery(2, 3):.6f}" == "2.444444"

5. Inversion Probability (CSES 1728) — An array where is uniform on , independently. Find the expected number of inversions. Teaches linearity over pairs with non-identical distributions.

Solution

For each pair add . With the triple loop is fast enough.

def inversion_probability(r: list[int]) -> float:
    total = 0.0
    for i in range(len(r)):
        for j in range(i + 1, len(r)):
            favourable = sum(min(a - 1, r[j]) for a in range(1, r[i] + 1))
            total += favourable / (r[i] * r[j])
    return total


assert f"{inversion_probability([5, 2, 7]):.6f}" == "1.057143"

6. Let's Play Osu! (Codeforces 235B) — Each of clicks succeeds with its own probability; a maximal run of successes scores . Find the expected score. Teaches linearity for squared quantities.

Solution

Let be the expected length of the run ending at the current click. Extending a run of length to adds to the score, so the click adds in expectation; then .

def osu(ps: list[float]) -> float:
    run = score = 0.0
    for p in ps:
        score += p * (2 * run + 1)
        run = p * (run + 1)
    return score


assert abs(osu([0.5, 0.5, 0.5]) - 2.75) < 1e-12

(Checked against brute force over all outcomes for random small inputs.)

7. Fishes (Codeforces 912D) — Place fish in distinct cells of an pond to maximise the expected catch of a randomly placed net. Teaches linearity plus a greedy choice.

Hint

The expected catch is , and each cell's probability is (number of net positions covering it) / (total positions). Linearity means you just take the cells with the largest coverage; expand outward from the centre with a priority queue.

8. Game on Tree (Codeforces 280C) — Repeatedly pick a uniformly random remaining vertex and delete its whole subtree. Expected number of steps? Teaches the "is this vertex chosen before all its ancestors?" indicator.

Solution

Vertex costs a step iff it is picked before every one of its ancestors. Among and its ancestors, each is equally likely to be picked first, so the probability is (root has depth 1). Answer: — the same argument as records.

from collections import deque


def game_on_tree(n: int, edges: list[tuple[int, int]]) -> float:
    adj = [[] for _ in range(n + 1)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    depth = [0] * (n + 1)
    depth[1] = 1
    q = deque([1])
    while q:
        u = q.popleft()
        for w in adj[u]:
            if depth[w] == 0:
                depth[w] = depth[u] + 1
                q.append(w)
    return sum(1 / depth[v] for v in range(1, n + 1))


assert abs(game_on_tree(2, [(1, 2)]) - 1.5) < 1e-12
assert abs(game_on_tree(3, [(1, 2), (1, 3)]) - 2.0) < 1e-12

9. Tree Array (Codeforces 1540B) — A random process labels tree vertices in an order; find the expected number of inversions, mod . Teaches linearity over pairs, a small probability DP per pair, and answers mod .

Hint

Fix the starting root and sum over roots. For a pair with , only the race between the two paths from their LCA matters: it is a symmetric random walk "who gets eaten first", a 2-D probability DP on the two distances that you precompute once. Linearity adds all pairs.

Common mistakes & interview follow-ups

"Expected number of fixed points of a shuffle?" 1, by indicators. Follow-up: "And the variance?" Also 1 (pairs are fixed together with probability ). "Probability of none?" Tends to .

"How many times does max = x execute?" on a random permutation, on sorted input, 1 on reversed input. Interviewers like this because it separates "I know Big-O" from "I can analyse".

"Why does randomized quicksort not have a bad input?" The randomness is in the algorithm, so the expectation holds for every input; only unlucky coin flips are slow, and Chernoff shows they are rare.

"How many items before a 32-bit hash collides?" About for a 39% chance and 77,164 for 50%. Follow-up: "64-bit?" About 5 billion for 50%.

"Your service picks a random server per request. Why is one server overloaded?" Balls into bins: max load for . Fix: two random choices, pick the less loaded.

"Is ?" Only for uncorrelated (e.g. independent) variables. Linearity is about sums.

"Prove some graph cut has at least half the edges." Random cut, linearity, probabilistic method.

Mistakes interviewers watch for: forgetting the first element is always a record; adding variances of dependent indicators; using the birthday formula for one-vs-many comparisons; saying a geometric retry "is due"; quoting as the exact quicksort count.

Quick quiz

1. A random permutation of 8 elements. Expected number of positions with ?

Answer
  1. Each position is fixed with probability , and there are 8 positions.

2. Expected number of records in a random permutation of 4 elements, as a fraction?

Answer

.

3. Expected inversions in a random permutation of 6 elements?

Answer

.

4. You need all 6 faces of a die. Expected rolls?

Answer

.

5. Markov's inequality says a non-negative variable with mean 10 exceeds 50 with probability at most what?

Answer

.

6. Expected colliding pairs when hashing 10,000 keys into values?

Answer

.

7. Why is the power of two choices exponentially better than one choice?

Answer

To reach load a ball must see two bins of load at least , so the fraction of heavy bins squares at each level: . Squaring reaches after levels instead of .

Further reading / sources

  • Michael Mitzenmacher and Eli Upfal, Probability and Computing (2nd ed., Cambridge, 2017) — indicators, coupon collector, Chernoff bounds, balls and bins, power of two choices, probabilistic method.
  • Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms (Cambridge, 1995).
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms (4th ed., 2022), Chapter 5 (hiring problem, indicator variables, birthday paradox, balls and bins, streaks) and §7.4 (randomized quicksort).
  • Donald E. Knuth, The Art of Computer Programming, Vol. 1, §1.2.10 (analysis of Algorithm M: records and harmonic numbers), and Vol. 3, §5.1.1 (inversions).
  • Noga Alon and Joel Spencer, The Probabilistic Method (4th ed., Wiley, 2016).
  • Yossi Azar, Andrei Broder, Anna Karlin and Eli Upfal, "Balanced Allocations", SIAM Journal on Computing 29(1), 1999 (STOC 1994).
  • Michael Mitzenmacher, "The Power of Two Choices in Randomized Load Balancing", IEEE Transactions on Parallel and Distributed Systems 12(10), 2001.
  • Martin Raab and Angelika Steger, "Balls into Bins — A Simple and Tight Analysis", RANDOM 1998.
  • Paul Erdős, "Some remarks on the theory of graphs", Bulletin of the AMS 53, 1947.
  • George Marsaglia, "Xorshift RNGs", Journal of Statistical Software 8(14), 2003.
  • Envoy documentation, Load balancers: weighted least request; NGINX documentation, random directive in ngx_http_upstream_module.
  • cp-algorithms, Modular inverse (linear-time inverses).

Lessons: module — Math for Algorithms · previous — Combinatorics · next — Linear Algebra · course — DSA: Zero to Mastery.

Related Archon pages: Probability for System Design · Probability & Expected-Value DP · Randomized Algorithms · Quick Sort · String Hashing · Hash Tables · Treaps, Splay Trees & Skip Lists · Load Balancing Algorithms · Game Theory.