Probability in Algorithms, in depth: Las Vegas and Monte Carlo contracts, amplification, Freivalds, fingerprinting and Karger's min cut

Two contracts: Las Vegas and Monte Carlo

Every randomized algorithm falls into one of two families, and choosing between them is the first design decision.

Monte Carlo algorithms split further by the shape of their error. A one-sided algorithm can only be wrong in one direction. Miller-Rabin never calls a prime composite; it can only occasionally call a composite prime. A two-sided algorithm can err either way, as a sampling-based estimate can. The distinction matters because it decides how repetition works.

Amplification: buying down the error

Suppose a one-sided algorithm answers "no" correctly whenever the truth is no, and answers "yes" wrongly with probability at most e. Run it k times with fresh random bits and answer "no" if any run says no. All k runs must fail independently for the combined answer to be wrong, so the error is at most e^k. With e = 1/2 and k = 40 the error is below one in a trillion, smaller than the chance of a hardware fault during the computation.

Two-sided error needs a majority vote instead. If each run is correct with probability at least 1/2 + d for some margin d > 0, the majority of k runs is wrong with probability at most exp(-2d²k), by a Hoeffding-style bound. The margin is essential: an algorithm that is right with probability exactly 1/2 is a coin flip, and no amount of voting helps. Note the quadratic dependence: halving the margin needs four times as many runs.

The practical rule is to state a target error, such as 2^-40, and compute k from it, rather than repeating "a few times". Independence matters as much as the count: runs that reuse a seed are one run repeated, not k runs.

Verification: Freivalds' algorithm

Given n by n matrices A, B and C, is AB = C? Recomputing the product costs about n³ operations with the schoolbook method. Freivalds' algorithm checks it in O(n²) per trial: pick a random vector r with entries in {0, 1}, compute A(Br) and Cr with three matrix-vector products, and compare.

import random

def matvec(M, v):
    return [sum(row[j] * v[j] for j in range(len(v))) for row in M]

def freivalds(A, B, C, trials=40, rng=random.Random()):
    n = len(A)
    for _ in range(trials):
        r = [rng.randint(0, 1) for _ in range(n)]
        if matvec(A, matvec(B, r)) != matvec(C, r):
            return False          # certainly AB != C: one-sided, never wrong here
    return True                   # AB == C with error <= 2**-trials

Why does one trial catch a wrong C with probability at least 1/2? Let D = AB - C, nonzero, and pick an entry D_ij that is not zero. Row i of Dr equals D_ijr_j plus a sum S that does not involve r_j. Fix all other coordinates of r; then at most one of the two values of r_j can make D_ijr_j + S equal zero. So Dr = 0 with probability at most 1/2. This principle-of-deferred-decisions argument is the template for many proofs: expose the randomness one coordinate at a time and look at the last one.

Use it whenever an expensive result arrives from somewhere you do not fully trust: a GPU kernel you just wrote, a distributed job, a third-party service. Verification is cheaper than recomputation, and with exact integer or modular arithmetic it has no false alarms. With floating point, compare with a tolerance and accept that the guarantee becomes approximate.

Fingerprinting and the Schwartz-Zippel lemma

Freivalds is a special case of a broader idea: compare two large objects by comparing a random small summary of each. The engine behind it is the Schwartz-Zippel lemma: a nonzero polynomial of total degree d, evaluated at a point chosen uniformly from a finite set S in each coordinate, is zero with probability at most d/|S|.

Apply it to strings. Treat a string a₀...a_n-1 as the polynomial sum a_ixⁱ over the integers modulo a prime p. Two different strings give a nonzero difference polynomial of degree below n, so evaluating both at a random x collides with probability at most (n - 1)/p. Two machines holding a gigabyte file each can decide whether the files are equal by exchanging one number. This is the same structure as the polynomial string hash, with one crucial difference: the evaluation point must be chosen at random after the strings are fixed, or an adversary can build collisions.

import secrets

P = (1 << 61) - 1                     # a Mersenne prime

def fingerprint(data: bytes, x: int) -> int:
    h = 0
    for byte in reversed(data):       # Horner: sum data[i] * x**i mod P
        h = (h * x + byte) % P
    return h

x = secrets.randbelow(P - 1) + 1      # chosen AFTER both inputs exist
same = fingerprint(file_a, x) == fingerprint(file_b, x)
# false "same" w.p. <= (len - 1) / P, about 4e-10 for a 1 GB file

The same lemma tests polynomial identities that would be exponentially large to expand symbolically, and underlies randomized algorithms for perfect matching via determinants.

Worked example: Karger's minimum cut

The global minimum cut of an undirected graph is the smallest set of edges whose removal disconnects it. Karger's contraction algorithm is almost absurdly simple: while more than two vertices remain, pick a uniformly random edge and merge its endpoints, keeping parallel edges and deleting self-loops. When two super-vertices remain, the edges between them form a cut.

Why does it find the minimum cut often enough? Fix a minimum cut of size k. Every vertex has degree at least k, or its own edges would be a smaller cut, so a graph with m vertices has at least mk/2 edges. The chance that a random edge is in the cut is at most k/(mk/2) = 2/m. The cut survives all contractions with probability at least the product of (1 - 2/m) for m from n down to 3, which telescopes to 2/(n(n - 1)). That is small, but it is not exponentially small, so repetition fixes it.

import math, random

def karger_once(n, edges, rng):
    parent = list(range(n))
    def find(v):
        while parent[v] != v:
            parent[v] = parent[parent[v]]
            v = parent[v]
        return v
    order = edges[:]
    rng.shuffle(order)           # contracting in random order = random edge each step
    groups = n
    for u, v in order:
        if groups == 2:
            break
        ru, rv = find(u), find(v)
        if ru != rv:             # skip edges that became self-loops
            parent[ru] = rv
            groups -= 1
    return sum(1 for u, v in edges if find(u) != find(v))

def karger(n, edges, seed=0):
    rng = random.Random(seed)
    runs = math.ceil(n * (n - 1) / 2 * math.log(n))
    return min(karger_once(n, edges, rng) for _ in range(runs))

Shuffling the edges once and contracting in that order is equivalent to choosing a random remaining edge at each step, and with union-find each run is nearly linear in the number of edges. With C(n, 2) ln n runs the failure probability is at most 1/n. For a 50-vertex graph that is about 4,800 runs, each touching every edge, which is fine for a test but explains why production code uses the Karger-Stein refinement, which repeats only the late, risky contractions, or the deterministic Stoer-Wagner algorithm.

Converting between the contracts

A Las Vegas algorithm with expected running time T becomes Monte Carlo by stopping it after 2T steps and reporting failure. By Markov's inequality the time exceeds 2T with probability at most 1/2, so the truncated algorithm fails at most half the time, and repetition takes it lower. This is how you put a hard deadline on randomized quicksort inside a real-time system.

The other direction needs a verifier. If a Monte Carlo answer can be checked quickly and with certainty, loop: run, check, retry on failure. The result is always correct, and with success probability q per round the expected number of rounds is 1/q. Finding a large prime this way, by sampling and testing, gives a Las Vegas algorithm only if the test is certain; with Miller-Rabin the result stays Monte Carlo with a tiny error, which is why key generation states its error bound explicitly.

Randomness in real systems

The analysis assumes perfect, independent random bits. Real systems have generators, seeds and adversaries, and most production failures of randomized algorithms come from here rather than from the mathematics.

• Choose the generator by threat. Statistical generators such as a Mersenne Twister or PCG are fine for simulation and Karger. If an adversary benefits from predicting your choices, as with hash-table seeds facing hash-flooding attacks or fingerprint points facing chosen collisions, use a cryptographic source.
• Pass a generator, never use global state. The functions above take an rng argument so tests can fix a seed and production can supply a fresh one.
• Log the seed. A rare wrong answer that cannot be replayed cannot be debugged.
• Test the distribution, not one output. Run thousands of seeds and check the empirical error rate against the bound with a confidence interval; a single green test on one seed proves almost nothing.
• Watch for hidden correlation. Forked worker processes that inherit one generator state produce identical random streams, quietly turning k independent runs into one.

Trade-offs

Randomization is the right choice when the deterministic alternative is much more complex or much slower, when adversarial inputs are a real risk, or when verification is cheaper than computation. It is the wrong choice when results must be bitwise reproducible without seed management, when a regulator or auditor needs a deterministic proof, or when the error, however small, lands on a path where one mistake is catastrophic and no verifier exists. Between those poles, prefer Las Vegas when correctness is non-negotiable and the time tail is acceptable, and Monte Carlo when the deadline is fixed and the error can be driven below other failure rates in the system.

What to do next

1. For each randomized component you own, write down its contract: Las Vegas or Monte Carlo, one-sided or two-sided, and the error or time bound.
2. Set an explicit error target and derive the repetition count from it.
3. Add a Freivalds-style check to one expensive computation you do not fully trust.
4. Implement Karger with a seeded generator and compare it against Stoer-Wagner on random graphs to see the error rate fall as runs increase.
5. Audit where your code draws randomness: generator type, seeding, forking, and whether an adversary can predict it.
6. Build a seed-sweep test that checks empirical error rates against the stated bound.