Probability and Randomized Algorithms

Expected value, linearity of expectation, randomized quicksort, randomized selection, reservoir sampling, randomized hashing, Monte Carlo versus Las Vegas algorithms, error probability, and reproducibility through seeds.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

Linearity of expectation: randomized quicksort compares elements i and j (in sorted order) exactly when one of them is the first pivot chosen among the j − i + 1 values between them, with probability 2/(j − i + 1). Summing over pairs gives 2(n+1)H_n − 4n ≈ 1.39 n log₂ n — the run matches it on *sorted* input, which is the worst case for a fixed pivot.

Monte Carlo algorithms have bounded time and a small probability of a wrong or approximate answer (Miller–Rabin, π estimation); Las Vegas algorithms are always correct with a random running time (randomized quicksort).

Fix the seed during testing so failures reproduce; use a fresh seed in production where adversaries matter (randomized hashing, Module 44).

#include <bits/stdc++.h>
using namespace std;

int main() {
    mt19937_64 rng(2024);                                         // fixed seed: the run is reproducible
    // reservoir sampling: one uniform item from a stream of unknown length, O(1) memory
    vector<int> hits(10, 0);
    for (int trial = 0; trial < 100000; ++trial) {
        int chosen = -1;
        for (int i = 0; i < 10; ++i) if (rng() % (i + 1) == 0) chosen = i;      // keep item i with probability 1/(i+1)
        ++hits[chosen];
    }
    cout << "reservoir sampling, 100000 trials over a stream of 10:";
    for (int h : hits) cout << ' ' << h;
    cout << "  (each about 10000)\n";

    // expected comparisons of randomized quicksort: 2(n+1)H_n - 4n
    long long comparisons = 0; int n = 1000, runs = 200;
    function<void(vector<int>&, int, int)> qs = [&](vector<int>& a, int l, int r) {
        if (l >= r) return;
        swap(a[l + rng() % (r - l + 1)], a[r]);
        int pivot = a[r], i = l;
        for (int j = l; j < r; ++j) { ++comparisons; if (a[j] < pivot) swap(a[i++], a[j]); }
        swap(a[i], a[r]);
        qs(a, l, i - 1); qs(a, i + 1, r);
    };
    for (int t = 0; t < runs; ++t) { vector<int> a(n); 
…

reservoir sampling, 100000 trials over a stream of 10: 9910 10041 9910 10135 9904 10108 9986 9974 9975 10057  (each about 10000)
randomized quicksort on sorted input, n = 1000: average 10975.1 comparisons, theory 10985.9
Monte Carlo estimate of pi with 1e6 samples: 3.1421
Las Vegas search found 777 after 279 random probes (expected 1000)

Quiz

? Why does reservoir sampling keep item i with probability 1/(i+1)?
+ It keeps every item seen so far equally likely to be the current choice, without knowing the stream's length. :: The run shows roughly equal counts.
- To favour recent items :: All items end up equally likely.
- To save time :: It uses O(1) memory.
- It is arbitrary :: Other probabilities bias the result.

? Randomized quicksort averaged close to the theoretical 2(n+1)H_n − 4n comparisons on sorted input. Why does sortedness not hurt?
+ The pivot is random, so no fixed input is bad; the expectation is over the random choices. :: A fixed pivot would take ~n²/2.
- Sorted input is the best case :: Only for adaptive algorithms.
- The compiler optimised it :: No.
- Quicksort detects sorted input :: It does not.

? Which is a Las Vegas algorithm?
+ Randomized quicksort — always sorts correctly, running time varies :: Correctness is guaranteed.
- Miller–Rabin with random bases :: Monte Carlo (one-sided error).
- Estimating π by sampling :: Monte Carlo.
- A Bloom filter query :: Probabilistic answer.