Lesson 28 · Core algorithms

Randomized Algorithms

Randomized algorithms use sampled choices to improve expected performance or allow a small, quantified probability of error.

Why introduce randomness

Random choices can prevent inputs from consistently triggering a bad deterministic pattern, simplify symmetry breaking, or sample a huge space. The analysis treats the random bits as part of the algorithm, even for a fixed input.

Randomized quicksort chooses a random pivot and has O(nlog n) expected time but O(n²) worst case. Randomization changes the probability of bad execution; it does not make that execution impossible.

Analyze over random choices
Random pivots resist fixed adversarial order
Worst cases may remain

Las Vegas versus Monte Carlo

A Las Vegas algorithm always returns a correct result but has random running time; randomized quicksort is the standard example. A Monte Carlo algorithm has bounded running time but may return a wrong answer with known probability, such as probabilistic primality testing.

Never describe expected correctness ambiguously. State which resource is random, the error direction, and the probability bound.

Las Vegas randomizes time
Monte Carlo permits bounded error
Name the guarantee precisely

Key reference

Terms, operations, and practical uses

Guarantees

Las VegasLas Vegas is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Monte CarloMonte Carlo is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Expected running timeExpected running time is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.

Probability

Error boundError bound is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
AmplificationAmplification is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Independent trialIndependent trial is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.

Sampling

Fisher–YatesFisher–Yates is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Reservoir samplingReservoir sampling is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Reproducible seedReproducible seed is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.

Implementation

Fisher–Yates makes a uniform shuffle

a=[1,2,3,4];choices=[1,0,1]
for i,j in zip(range(len(a)-1,0,-1),choices):a[i],a[j]=a[j],a[i]
print("Shuffled:",", ".join(map(str,a)))

#include <algorithm>
#include <array>
#include <cstring>
#include <functional>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
int main() {
    vector<int>a={1,2,3,4},choice={1,0,1};
    for(int i=3,k=0;i>0;i--,k++) swap(a[i],a[choice[k]]);
    cout << "Shuffled:";
    for(int x:a) cout << ' ' << x;
    cout << '\n';
}

class Main {
    public static void main(String[] args) {
        int[] a={1,2,3,4},choice={1,0,1};
        for(int i=3,k=0;i>0;i--,k++) {
            int t=a[i];
            a[i]=a[choice[k]];
            a[choice[k]]=t;
        }
        System.out.println("Shuffled: "+a[0]+", "+a[1]+", "+a[2]+", "+a[3]);
    }
}

Watch it run

Step through it

Running on [1,2,3,4] with fixed choices 1,0,1

Output

Amplification

Repeat independent Monte Carlo trials and combine results to reduce error exponentially. If one trial fails with probability p, k independent all-fail events have probability p^k. Independence or an appropriate weaker property is part of the proof.

One-sided tests can often OR or AND trials without rejecting a true case incorrectly. Two-sided estimators may use majority vote plus concentration bounds.

Independent repetition shrinks error
Combination depends on error type
Correlated seeds break naive amplification

Sampling and shuffling correctly

Uniformly sample integer ranges without modulo bias when the generator range is not divisible by the target range. Fisher–Yates produces a uniform permutation by choosing among the remaining positions at each step.

Sorting by random keys can collide and is not a reliable uniform shuffle. Reservoir sampling selects k items from a stream of unknown length with fixed memory and a proof based on equal inclusion probability.

Avoid modulo bias
Fisher–Yates is uniform
Reservoir sampling handles streams

Reproducibility and adversaries

Accept an injected seed or random generator so failures can be replayed. Use deterministic seeds in tests and varied seeds in stress runs. Pseudorandom generators are not automatically cryptographically secure.

For untrusted adversarial inputs, exposing a seed or using predictable hashes can restore worst-case attacks. Test distribution on small spaces, but do not mistake empirical frequencies for a proof of uniformity.

Record seeds for replay
Security needs a secure generator
Statistical tests complement proofs

Analyzing probability honestly

Specify the random experiment and indicator variables, then use linearity of expectation, tail bounds, or direct counting. Expected O(nlog n) does not mean every run stays near that value, and a small error probability must be attached to a defined input and number of trials.

Production systems also need entropy failure handling and deterministic fallbacks where denial-of-service risk matters. Record algorithm version and seed alongside a failing test. Property tests should run many seeds but shrink a failure while preserving the seed so debugging remains reproducible.

Random choices should never conceal a missing deterministic invariant. Verify every Las Vegas result before returning, and make Monte Carlo error reducible through repetition. If a caller needs zero error, offer a deterministic verification or fallback path instead of merely choosing a larger seed.

Fisher–Yates is uniform by induction: after choosing j uniformly from 0 through i, every remaining element has probability 1/(i+1) of occupying position i; the recursive shuffle is uniform over the positions before it. Using a range that excludes i forbids self-swaps and biases the result. In randomized quicksort, expected bounds assume pivot choices are independent of the input arrangement; a predictable generator exposed to an adversary may lose that protection. Tests should inject a deterministic sequence of choices to cover boundary indexes zero and i, while statistical checks over many seeds can detect gross bias without replacing the mathematical proof.

Define the probability space
Expected bounds are distributional
Persist seeds with failures