Randomized and Probabilistic Algorithms

Introduction and Context

A randomized algorithm uses random choices during execution. Unlike a deterministic algorithm, whose behavior is completely determined by its input, a randomized algorithm may follow different computational paths on different runs of the same input. Randomness can simplify algorithm design, reduce expected running time, avoid adversarial inputs, support approximate computation, and make large-scale sampling feasible.

Randomization is especially important in artificial intelligence and machine learning. Exact computation is often infeasible when datasets contain billions of records, feature spaces are very high-dimensional, or optimization landscapes are non-convex. Random sampling supports stochastic optimization and approximate inference; randomized hashing enables scalable data structures; probabilistic bounds quantify uncertainty; and Markov-chain methods support sampling from distributions that cannot be normalized or sampled from directly.

The central challenge is to distinguish a reliable probabilistic guarantee from an informal claim that an algorithm “usually works.” A rigorous analysis specifies the random variables involved, the source of randomness, the probability of failure, the expected cost, and the assumptions under which the result holds.

Learning Objectives

By the end of this chapter, a learner should be able to:

1. Distinguish Las Vegas, Monte Carlo, and deterministic algorithms.
2. Analyze expected running time and failure probability.
3. Apply random sampling and concentration inequalities.
4. Explain randomized hashing and collision guarantees.
5. Use amplification to improve probabilistic reliability.
6. Describe Markov chains, stationary distributions, mixing, and MCMC.
7. Evaluate randomized algorithms in large-scale AI and data systems.
8. Identify implementation, reproducibility, fairness, and governance risks.

1. Randomness as an Algorithmic Resource

A randomized algorithm is usually modeled as a deterministic algorithm receiving an additional random bit string R. For input x, its output and running time are therefore functions of (x, R). Probability statements are taken over R, while the input may be fixed or may itself be random.

This distinction is fundamental. A statement such as “the algorithm runs in expected linear time” may mean expectation over the algorithm’s random choices for every fixed input. A statement such as “the algorithm succeeds with probability at least 0.99” must identify whether the probability is over internal randomness, data sampling, or both.

Important terminology includes:

• Random variable: a numerical outcome determined by a random experiment.
• Expectation: the probability-weighted average of a random variable.
• Failure probability: the probability that an algorithm violates its required guarantee.
• High probability: commonly an event whose probability is at least 1 − 1/n^c for a constant c > 0, although conventions vary.
• Independence: knowledge of one random event does not change the probability of another.
• Pairwise independence: every pair of variables is independent, even if larger groups are not.

For a discrete random variable X with possible values x and probabilities Pr[X = x], its expectation is

The expectation exists when the sum is well-defined, and it is measured in the same units as X. Linearity of expectation is particularly valuable:

This identity does not require independence. Independence is required for many variance and concentration results, but not for linearity of expectation.

2. Las Vegas and Monte Carlo Algorithms

2.1 Las Vegas algorithms

A Las Vegas algorithm always returns a correct answer, but its running time is random. Randomized quicksort is a standard example: choosing a pivot uniformly at random does not change correctness, but it changes the partition sizes and therefore the running time.

If T is the random running time, analysis focuses on E[T], tail probabilities such as Pr[T > t], and sometimes the worst-case bound. A Las Vegas algorithm is appropriate when an incorrect answer is unacceptable but variable execution time is tolerable.

2.2 Monte Carlo algorithms

A Monte Carlo algorithm has a bounded or controlled running time but may return an incorrect answer or an approximation. Its quality is described by an error probability or approximation guarantee. For a decision problem, a one-sided Monte Carlo algorithm may never produce a false negative but may produce a false positive with probability at most δ. A two-sided algorithm may have either type of error.

The distinction can be summarized as follows:

2.3 Converting between forms

A Monte Carlo algorithm can sometimes be converted into a Las Vegas algorithm by verifying its output and repeating until verification succeeds. This is possible only when correctness is efficiently verifiable and the success probability is sufficiently large. Conversely, a Las Vegas algorithm can be truncated to obtain a Monte Carlo algorithm: stop after a fixed time and report failure. The resulting failure probability must be bounded using a tail inequality.

3. Probability Bounds and Amplification

3.1 Markov’s inequality

For a nonnegative random variable X and a > 0,

The inequality is general but often loose. It requires only nonnegativity and a finite expectation. For example, if E[X] = 10, then Pr[X ≥ 50] ≤ 0.2.

3.2 Chebyshev’s inequality

If X has finite mean μ and variance σ², then for t > 0,

Chebyshev’s inequality does not require a particular distribution or independence among observations beyond what is needed to determine σ². It is stronger than Markov’s inequality when variance is known, but often weaker than exponential concentration bounds.

3.3 Hoeffding’s inequality

Let X₁, …, X_n be independent random variables with a_i ≤ X_i ≤ b_i. Then, for t > 0,

A common special case is independent Bernoulli variables X_i ∈ {0,1}, with sample mean Ȳ = (1/n)∑_i=1ⁿ X_i. If μ is the mean of each variable, then

Here ε is an absolute error tolerance. The bound applies to independent bounded observations; it should not be used automatically for dependent samples such as successive states of a Markov chain.

3.4 Union bound

For events A₁, …, A_k,

The events need not be independent. If each of k components fails with probability at most δ/k, then the probability that at least one component fails is at most δ. This principle is central to designing systems with many randomized subroutines.

3.5 Amplification

Suppose an independent trial succeeds with probability p > 1/2. Repeating it r times and taking the majority answer reduces the error probability rapidly. For a one-sided algorithm that fails with probability at most q per trial, repeating until all trials fail gives error at most q^r.

For example, if q = 0.1 and r = 3, the probability that all three independent trials fail is 0.001. Independence is essential for this multiplication; correlated repetitions may provide little improvement. Using a fresh, adequately independent random seed is therefore part of the algorithmic design.

4. Random Sampling and Approximation

Sampling replaces an expensive computation over a population with a computation over a smaller random subset. If a population has N items and a sample of n items is drawn uniformly without replacement, the sample can estimate aggregate properties without reading every item.

For independent observations X₁, …, X_n with mean μ, the sample mean is

and, when the observations have variance σ²,

The standard error is therefore σ/√n. This relation assumes independent observations with common finite variance. For sampling without replacement from a finite population, variance is reduced by a finite-population correction; treating dependent or clustered samples as independent can substantially understate uncertainty.

4.1 Reservoir sampling

Reservoir sampling selects k items uniformly from a stream whose length is unknown. The basic algorithm is:

1. Place the first k stream items into the reservoir.
2. For the jth item, j > k, draw a uniform integer r from {1, …, j}.
3. If r ≤ k, replace reservoir item r with the new item.

At the end, every item has probability k/N of appearing in the reservoir when the stream length is N. The algorithm uses O(k) memory and O(N) time. Its correctness follows because an item entering at position j is retained with probability k/j, and each earlier reservoir item survives later replacements with the corresponding product of probabilities.

4.2 Importance sampling

Uniform sampling is inefficient when important outcomes are rare. Importance sampling draws from a proposal distribution q(x) and reweights observations to estimate an expectation under target distribution p(x):

The identity requires q(x) > 0 whenever p(x)f(x) ≠ 0. High-variance weights p(x)/q(x) can make the estimator unstable, so proposal design is crucial. In continuous settings, sums become integrals and p and q are densities.

5. Randomized Hashing

Hashing maps keys to table positions. A randomized hash function is selected from a family H so that collisions are unlikely. A family is universal if, for distinct keys x and y,

for a table of m positions. Pairwise independence is often sufficient for expected collision analysis, while stronger independence may be needed for concentration or adversarial settings.

Consider inserting n distinct keys into m buckets using a universal hash family. For a fixed key x, the expected number of other keys colliding with x is at most (n − 1)/m. The expected number of colliding pairs is at most

This is an expectation, not a guarantee that every execution has that many collisions. Chaining handles collisions by storing lists; open addressing searches for alternative positions. Randomization prevents an adversary from reliably constructing a worst-case set of keys when the seed remains secret or is periodically refreshed.

In machine learning systems, hashing is used for feature hashing, approximate frequency counting, distributed partitioning, and sketches. Collisions can introduce biased feature interactions or false frequency estimates, so the number of buckets and the hash-family properties must be validated empirically and theoretically.

6. Randomized Algorithms for Large-Scale Linear Algebra

Randomized numerical methods reduce the cost of matrix computations by constructing a smaller representative subspace. Given a matrix A ∈ ℝ^{m×n}, a random test matrix Ω ∈ ℝ^{n×k} can be used to form

where k is much smaller than min(m,n). An orthonormal basis Q for the columns of Y approximates the dominant column space of A. A rank-k approximation is then formed as

The approximation quality depends on the singular-value decay of A, the oversampling strategy, and numerical conditioning. Power iterations can improve accuracy for slowly decaying spectra, but they increase computational cost and may require reorthogonalization for numerical stability.

Randomized sketches are also used in least-squares regression. A sketching matrix S reduces an overdetermined system from A x ≈ b to SA x ≈ Sb. A useful sketch approximately preserves the geometry of the relevant column space. The resulting solution can be computed more cheaply, although approximation error, conditioning, and the cost of forming the sketch must all be considered.

7. Markov Chains and Markov-Chain Monte Carlo

A Markov chain is a stochastic process X₀, X₁, … in which the distribution of the next state depends on the current state but not on the full history:

For a finite state space, transition probabilities form a matrix P, where P_{xy} = Pr[X_{t+1}=y | X_t=x]. Each row sums to 1 and all entries are nonnegative.

A distribution π is stationary if

A sufficient condition for π to be stationary is detailed balance:

for all states x and y. A finite chain has a unique limiting distribution under conditions commonly described as irreducibility and aperiodicity. Irreducibility means every state can eventually reach every other state; aperiodicity prevents deterministic cycling. These conditions concern the chain’s structure, not merely the number of iterations.

7.1 Metropolis–Hastings sampling

Suppose the target distribution is known up to a constant: π(x) ∝ tildeπ(x). From current state x, propose y from q(y|x), then accept y with probability

If the proposal is symmetric, q(y|x) = q(x|y), this simplifies to min(1, tildeπ(y)/tildeπ(x)). If the proposal is rejected, the chain remains at x. The acceptance rule establishes detailed balance with the target distribution under standard positivity and irreducibility conditions.

7.2 Gibbs sampling

Gibbs sampling updates one component at a time from its conditional distribution. For variables X = (X₁, …, X_d), an iteration may sample

where X_{−i} denotes all variables other than X_i. Gibbs sampling is useful when conditional distributions are easy to sample even though the joint distribution is difficult.

7.3 Burn-in, autocorrelation, and effective sample size

Early states may depend strongly on the initial state and are often discarded as burn-in. However, burn-in is not a universal fixed number; it depends on the chain’s mixing behavior. Successive MCMC samples are correlated, so n iterations do not generally provide n independent observations.

For a scalar quantity f(X), the effective sample size is often approximated by

where ρ_k is the lag-k autocorrelation and the sum is estimated in practice using a stable truncation rule. This formula assumes a stationary chain and suitable regularity conditions. A high nominal sample count can therefore conceal a small effective sample size.

8. Worked Example: Estimating a Rare Event

Suppose a Monte Carlo simulation estimates an event with probability p = 0.02. In n = 10,000 independent trials, the estimator is the sample proportion p̂ = X/n, where X is the number of observed events. Since X is binomial,

and

The standard deviation is √0.00000196 ≈ 0.0014, or about 0.14 percentage points. Thus the simulation’s random error is small relative to the 2% estimate, although this calculation does not account for model error, dependence, or biased event detection.

Using Hoeffding’s inequality for an absolute error ε = 0.01 gives

This bound is valid but conservative. It demonstrates that a formal guarantee may be much weaker than a variance-based practical assessment. For rare-event simulation, importance sampling or splitting methods may be preferable because ordinary sampling observes too few rare events.

9. Illustrative Case Study: Randomized Fraud Screening

Background

A financial platform processes millions of transactions per hour. Exact comparison with every historical transaction and exact computation of all graph relationships is too expensive for real-time screening.

Problem

The platform must identify suspicious transactions while controlling false positives, maintaining auditability, and avoiding a system that an attacker can manipulate by submitting specially constructed identifiers.

Analysis

The engineering team uses three randomized components. First, a reservoir sample maintains a recent, representative stream sample for exploratory monitoring. Second, universal hashing maps high-dimensional categorical features into a fixed-size feature vector. Third, a Monte Carlo graph procedure estimates connectivity to known risk clusters. Each component introduces uncertainty or possible collisions, so the system records seeds, sample sizes, confidence diagnostics, and versioned hash functions.

Approach and solution

The screening score is not treated as proof of fraud. Transactions above a conservative threshold are sent for secondary review. Independent repetitions of the graph estimator are aggregated to reduce error. A union-bound budget allocates a maximum failure probability across separate alerts and monitoring tasks. Sensitive decisions use calibrated validation data and subgroup performance tests rather than relying only on theoretical randomization guarantees.

Hash seeds are generated from a secure source and rotated under a documented policy. Reproducibility is preserved by storing the seed or a secure seed identifier for every model version, with access controls to prevent adversarial exploitation. Human reviewers can inspect the principal features and the uncertainty associated with an alert.

Outcome

The randomized pipeline reduces memory and latency while retaining a reviewable decision process. Its performance is assessed using precision, recall, false-positive rate, calibration, latency, and stability across seeds and demographic or geographic subgroups. The organization does not claim that randomization itself guarantees fairness or accuracy.

Learning points

1. Randomized efficiency must be paired with measurable error controls.
2. Theoretical collision or sampling bounds do not replace validation on operational data.
3. Reproducibility requires controlled randomness, versioning, and audit logs.
4. Human and governance processes remain necessary when algorithmic outputs affect individuals.

10. Implementation and Best Practices

• State whether the guarantee is worst-case, expected, or high probability.
• Separate algorithmic randomness from randomness in the data-generating process.
• Use cryptographically secure randomness when unpredictability matters; ordinary pseudorandom generators are generally sufficient for simulation but not for security.
• Record seeds, generator versions, parameter settings, and stopping rules.
• Do not assume that repeated runs are independent when they share data, hardware state, or seeds.
• Test both average performance and tail behavior.
• Use confidence intervals or concentration bounds appropriate to the sampling design.
• Check the assumptions of independence, boundedness, stationarity, and irreducibility before applying a theorem.
• In distributed systems, manage correlated randomness and communication overhead explicitly.
• For MCMC, report diagnostics such as trace behavior, autocorrelation, effective sample size, and sensitivity to initialization.

11. Limitations, Ethics, and Governance

Randomization does not eliminate bias. A random sample can be unrepresentative by chance, and a systematically biased data-collection process remains biased after randomization. Approximation error may be acceptable for aggregate analytics but unacceptable for safety-critical or individual-level decisions.

Probabilistic guarantees can also be misunderstood. A 99% success probability does not mean that every user receives a 99% correct result, nor does it identify which executions fail. Multiple decisions can accumulate risk, making a union-bound or system-level analysis necessary.

In privacy-sensitive applications, randomization may support differential privacy, but ordinary algorithmic randomness is not itself differential privacy. Privacy guarantees require a formal mechanism and a quantified privacy budget. In regulated settings, organizations should document data provenance, random seeds where appropriate, model versions, validation evidence, uncertainty, human oversight, and appeal procedures.

Contemporary Developments

Current research combines randomized algorithms with distributed learning, streaming analytics, privacy-preserving computation, randomized numerical linear algebra, and probabilistic programming. Variance-reduced stochastic optimization, sketching for large language-model infrastructure, subsampling for Bayesian inference, and adaptive MCMC are active areas. A major research concern is robustness: adaptive adversaries may observe outputs and exploit weaknesses in sampling, hashing, or evaluation. Consequently, modern systems increasingly combine formal probability bounds with empirical stress testing, secure randomness, and reproducible experiment management.

Chapter Summary

Randomized algorithms use controlled randomness to improve efficiency, scalability, robustness, or approximation quality. Las Vegas algorithms preserve correctness while randomizing running time; Monte Carlo algorithms control running time while accepting bounded error. Expectation, variance, Markov’s inequality, Chebyshev’s inequality, Hoeffding’s inequality, and the union bound provide the language for analyzing cost and reliability.

Random sampling supports streaming and large-scale estimation, with reservoir sampling providing uniform samples using limited memory. Universal hashing reduces expected collisions and supports compact sketches and feature representations. Randomized linear algebra approximates matrix structure through low-dimensional projections. Markov chains provide a foundation for MCMC, where stationarity, irreducibility, aperiodicity, mixing, autocorrelation, and effective sample size determine practical reliability. Sound deployment requires explicit assumptions, independent or controlled randomness, reproducibility, uncertainty reporting, security, fairness evaluation, and governance.

Key Terms

Randomized algorithm: An algorithm whose execution depends on random choices.

Las Vegas algorithm: A randomized algorithm that always returns a correct result but has random running time.

Monte Carlo algorithm: A randomized algorithm with bounded or controlled cost that may produce an error or approximation.

Expected running time: The probability-weighted average execution time.

Failure probability: The probability that a required guarantee is violated.

Markov’s inequality: A bound on the probability that a nonnegative variable exceeds a threshold.

Chebyshev’s inequality: A variance-based bound on deviation from the mean.

Hoeffding’s inequality: An exponential concentration bound for independent bounded variables.

Union bound: An upper bound on the probability of at least one event occurring.

Amplification: Repetition used to reduce error probability.

Reservoir sampling: A streaming method for maintaining a uniform sample of fixed size.

Importance sampling: Estimation using samples from a proposal distribution with corrective weights.

Universal hashing: A hash-family property that limits collision probability for distinct keys.

Pairwise independence: Independence guaranteed for every pair of random variables.

Markov chain: A stochastic process whose next state depends only on its current state.

Stationary distribution: A distribution unchanged by application of the transition matrix.

Detailed balance: A sufficient condition ensuring stationarity through balanced probability flow.

Metropolis–Hastings: An MCMC method using proposals and acceptance probabilities.

Burn-in: Initial MCMC iterations discarded because the chain may not represent its limiting distribution.

Effective sample size: The approximate number of independent observations represented by correlated MCMC samples.

Review Questions

Short Answer Questions

1. What is the main distinction between a Las Vegas and a Monte Carlo algorithm?
2. Why does linearity of expectation not require independence?
3. State the union bound and explain one use in algorithm design.
4. What problem does reservoir sampling solve?
5. Define a stationary distribution of a Markov chain.

Long Answer Questions

1. Explain how Markov’s, Chebyshev’s, and Hoeffding’s inequalities differ in assumptions and typical strength.
2. Describe universal hashing, collision analysis, and the role of independence assumptions.
3. Explain Metropolis–Hastings sampling and derive the acceptance probability conceptually from detailed balance.
4. Discuss burn-in, autocorrelation, and effective sample size in MCMC.
5. Compare random sampling, importance sampling, and randomized matrix sketching as large-scale computation techniques.

Analytical / Application Questions

1. A randomized decision procedure succeeds with probability 0.9 on each independent run. How many repetitions are needed to make the probability that all runs fail at most 0.001? State the assumption used.
2. A hash table has m buckets and receives n distinct keys under a universal hash family. Derive an upper bound on the expected number of colliding key pairs and discuss how changing m affects it.
3. Design an evaluation plan for a randomized fraud-screening system that measures accuracy, uncertainty, reproducibility, latency, subgroup performance, and adversarial robustness.

Multiple Choice Questions with Answers

Question 1

Which property characterizes a Las Vegas algorithm?

A. It always returns a correct result, but its running time may be random.

B. It always runs in constant time but may return an incorrect result.

C. It uses no random bits during execution.

D. It guarantees zero memory consumption.

Correct Answer: A. It always returns a correct result, but its running time may be random.

Question 2

For a nonnegative random variable X, which statement is Markov’s inequality?

A. Pr[X ≥ a] ≤ E[X]/a for a > 0

B. Pr[X ≥ a] ≤ Var(X)/a² for every X

C. Pr[X = a] = E[X]/a

D. E[X] ≤ Pr[X ≥ a]/a

Correct Answer: A. Pr[X ≥ a] ≤ E[X]/a for a > 0

Question 3

What is the principal guarantee of reservoir sampling with reservoir size k?

A. The first k items are always retained.

B. Every item in a stream of length N has probability k/N of being retained.

C. Only the most frequent k items are retained.

D. The method requires storing the entire stream.

Correct Answer: B. Every item in a stream of length N has probability k/N of being retained.

Question 4

Under a universal hash family with m buckets, what is the maximum stated collision probability for two distinct fixed keys?

A. m

B. 1 − 1/m

C. 1/m

D. 1/n² regardless of m

Correct Answer: C. 1/m

Question 5

Which condition is required by the common Hoeffding bound for the sample mean?

A. The observations must be independent and bounded.

B. The observations must all be normally distributed.

C. The observations must have zero variance.

D. The sample size must equal the population size.

Correct Answer: A. The observations must be independent and bounded.

Question 6

If an independent Monte Carlo trial fails with probability 0.1, what is the probability that three repetitions all fail?

A. 0.03

B. 0.01

C. 0.001

D. 0.9

Correct Answer: C. 0.001

Question 7

A distribution π is stationary for transition matrix P when:

A. Pπ = 0

B. πP = π

C. π = 1/P

D. Every entry of P is equal

Correct Answer: B. πP = π

Question 8

In Metropolis–Hastings, what happens when a proposed state is rejected?

A. The chain terminates.

B. The current state is retained for the next iteration.

C. The proposal is automatically accepted later.

D. The stationary distribution is changed.

Correct Answer: B. The current state is retained for the next iteration.

Question 9

Why can the nominal number of MCMC iterations overstate the amount of information obtained?

A. MCMC samples are often autocorrelated.

B. MCMC always discards half the data.

C. Stationary distributions contain no information.

D. Transition matrices cannot be evaluated.

Correct Answer: A. MCMC samples are often autocorrelated.

Question 10

For universal hashing, the stated upper bound on the expected number of colliding pairs among n keys and m buckets is:

A. n + m

B. n(n − 1)/(2m)

C. m/[n(n − 1)]

D. n²m

Correct Answer: B. n(n − 1)/(2m)