19.2 Las Vegas Algorithms

A randomized algorithm can use randomness in several ways.

algorithmsrandomizedapproximation

19.2 Las Vegas Algorithms

A randomized algorithm can use randomness in several ways. Some algorithms use random choices to improve performance while guaranteeing that every answer produced is correct. Others use random choices to reduce running time while accepting a small probability of error. The first category is known as Las Vegas algorithms.

A Las Vegas algorithm always returns a correct result. Randomness affects the amount of work performed, not the correctness of the output. Different executions on the same input may require different running times, memory usage, or numbers of operations, but every successful execution produces the same correct answer.

This distinction is important because many practical systems can tolerate performance variation more easily than incorrect results. Database indexes, network routing systems, search engines, and compiler optimizations often rely on randomized techniques that preserve correctness while improving average performance.

Problem

You want the advantages of randomization without sacrificing correctness.

Questions include:

  • Can random choices improve performance?
  • Can worst-case inputs be avoided?
  • Can implementation be simplified?
  • Can expected running time be improved?
  • Can correctness remain guaranteed?

Las Vegas algorithms provide a framework for achieving these goals.

Recipe: The Las Vegas Model

A Las Vegas algorithm satisfies two properties:

Correctness

Every returned answer is correct.

P(correct answer) = 1

Variable Runtime

Execution time depends on random choices.

Runtime = random variable

Randomness influences efficiency rather than correctness.

Suppose an unsorted array contains a target value.

[7, 12, 5, 19, 8, 3]

Instead of scanning sequentially, we randomly inspect positions.

while positions_remain:
    i = random_unchecked_position()
    if array[i] == target:
        return i

The order of inspection changes between executions.

Some runs find the target quickly.

Others examine many positions.

However:

If the target exists,
the algorithm always finds it.

Correctness remains guaranteed.

Runtime becomes random.

Expected Runtime

Because running time varies, worst-case analysis alone provides limited insight.

Suppose a target appears in a random position among:

n elements

Expected number of inspections:

(n + 1) / 2

Average behavior is often more important than the worst case.

This shift toward expectation is one of the defining characteristics of randomized algorithm analysis.

Randomized Quicksort

The most famous Las Vegas algorithm is randomized quicksort.

Traditional quicksort selects a pivot according to a deterministic rule.

Examples:

First element
Last element
Middle element

Certain inputs cause extremely unbalanced partitions.

Example:

[1,2,3,4,5,6,7,8]

When the first element is always chosen as pivot:

Partition sizes:
0 and n−1

Repeatedly.

Result:

O(n²)

comparisons.

Randomized quicksort chooses:

pivot = random element

Each recursive call selects a new random pivot.

Poor partitions remain possible.

However, consistently poor partitions become extremely unlikely.

Analysis shows:

Expected runtime = O(n log n)

while correctness remains unchanged.

The sorted output is always correct.

Only the amount of work varies.

Why Randomization Helps

Many deterministic algorithms can be attacked by carefully chosen inputs.

Consider a web service that always uses:

first element as pivot

An attacker can intentionally provide worst-case data.

Runtime degrades significantly.

Randomization prevents the attacker from predicting algorithm behavior.

The input remains fixed.

The algorithm's decisions vary.

This idea appears repeatedly in modern systems.

Examples include:

  • Hash tables
  • Treaps
  • Skip lists
  • Load balancing
  • Network routing
  • Distributed consensus

Randomness removes exploitable structure.

Repeated Trials

Some Las Vegas algorithms repeatedly attempt a task until success.

Example:

while True:
    candidate = generate_random_solution()

    if valid(candidate):
        return candidate

Each attempt either succeeds or fails.

Success probability:

p

Expected attempts:

1 / p

The algorithm always returns a valid solution.

Randomness determines how long it takes.

Example: Randomized Selection

Suppose we want:

the kth smallest element

Randomized Quickselect chooses pivots randomly.

Poor pivots produce larger recursive subproblems.

Good pivots quickly eliminate large portions of the search space.

The algorithm always finds the correct element.

Expected runtime:

O(n)

Worst-case runtime:

O(n²)

The expected bound is the quantity that matters in practice.

Randomized Data Structures

Las Vegas ideas extend beyond algorithms.

Treaps

A treap combines:

Binary Search Tree
+
Random Priority

Each inserted node receives a random priority.

The structure maintains:

BST order
Heap order

Random priorities create balanced trees on average.

Operations remain correct.

Expected complexity:

O(log n)

Skip Lists

Skip lists assign random levels to nodes.

Searches, insertions, and deletions follow deterministic rules once levels are assigned.

Expected complexity:

O(log n)

Correctness remains guaranteed.

Randomness influences structure quality rather than output correctness.

Expected Running Time

For Las Vegas algorithms, the most important quantity is:

E[T]

where:

T = runtime random variable

Example:

Suppose:

50% probability -> 10 ms
50% probability -> 30 ms

Expected runtime:

E[T]
=
0.5 × 10
+
0.5 × 30
=
20 ms

Even though no execution lasts exactly 20 ms, the expectation accurately predicts long-term behavior.

Tail Behavior

Expectation alone is often insufficient.

Consider:

Probability Runtime
99.9% 1 ms
0.1% 10000 ms

Expected runtime remains small.

Practical performance may still be unacceptable.

Therefore analyses frequently study:

P(T > threshold)

which measures the probability of unusually long executions.

Modern algorithm analysis often combines:

  • Expected runtime
  • Variance
  • Tail bounds

to obtain a more complete picture.

Correctness Proof Strategy

Las Vegas algorithms require two separate proofs.

Proof 1: Correctness

Show that every returned result is valid.

Random choices do not affect correctness.

Proof 2: Runtime Analysis

Show that:

E[T]

is acceptable.

The two analyses are independent.

This separation greatly simplifies reasoning.

Comparison with Deterministic Algorithms

Property Deterministic Las Vegas
Correctness Guaranteed Guaranteed
Runtime Fixed for input Random
Expected runtime Same as actual Primary metric
Adversarial inputs Often problematic Usually mitigated
Random choices None Required

Las Vegas algorithms preserve correctness while gaining flexibility through randomization.

Common Applications

Las Vegas techniques appear in:

Area Examples
Sorting Randomized quicksort
Selection Quickselect
Data structures Treaps
Search Randomized search trees
Geometry Randomized incremental construction
Databases Randomized indexing
Networking Randomized routing
Distributed systems Leader election

Many systems use these methods because expected performance matters more than absolute worst-case guarantees.

Common Mistakes

Confusing Las Vegas and Monte Carlo

A Las Vegas algorithm:

May take longer.
Never returns a wrong answer.

A Monte Carlo algorithm:

Runs within a predictable bound.
May return a wrong answer.

The distinction is fundamental.

Ignoring Tail Probabilities

Expected runtime alone may hide rare but expensive executions.

Always examine the distribution.

Assuming Random Means Fast

Randomization improves average behavior.

Poor random choices remain possible.

The analysis must account for all possibilities.

Discussion

Las Vegas algorithms demonstrate one of the most useful applications of randomness in computer science. Random choices help avoid adversarial inputs, improve expected performance, simplify implementation, and maintain scalability. Unlike probabilistic algorithms that occasionally produce incorrect answers, Las Vegas algorithms preserve absolute correctness and move uncertainty entirely into resource consumption.

This model explains the success of randomized quicksort, treaps, skip lists, randomized geometric algorithms, and many modern distributed systems. The next section examines the complementary model, Monte Carlo algorithms, where randomness affects correctness itself and small probabilities of error are accepted in exchange for stronger performance guarantees.