Randomized Algorithms: Monte Carlo and Las Vegas

Key Insights

Monte Carlo algorithms guarantee fast execution but may return incorrect results, while Las Vegas algorithms guarantee correctness but have variable runtime—choosing between them depends on whether you can tolerate errors or latency spikes.
You can amplify the success probability of Monte Carlo algorithms exponentially by running them multiple times, making even 51% accurate algorithms arbitrarily reliable.
Both algorithm types are convertible under the right conditions: Monte Carlo becomes Las Vegas when results are verifiable, and Las Vegas becomes Monte Carlo by adding timeouts.

Introduction to Randomized Algorithms

Deterministic algorithms feel safe. Given the same input, they produce the same output every time. But this predictability comes at a cost—sometimes the best deterministic solution is too slow, too complex, or simply unknown.

Randomized algorithms flip this constraint on its head. By introducing controlled randomness, we can often achieve better average-case performance, simpler implementations, and solutions to problems where deterministic approaches struggle.

You’re already using randomized algorithms daily. Cryptographic key generation relies on randomness. Load balancers use random selection to distribute traffic. Machine learning models shuffle training data and initialize weights randomly. Distributed systems use randomized protocols for leader election and consensus.

The two fundamental categories of randomized algorithms—Monte Carlo and Las Vegas—represent different tradeoffs between correctness and performance. Understanding when to use each is essential for building robust systems.

Monte Carlo Algorithms: Trading Accuracy for Speed

Monte Carlo algorithms always terminate in bounded time but may return incorrect results. The key insight is that we can control the error probability, often making it negligibly small.

Errors come in two flavors. One-sided error algorithms only fail in one direction—they might return false negatives but never false positives (or vice versa). Two-sided error algorithms can fail in either direction.

The power of Monte Carlo lies in probability amplification. If an algorithm has a 75% success rate, running it 10 times and taking the majority answer pushes success probability above 99.9%. This exponential improvement makes even weak algorithms practical.

The Miller-Rabin primality test exemplifies Monte Carlo elegance. Testing whether a number is prime deterministically requires expensive factorization, but Miller-Rabin gives us a fast probabilistic answer:

import random

def miller_rabin(n: int, k: int = 40) -> bool:
    """
    Monte Carlo primality test.
    Returns True if n is probably prime, False if definitely composite.
    Error probability: at most 4^(-k)
    """
    if n < 2:
        return False
    if n == 2 or n == 3:
        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
    
    def check_witness(a: int) -> bool:
        """Returns True if a is a witness for n being composite."""
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            return False
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                return False
        return True
    
    # Test k random witnesses
    for _ in range(k):
        a = random.randrange(2, n - 1)
        if check_witness(a):
            return False  # Definitely composite
    
    return True  # Probably prime


# With k=40, error probability is less than 1 in 10^24
print(miller_rabin(104729))  # True (prime)
print(miller_rabin(104730))  # False (composite)

This algorithm has one-sided error: if it returns False, the number is definitely composite. If it returns True, there’s a tiny chance it’s wrong. With 40 iterations, that chance is smaller than the probability of a cosmic ray flipping a bit in your RAM.

Las Vegas Algorithms: Guaranteed Correctness, Variable Runtime

Las Vegas algorithms take the opposite stance: the answer is always correct, but runtime varies. We analyze them using expected runtime—the average time across all possible random choices.

The classic example is randomized QuickSort. Deterministic QuickSort with a fixed pivot strategy can degrade to O(n²) on adversarial inputs. Random pivot selection gives O(n log n) expected time regardless of input:

import random
from typing import List

def randomized_quicksort(arr: List[int]) -> List[int]:
    """
    Las Vegas sorting algorithm.
    Always correct, O(n log n) expected time.
    """
    if len(arr) <= 1:
        return arr
    
    # Random pivot selection defeats adversarial inputs
    pivot_idx = random.randrange(len(arr))
    pivot = arr[pivot_idx]
    
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    return randomized_quicksort(left) + middle + randomized_quicksort(right)


def median_of_three_quicksort(arr: List[int]) -> List[int]:
    """
    Alternative pivot strategy: median of three random elements.
    Better constant factors in practice.
    """
    if len(arr) <= 1:
        return arr
    
    if len(arr) <= 3:
        pivot = arr[random.randrange(len(arr))]
    else:
        # Sample three random elements, take median
        samples = random.sample(arr, 3)
        samples.sort()
        pivot = samples[1]
    
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    return median_of_three_quicksort(left) + middle + median_of_three_quicksort(right)

The tradeoff is clear: Monte Carlo gives you predictable latency with potential errors; Las Vegas gives you correctness with potential latency spikes.

Probability Analysis Fundamentals

Analyzing randomized algorithms requires basic probability tools. The most important is expected value—the weighted average of all possible outcomes.

For Las Vegas algorithms, we care about expected runtime. For Monte Carlo, we care about error probability. Both benefit from understanding how repeated trials behave.

Here’s a practical harness for empirically measuring both:

import time
import statistics
from typing import Callable, Any, Tuple
from dataclasses import dataclass

@dataclass
class AlgorithmStats:
    mean_time: float
    std_time: float
    accuracy: float
    trials: int

def benchmark_algorithm(
    algorithm: Callable[..., Any],
    inputs: list,
    expected_outputs: list,
    trials: int = 100
) -> AlgorithmStats:
    """
    Measure runtime distribution and accuracy of a randomized algorithm.
    """
    times = []
    correct = 0
    
    for _ in range(trials):
        for inp, expected in zip(inputs, expected_outputs):
            start = time.perf_counter()
            result = algorithm(inp)
            elapsed = time.perf_counter() - start
            
            times.append(elapsed)
            if result == expected:
                correct += 1
    
    total_runs = trials * len(inputs)
    return AlgorithmStats(
        mean_time=statistics.mean(times),
        std_time=statistics.stdev(times) if len(times) > 1 else 0,
        accuracy=correct / total_runs,
        trials=total_runs
    )


# Example: Compare Miller-Rabin accuracy at different iteration counts
test_primes = [104729, 1299709, 15485863]
test_composites = [104730, 1299710, 15485864]

for k in [1, 5, 10, 20]:
    def test_algo(n, k=k):
        return miller_rabin(n, k)
    
    stats = benchmark_algorithm(
        test_algo,
        test_primes + test_composites,
        [True] * 3 + [False] * 3,
        trials=1000
    )
    print(f"k={k:2d}: accuracy={stats.accuracy:.4f}, mean_time={stats.mean_time*1e6:.1f}µs")

Chernoff bounds tell us that the sum of independent random variables concentrates tightly around its expectation. In practice, this means that running a Monte Carlo algorithm many times gives highly predictable aggregate behavior, even though individual runs are random.

Practical Applications and Case Studies

Karger’s minimum cut algorithm demonstrates the power of randomized approaches. Finding the minimum cut in a graph deterministically is complex, but Karger’s algorithm is beautifully simple:

import random
from typing import List, Tuple, Set
from collections import defaultdict
import copy

def karger_min_cut(edges: List[Tuple[int, int]]) -> int:
    """
    Monte Carlo algorithm for minimum cut.
    Returns the size of a cut (may not be minimum on any single run).
    Run O(n^2 log n) times for high probability of finding true min cut.
    """
    # Build adjacency representation with parallel edges
    graph = defaultdict(list)
    vertices = set()
    
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
        vertices.add(u)
        vertices.add(v)
    
    # Contract until 2 vertices remain
    while len(vertices) > 2:
        # Pick random edge
        u = random.choice(list(vertices))
        if not graph[u]:
            vertices.remove(u)
            continue
        v = random.choice(graph[u])
        
        # Contract: merge v into u
        for neighbor in graph[v]:
            if neighbor != u:
                graph[u].append(neighbor)
                graph[neighbor].append(u)
            # Remove v from neighbor's list
            graph[neighbor] = [x for x in graph[neighbor] if x != v]
        
        # Remove self-loops
        graph[u] = [x for x in graph[u] if x != v]
        del graph[v]
        vertices.remove(v)
    
    # Remaining edges cross the cut
    if vertices:
        u = next(iter(vertices))
        return len(graph[u])
    return 0


def repeated_karger(edges: List[Tuple[int, int]], trials: int = None) -> int:
    """
    Run Karger's algorithm multiple times, return minimum cut found.
    """
    n = len(set(v for e in edges for v in e))
    if trials is None:
        trials = n * n  # Gives ~1/n failure probability
    
    min_cut = float('inf')
    for _ in range(trials):
        cut = karger_min_cut(copy.deepcopy(edges))
        min_cut = min(min_cut, cut)
    
    return min_cut

Skip lists are a Las Vegas data structure—they always return correct results, but operation times vary based on the random structure. They provide O(log n) expected time for search, insert, and delete, matching balanced trees with simpler implementation.

Converting Between Algorithm Types

Sometimes you need to convert between Monte Carlo and Las Vegas. The conversions aren’t always possible, but when they are, they’re powerful.

Monte Carlo → Las Vegas works when you can verify results. If checking correctness is cheap, run the Monte Carlo algorithm and verify; repeat until correct.

Las Vegas → Monte Carlo works by adding a timeout. If the algorithm hasn’t finished, return a default answer or random guess.

import threading
from typing import TypeVar, Callable, Optional
from concurrent.futures import ThreadPoolExecutor, TimeoutError

T = TypeVar('T')

class AlgorithmConverter:
    """Patterns for converting between Monte Carlo and Las Vegas algorithms."""
    
    @staticmethod
    def monte_carlo_to_las_vegas(
        monte_carlo_algo: Callable[..., T],
        verifier: Callable[[T], bool],
        max_attempts: int = 1000
    ) -> Callable[..., Optional[T]]:
        """
        Convert Monte Carlo to Las Vegas by verifying results.
        Requires a cheap verification function.
        """
        def las_vegas_wrapper(*args, **kwargs) -> Optional[T]:
            for _ in range(max_attempts):
                result = monte_carlo_algo(*args, **kwargs)
                if verifier(result):
                    return result
            return None  # Failed to find valid result
        
        return las_vegas_wrapper
    
    @staticmethod
    def las_vegas_to_monte_carlo(
        las_vegas_algo: Callable[..., T],
        timeout_seconds: float,
        default_value: T
    ) -> Callable[..., T]:
        """
        Convert Las Vegas to Monte Carlo by adding timeout.
        Returns default_value if algorithm doesn't complete in time.
        """
        def monte_carlo_wrapper(*args, **kwargs) -> T:
            with ThreadPoolExecutor(max_workers=1) as executor:
                future = executor.submit(las_vegas_algo, *args, **kwargs)
                try:
                    return future.result(timeout=timeout_seconds)
                except TimeoutError:
                    return default_value
        
        return monte_carlo_wrapper

Choosing the Right Approach

Use this decision framework:

Factor	Choose Monte Carlo	Choose Las Vegas
Correctness	Errors tolerable or detectable	Must be correct
Latency	Strict SLA required	Variable latency OK
Verification	Expensive or impossible	Cheap to verify
Use case	Approximation, estimation	Exact computation

Choose Monte Carlo when: You’re doing approximate counting, probabilistic data structures (Bloom filters, HyperLogLog), or when downstream systems can handle occasional errors. Web analytics, recommendation systems, and monitoring often fit here.

Choose Las Vegas when: Correctness is non-negotiable but you can tolerate occasional slow responses. Database operations, financial calculations, and cryptographic operations typically require Las Vegas guarantees.

The best engineers understand both paradigms and choose deliberately. Randomness isn’t a cop-out—it’s a powerful tool that often yields simpler, faster, and more robust solutions than deterministic alternatives.