Randomized Algorithms6 min read

Las Vegas vs Monte Carlo

Correct-always vs probably-correct — two flavors of randomized algorithms
Las Vegas:Always correct, random runtimeMonte Carlo:Fixed runtime, probably correct

Most algorithms follow a fixed recipe: given the same input, they always take the exact same steps. But some of the most elegant algorithms in computer science flip coins along the way. They make random decisions — and somehow, they still work correctly (or almost always work correctly) and are blazing fast.

These are randomized algorithms. Randomness isn't a flaw — it's the whole point. It's used to get simpler code, avoid adversarial inputs, or achieve average-case speeds that deterministic algorithms can't match.

Two Flavors: Las Vegas and Monte Carlo

There are two camps of randomized algorithms, named after casinos (the connection: both involve gambling, but in different ways).

A Las Vegas algorithm always produces the correct answer. The only thing that varies is how long it takes. Think of it like a slot machine that always pays out eventually — you just don't know when. Randomized QuickSort is the classic example: no matter what, the output is a sorted array. Only the runtime depends on the random pivot choices.

A Monte Carlo algorithm always finishes in a fixed amount of time but might occasionally give a wrong answer. The probability of being wrong is tiny and controllable. The Miller-Rabin primality test is canonical: run it k times, and the probability of a false positive drops to 4^(-k). At k=40, that's 1 in a trillion — safe for any practical purpose.

Why Not Just Use Deterministic Algorithms?

Two big reasons:

  • Adversarial inputs: A deterministic algorithm has a fixed worst case that an attacker can engineer. If your hash table always uses the same hash function, an adversary can craft inputs where everything collides, degrading every operation to \(O(n)\). A randomized hash function makes this essentially impossible — the attacker doesn't know which function you'll pick.
  • Simplicity: Many randomized algorithms are dramatically simpler to implement and analyze than their deterministic counterparts with equivalent guarantees. Randomized QuickSort is 5 lines; Median-of-Medians (deterministic \(O(n \log n)\) guaranteed sort) is dozens.

Probability Amplification

Monte Carlo algorithms become arbitrarily reliable through repetition. If one run gives a wrong answer with probability 1/4, running it k times independently and taking the majority vote drops the error probability to exponentially small in k. This is probability amplification — a powerful general technique.

Note: Las Vegas: the casino always pays you — you just don't know when. Monte Carlo: you get your result on time, but there's a tiny chance it's wrong. Both are incredibly useful, and the choice depends on whether you care more about correctness or predictable runtime.

Las Vegas vs Monte Carlo — Examples

import random


# --- Las Vegas Example ---
# Random pivot selection in QuickSort: always correct, runtime varies
def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = random.choice(arr)  # random pivot!
    left  = [x for x in arr if x < pivot]
    mid   = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + mid + quicksort(right)


print(quicksort([3, 1, 4, 1, 5, 9, 2, 6]))  # always sorted


# --- Monte Carlo Example ---
# Estimate pi using random points in a square
def estimate_pi(n_samples):
    inside = sum(
        1 for _ in range(n_samples)
        if random.random()**2 + random.random()**2 <= 1
    )
    return 4 * inside / n_samples


print(f"pi ≈ {estimate_pi(100000):.4f}")  # close but not exact
Output
[1, 1, 2, 3, 4, 5, 6, 9]
pi ≈ 3.1412

Complexity

✅ Las Vegas correctnessRandomness only affects runtime, never the result — output is always valid
Guaranteed correct — alwaysP(error) = 0
⏱️ Las Vegas runtimeExpected runtime is the key metric; worst case may exist but is astronomically unlikely
Variable — analyze in expectationE[T] bounded
⏰ Monte Carlo runtimeAlways completes in the promised time — no variance in runtime
Fixed — always finishes on timeT(n) deterministic
🎲 Monte Carlo correctnessError probability can be driven exponentially small by running more rounds
Probably correctP(error) ≤ ε

Quick check

Randomized QuickSort always returns a sorted array. Which type of randomized algorithm is it?

Continue reading

Randomized Quick Sort
A random pivot destroys adversarial worst-case inputs
→
Reservoir Sampling
Sample k items fairly from a stream you see only once
→
Bloom Filter
Probably yes, definitely no — a memory-sipping membership checker
→