Las Vegas Algorithms, in depth: runtime distributions, heavy tails, Luby restarts and engineering always-correct randomness

The contract and what expected time hides

Formally, a Las Vegas algorithm either always halts with a correct answer, or (in the weaker form) halts with a correct answer or an explicit "failed", never a wrong answer. Its running time T is a random variable over the algorithm's own coin flips. It is not averaged over inputs. The bound is for every input, and the expectation is over the randomness. That distinction is the point. Deterministic quicksort with a fixed pivot rule is fast on average over random inputs, but some inputs (sorted ones, for the first-element rule) are always slow. Randomized quicksort has no bad input, only unlucky coin flips, and those are not reproducible by an adversary who does not see the coins.

Markov's inequality gives a tail bound for free: P(T at least k E[T]) is at most 1/k. That bound is weak, but it is what makes restarts work. Stop a run at 2E[T] and it has failed with probability at most 1/2. Independent restarts then make the chance of m consecutive failures at most 2^-m. A known mean therefore always buys an exponential tail, at a constant-factor cost. The rest of this article is about what happens when you do not know the mean, or the tail is much worse than the median suggests.

Three ways to build one

Randomize choices that affect only cost. Quickselect's pivot changes how much work is done, never which element is returned. The same holds for treap priorities, skip-list levels and a hash function's seed. Correctness rests on a deterministic invariant; randomness only makes bad cases unlikely.

Guess and verify. If candidates are cheap to draw, a fixed fraction of them are good, and goodness can be checked with certainty, then loop until a check passes. Finding a quadratic non-residue modulo a prime (a step in Tonelli-Shanks square roots) is the classic case: exactly half the nonzero residues qualify, and Euler's criterion verifies one exactly. If the checker is itself probabilistic, the result is Monte Carlo, not Las Vegas.

Randomized search with a checkable goal. Backtracking with random value ordering, randomized local search and SAT solvers with random tie-breaking all return only solutions they have checked. Their running time is where heavy tails live.

import random

def quickselect(a, k, rng):
    """k-th smallest (0-based). Always correct; only the work is random."""
    a = list(a); lo, hi = 0, len(a) - 1
    while True:
        if lo == hi:
            return a[lo]
        p = a[rng.randint(lo, hi)]                    # the only random choice
        lt = [x for x in a[lo:hi + 1] if x < p]
        eq = [x for x in a[lo:hi + 1] if x == p]
        gt = [x for x in a[lo:hi + 1] if x > p]
        a[lo:hi + 1] = lt + eq + gt
        if k < lo + len(lt):              hi = lo + len(lt) - 1
        elif k < lo + len(lt) + len(eq):  return p
        else:                             lo = lo + len(lt) + len(eq)

def nonresidue(p, rng):
    """A quadratic non-residue mod an odd prime p: guess, then verify with Euler's criterion."""
    while True:
        a = rng.randrange(2, p)
        if pow(a, (p - 1) // 2, p) == p - 1:          # certain check, so the output is certain
            return a

Both functions return only correct answers: the partition invariant guarantees quickselect's result, and Euler's criterion guarantees the non-residue. Only the number of loop iterations is random. A deterministic linear-time selection algorithm exists (median of medians; see selection and medians), but its constant factor is large, which is why libraries use the randomized version or an introselect hybrid.

Measured: three runtime distributions

Run the code and look at distributions, not just means. Quickselect for the median of a shuffled list of 10,001 values, 2,000 runs: the work (elements examined across all partition passes) averaged 3.378n, close to the theoretical expected comparison count for the median, (2 + 2 ln 2)n, about 3.386n. The median run was 3.28n, the 99th percentile 6.25n and the worst of 2,000 runs 7.63n. That is a concentrated distribution: the tail is real, but no run cost more than about 2.3 times the mean.

The non-residue search modulo 1,000,000,007, 100,000 runs, averaged 2.005 tries. Theory says exactly 2, because each try succeeds with probability 1/2. The worst run needed 16 tries, and 0.101% of runs needed more than 10, against the geometric prediction of 2^-10, about 0.098%. A geometric tail is the best a Las Vegas algorithm can have: each extra try halves the remaining probability, and restarting cannot help because every try already is a fresh start.

Randomized backtracking for 40 queens is different. With random column order per row, 300 runs, counting queen placements: median 379, mean 8,467, worst 687,271. The mean is 22 times the median. Most runs are quick, and a few wander into a hopeless subtree near the root and spend hundreds of thousands of steps proving it hopeless. This is a heavy-tailed distribution, the shape reported for randomized backtracking and SAT search by Gomes, Selman and colleagues. For this shape, the expected time is dominated by rare disasters, and the remedy is to stop waiting for them.

Restart strategies and the Luby sequence

A restart strategy is a sequence of budgets t1, t2, ...: run with fresh randomness for at most t1 steps, then t2, and so on until success. Luby, Sinclair and Zuckerman (1993) proved two results that frame the whole topic. First, for any known distribution some fixed cutoff t*, repeated forever, is optimal; call its expected total time T*. Second, if you do not know the distribution, the universal sequence 1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 1, 1, 2, 4, 8, ... achieves expected time O(T* log T*) on every distribution, and no universal strategy does better by more than a constant factor. The sequence spends roughly equal total effort on every power-of-two cutoff, so whichever cutoff is right gets its share.

def luby(i):
    """i-th term (1-based) of 1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 1, 1, 2, 4, 8, ..."""
    k = 1
    while (1 << k) - 1 < i:
        k += 1
    if i == (1 << k) - 1:
        return 1 << (k - 1)
    return luby(i - (1 << (k - 1)) + 1)

def solve_with_restarts(run, unit, rng):
    """run(rng, budget) -> answer or None. Fresh randomness each attempt."""
    i = 0
    while True:
        i += 1
        answer = run(rng, unit * luby(i))
        if answer is not None:
            return answer

The unit multiplier is the one tuning knob. It sets the scale of the smallest attempt and does not affect the asymptotic guarantee. Modern SAT solvers use Luby restarts, or adaptive schedules that are evaluated against them, as a standard component.

Worked example: restarting 40-queens search

The solver is plain backtracking with a random column order per row and a budget on placements. Wrapping it as run(rng, budget) plugs it into the restart loop above. Same seed, 300 runs per strategy, counting all placements including the budgets of abandoned attempts:

def queens(n, rng, budget):
    """Randomized backtracking. Returns (solution or None, placements used)."""
    cols, d1, d2, sol = set(), set(), set(), []
    nodes = 0
    def rec(r):
        nonlocal nodes
        if r == n:
            return True
        order = list(range(n)); rng.shuffle(order)       # random value ordering
        for c in order:
            if c in cols or (r - c) in d1 or (r + c) in d2:
                continue
            nodes += 1
            if nodes > budget:
                raise TimeoutError
            cols.add(c); d1.add(r - c); d2.add(r + c); sol.append(c)
            if rec(r + 1):
                return True
            cols.discard(c); d1.discard(r - c); d2.discard(r + c); sol.pop()
        return False
    try:
        rec(0)
        return list(sol), nodes
    except TimeoutError:
        return None, budget

Every restart strategy cut the mean by 6 to 16 times and the worst case by 45 to 240 times, while barely moving the median. That is the signature of a heavy tail: restarts throw away the rare disastrous runs and pay a small tax on the typical ones. The fixed cutoffs show the sensitivity Luby's result protects against: 200 was good, 5,000 was about two and a half times worse, and you would not know which without measuring. Luby with unit 50, deliberately small, still came within 20% of the best fixed cutoff tried. Run the same experiment on the non-residue search and restarts change nothing, because a geometric distribution has no tail to cut.

Engineering Las Vegas algorithms

Seeds and reproducibility. Log the seed of every run that matters, and make it injectable, as in the code above, so a slow or failing run can be replayed exactly. Tests should fix seeds, and a separate soak test should sweep many of them, because a single fixed seed hides the distribution you care about.

Adversaries. The expected-time guarantee assumes the input does not depend on the coins. If an attacker can learn or predict your seed, they can choose inputs that make every run unlucky. This is hash flooding, and it is why language runtimes seed hash functions per process. Use an unpredictable seed whenever inputs are untrusted.

Deadlines. When the caller has a hard deadline, cap the total budget and return "unknown" at the cap. This is the Las Vegas to Monte Carlo conversion, now with a failure you can report rather than a wrong answer. Callers must handle the failure, or the deadline becomes a hidden bug.

Portfolios. On a heavy-tailed distribution, k independent copies running in parallel finish when the fastest one does. That is an excellent use of idle cores, because the minimum of k heavy-tailed samples is far smaller than one sample. It is the same reasoning as restarts, spent in space instead of time.

What to keep across restarts. Pure restarts discard everything. Solvers that keep learned information (SAT clause learning, caches of proven-dead states) get the benefit of restarts without repeating proven work. Algorithms like Karger's min cut repeat runs too, but they are Monte Carlo: each run may be wrong, and repetition raises confidence rather than cutting time.

Failure modes

Trade-offs

Las Vegas trades a deterministic time bound for a deterministic correctness bound. When a deterministic algorithm of similar speed exists, as for sorting, prefer the one whose worst case you can state, or combine them, as introsort and introselect do: randomize, and fall back to a guaranteed method if the run goes badly. When verification is cheap and candidates are plentiful, guess-and-verify is hard to beat. For search problems, expect a heavy tail, measure the distribution rather than the mean, and treat restarts as part of the algorithm. Related techniques on this site: randomized pivots in quicksort and random rehashing in cuckoo hashing.

What to do next

1. List the randomized components in your code and classify each as cost-only randomness, guess-and-verify, or randomized search.
2. For each one, record the runtime of 1,000 seeded runs and plot the distribution. Compare the median, mean, 99th percentile and maximum.
3. If the mean is several times the median, add Luby restarts and rerun the measurement, starting with a unit near the median.
4. Check that every verifier is certain. If it is not, relabel the routine as Monte Carlo and document its error bound.
5. Make seeds injectable and logged, and use unpredictable seeds wherever inputs come from outside.
6. Give callers with deadlines an explicit "unknown" result rather than an open-ended loop.