Monte Carlo vs. Las Vegas Algorithms — Two Types of Randomization

Why This Distinction Matters

Randomized algorithms fall into two categories, named after famous casino cities. Understanding the difference is essential for choosing the right algorithm for your problem:

• Monte Carlo algorithms are fast but may produce incorrect results with bounded probability
• Las Vegas algorithms always produce correct results but have randomized runtime

Why this matters for your career:

• Interview questions often ask: "Is this randomized algorithm Monte Carlo or Las Vegas?"
• Choosing the right type affects system reliability, correctness guarantees, and user experience
• Monte Carlo algorithms are common in ML, data science, and simulations
• Las Vegas algorithms are preferred when correctness is critical (banking, medical)

Las Vegas Algorithms

A Las Vegas algorithm always returns the correct answer. Its runtime is a random variable — it may be fast or slow depending on the random choices made.

Properties

| Property | Description | |----------|-------------| | Correctness | Always correct (deterministic output) | | Runtime | Random variable — we analyze expected runtime | | Termination | May never terminate in worst case (probability zero) | | Failure mode | Slow but never wrong |

Examples

| Algorithm | Expected Runtime | Notes | |-----------|-----------------|-------| | Randomized Quicksort | O(n log n) | Random pivot, always sorts correctly | | Quickselect | O(n) | Random pivot, always finds correct k-th element | | Randomized Binary Search | O(log n) | Random probing order | | Treap (Randomized BST) | O(log n) | Random priorities ensure balanced tree | | Karger-Stein Min-Cut | O(n² log³ n) | Recurse for guaranteed correct answer |

Implementation Pattern

def randomized_quicksort(arr):
    """
    Las Vegas algorithm: always sorts correctly.
    Runtime varies based on random pivot selection.
    Expected: O(n log n). Worst case: O(n²) with probability ~0.
    """
    if len(arr) <= 1:
        return arr
    pivot = random.choice(arr)
    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 randomized_quicksort(left) + mid + randomized_quicksort(right)

Monte Carlo Algorithms

A Monte Carlo algorithm may produce incorrect results, but the probability of error is bounded and can be made arbitrarily small by running more trials.

Properties

| Property | Description | |----------|-------------| | Correctness | Probably correct (bounded error probability) | | Runtime | Usually deterministic or bounded | | Termination | Always terminates in bounded time | | Failure mode | Wrong answer (rarely) but never slow |

Examples

| Algorithm | Error Probability | Notes | |-----------|-----------------|-------| | Karger's Min-Cut | 1/n after n² log n trials | May output wrong cut, but unlikely | | Freivalds' Matrix Check | ≤ 1/2 per trial | Verify matrix multiplication | | Primality Testing (Miller-Rabin) | ≤ 1/4^k per trial | Fast prime checking | | Approximate Counting | ε error with probability 1-δ | Stream cardinality estimation | | Random Projection (JL Lemma) | Preserves distances w.h.p. | Dimensionality reduction |

Implementation Pattern

def is_prime_miller_rabin(n, k=40):
    """
    Monte Carlo algorithm: may say prime when composite.
    Error probability ≤ 1/4^k ≈ 10^-24 for k=40.
    """
    if n < 2:
        return False
    if n < 4:
        return True
    if n % 2 == 0:
        return False

    # Write n-1 as 2^r * d
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2

    for _ in range(k):
        a = random.randint(2, n - 2)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue

        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False  # definitely composite

    return True  # probably prime

Comparison Table

| Aspect | Las Vegas | Monte Carlo | |--------|-----------|-------------| | Output correctness | Always correct | May be wrong (bounded probability) | | Runtime | Random variable (expected time) | Usually deterministic | | Error source | Never wrong | Wrong answer with small probability | | Amplification | Cannot improve correctness | Run more trials to reduce error | | Use case | Must be correct (finance, medical) | Can tolerate errors (ML, simulation) | | Examples | Quicksort, Quickselect | Miller-Rabin, Karger's min-cut | | Termination guarantee | May run forever (prob. zero) | Always terminates |

When to Use Each

| Scenario | Best Choice | Reason | |----------|-------------|--------| | Sorting a list | Las Vegas | Must be correctly sorted | | Checking if a number is prime | Monte Carlo | Miller-Rabin is fast, error is negligible | | Finding minimum cut | Monte Carlo | Karger's may be wrong but we run many trials | | Password verification | Las Vegas | Must be absolutely correct | | Machine learning training | Monte Carlo | SGD is inherently random, convergence is probabilistic | | Database query execution | Las Vegas | Query results must be accurate | | Streaming cardinality estimation | Monte Carlo | HyperLogLog gives approximate counts | | Cryptography | Las Vegas | Encryption/decryption must be exact |

Converting Between Types

Sometimes you can convert one type to the other:

Las Vegas → Monte Carlo: If a Las Vegas algorithm takes too long, abort and return a best-effort answer. This creates a Monte Carlo algorithm.

Monte Carlo → Las Vegas: Run a Monte Carlo algorithm that can verify its answer. If the answer is wrong, retry. This creates a Las Vegas algorithm.

Example: Verifiable Monte Carlo → Las Vegas

def verify_matrix_product(A, B, C):
    """Freivalds' algorithm: verify if C = A * B in O(n²) time."""
    n = len(A)
    r = [random.randint(0, 1) for _ in range(n)]
    # Check if A * (B * r) == C * r
    Br = matrix_vector_multiply(B, r)
    ABr = matrix_vector_multiply(A, Br)
    Cr = matrix_vector_multiply(C, r)
    return ABr == Cr

def las_vegas_matrix_multiply(A, B, true_multiply):
    """Las Vegas matrix multiply using Monte Carlo verification."""
    while True:
        C = true_multiply(A, B)  # standard O(n³) or Strassen
        if verify_matrix_product(A, B, C):
            return C
        # If verification failed, recompute (rare)

Summary

The Monte Carlo vs. Las Vegas distinction is fundamental to randomized algorithm design. Las Vegas algorithms are always correct but have variable runtime — good when correctness is critical. Monte Carlo algorithms are fast but may err with bounded probability — good when speed matters and small errors are acceptable.

Key takeaways:

• Las Vegas: always correct, randomized runtime (e.g., Quicksort, Quickselect)
• Monte Carlo: always bounded runtime, may be wrong (e.g., Miller-Rabin, Karger)
• Las Vegas algorithms are preferred when correctness is non-negotiable
• Monte Carlo algorithms are preferred when speed matters and errors are tolerable
• Error probability can be reduced by running more independent trials
• Some problems can be solved with either approach depending on requirements
• Understanding both types helps you choose the right tool for each problem

What's Next: Randomized Quicksort

The next chapter dives deep into Randomized Quicksort — implementation, analysis, and why random pivot selection guarantees O(n log n) expected time.

Historical Context

The terms "Monte Carlo" and "Las Vegas" were coined by researchers at the RAND Corporation and later popularized by computer scientists:

• Monte Carlo (1940s): Named after the Monaco casino by Stanislaw Ulam and John von Neumann, who developed the method while working on nuclear weapons simulations at Los Alamos.
• Las Vegas (1980s): Named by László Babai to contrast with Monte Carlo — in Las Vegas, you always win (correct answer), but the time varies.

The naming is memorable and captures the essence: Monte Carlo is about gambling with correctness, Las Vegas is about gambling with time.