Randomized and Probabilistic Algorithms

Introduction

Many algorithmic problems are difficult not because the input is large, but because deterministic choices repeatedly lead to poor performance. Randomization provides an additional source of information: a random sample, a random pivot, a random hash function, or a random ordering. A randomized algorithm uses such choices during execution. Its behaviour is therefore described not only as a function of the input, but also as a probability distribution over possible executions.

Randomized algorithms are central to modern artificial intelligence and machine learning systems. They support sampling, approximate inference, randomized optimization, privacy-preserving computation, distributed coordination, hashing, graph algorithms, cryptography, and scalable data processing. Their analysis requires careful separation of three ideas: the input, the algorithm’s internal randomness, and the event whose probability is being measured.

A randomized algorithm may be faster, simpler, or more robust than a deterministic alternative. However, randomness does not automatically guarantee correctness. The designer must specify whether an error is possible, whether the running time is random, and how failure probability is bounded.

Learning Objectives

After completing this chapter, a student should be able to:

1. distinguish Las Vegas, Monte Carlo, and probabilistic algorithms;
2. analyse expected running time and error probability;
3. apply indicator variables, linearity of expectation, conditional expectation, and concentration bounds;
4. explain and analyse randomized quicksort, randomized selection, hashing, reservoir sampling, and randomized graph algorithms;
5. understand amplification, pairwise independence, universal hashing, and random walks;
6. evaluate the practical, ethical, and security implications of randomized computation;
7. select an appropriate randomized strategy for an AI/ML or large-scale computing problem.

1. Foundations of Randomized Computation

A deterministic algorithm maps each input x to one output and one execution path. A randomized algorithm can be represented as A(x, r), where x is the input and r is a random string generated internally. For a fixed input, different values of r may produce different paths, outputs, or running times.

The probability space must be stated explicitly. Usually, the input is fixed and the probability is taken over the algorithm’s random choices. This is called the probability of the algorithmic randomness. By contrast, average-case analysis places a probability distribution on inputs. Confusing these two models can produce incorrect conclusions.

1.1 Las Vegas and Monte Carlo algorithms

A Las Vegas algorithm always returns a correct answer, but its running time is random. Randomized quicksort is a typical example: every pivot choice produces a correct sorted sequence, although the number of comparisons varies.

A Monte Carlo algorithm has a bounded or predictable running time, but it may return an incorrect answer with small probability. The Miller–Rabin primality test is a standard example. A randomized approximation algorithm may also produce an estimate whose error is probabilistically bounded.

“High probability” is not a universal numerical guarantee. In theoretical computer science it often means probability at least 1 − 1/n^c for a constant c > 0, where n is an input-size parameter. In an engineering system, the required probability must be stated explicitly.

1.2 Expected running time

If T is the random variable representing running time, the expected running time is

The summation applies to discrete running times; an integral is used for a continuous random variable. The expectation is an average over random executions for a fixed input. It does not mean that every execution takes E[T] time.

A useful distinction is between expected polynomial time and strict worst-case polynomial time. An algorithm may have a polynomial expected running time while possessing rare, very long executions. Such an algorithm may be acceptable when long tails are harmless, but unsuitable for real-time systems.

2. Probabilistic Tools for Algorithm Analysis

2.1 Indicator random variables

For an event E, define the indicator variable I_E by

Its expectation is

This simple identity allows a complex count to be expressed as a sum of elementary events. If X is the number of successful events among m trials, and I_i indicates success in trial i, then X = ∑_{i=1}^m I_i. Consequently,

This is the linearity of expectation. It holds even when the events are dependent.

2.2 Conditional expectation

For events or random variables conditioned on information Y, the law of total expectation is

for discrete Y. Conditional analysis is especially useful when the first random choice divides the problem into subproblems.

2.3 Markov’s inequality

For a non-negative random variable X and any a > 0,

Markov’s inequality requires only non-negativity and is therefore broadly applicable, but it is often loose.

2.4 Chebyshev’s inequality

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

Chebyshev’s inequality is useful when variance is known but the distribution is not.

2.5 Chernoff bounds

For independent Bernoulli trials, Chernoff bounds give exponentially decreasing tail probabilities. If X is the sum of independent indicator variables and μ = E[X], then for 0 < δ < 1,

and

These bounds assume independence and are valuable for analysing randomized load balancing, sampling, hashing, and machine-learning estimators.

2.6 Amplification

Suppose a Monte Carlo algorithm is correct with probability at least 1/2 + ε, where ε > 0. Repeating independent trials and taking majority vote increases confidence. If each trial independently fails with probability p < 1/2, then the probability that a majority of k trials fail decreases exponentially in k; a Chernoff bound can quantify the decrease.

For one-sided algorithms whose failure probability is at most p, repeating independently k times and accepting only if all trials accept gives failure probability at most p^k. Repetition must be independent or sufficiently weakly dependent; simply rerunning with the same random seed provides no amplification.

3. Randomized Quicksort

Quicksort selects a pivot, partitions the array, and recursively sorts the two resulting parts. Its worst-case running time is Θ(n²), which occurs when partitions are extremely unbalanced at every level. Randomized quicksort chooses the pivot uniformly from the current subarray.

The algorithm remains correct for every sequence of pivot choices. Its running time is therefore a Las Vegas random variable.

3.1 Comparison-based analysis

Assume all keys are distinct and the pivot is chosen uniformly. Let C_n be the number of comparisons on n elements. If the pivot has rank k, the two subproblems contain k − 1 and n − k elements. Thus,

The term n − 1 accounts for partition comparisons. By symmetry,

Solving this recurrence gives

where H_n = 1 + 1/2 + ··· + 1/n is the nth harmonic number. Since H_n = Θ(log n), the expected number of comparisons is Θ(n log n).

A second proof uses pairwise indicators. Consider two keys of ranks i and j, with i < j. They are compared if and only if the first pivot selected from the set of keys with ranks i through j is one of the two endpoints. Therefore,

Summing these probabilities over all pairs gives the expected comparison count. This method illustrates the power of indicators: independence among comparison events is unnecessary.

3.2 Practical considerations

Randomized quicksort should use a high-quality pseudorandom generator, avoid predictable seeds in adversarial settings, and handle duplicate keys with three-way partitioning. A recursion-depth safeguard or hybrid switch to heapsort can protect against implementation defects or hostile randomness. Randomization improves expected behaviour but does not eliminate the Θ(n²) worst-case possibility for a particular random sequence.

4. Randomized Selection

The selection problem asks for the kth smallest element. Randomized quickselect partitions around a uniformly chosen pivot and recursively processes only the side containing the kth element.

Its expected running time is Θ(n), while its worst-case time is Θ(n²). The expected recurrence is less costly than quicksort because only one subproblem is processed. If the pivot is reasonably balanced, the active problem shrinks rapidly. A deterministic linear-time selection algorithm based on medians of groups provides worst-case Θ(n), but is more complex and often slower in practice. Randomized selection is therefore an important example of the trade-off between elegant expected performance and strict worst-case guarantees.

5. Hashing and Universal Families

Hash tables ideally provide expected O(1) insertion, deletion, and search. The challenge is collisions: different keys may map to the same slot.

A family H of hash functions from universe U to table positions {0, …, m − 1} is universal if, for any distinct keys x and y,

The probability is over a uniformly selected h from H. Under suitable assumptions, universal hashing limits expected collisions even when the input keys are chosen adversarially before the random function is selected.

If n keys are stored in m slots, the load factor is α = n/m. With chaining and universal hashing, the expected chain length for a searched key is O(1 + α). For a successful search, the expected number of examined entries is proportional to 1 + α; keeping α bounded gives expected constant-time operations.

Randomization is also used in cryptographic hash constructions, randomized dictionaries, skip lists, and Bloom filters. A Bloom filter has no false negatives for correctly inserted items, but may have false positives. If m bits, k independent hash functions, and n inserted items are used, the approximate false-positive probability is

This approximation assumes sufficiently independent, uniform hash outputs and is most reliable when m, n, and k are in an operating range where the standard occupancy approximation applies. The approximate optimal number of hash functions is k ≈ (m/n) ln 2.

6. Sampling Algorithms

6.1 Reservoir sampling

Suppose a stream contains an unknown number N of records, but memory can store only one record. Reservoir sampling selects one item uniformly without storing the entire stream:

1. store the first item;
2. when item i arrives, where i ≥ 2, replace the stored item with probability 1/i;
3. otherwise retain the current item.

At the end, every item has probability 1/N of being stored. To see this, item i is selected when it arrives with probability 1/i and survives every later replacement with probability ∏_{j=i+1}^N (1 − 1/j) = i/N. Their product is 1/N.

For a reservoir of size k, item i is selected with probability k/i when i > k, and survives later steps with the appropriate product, resulting in probability k/N for every item. Reservoir sampling is valuable in data streams, telemetry, online learning, and unbiased dataset inspection.

6.2 Monte Carlo estimation

If X_1, …, X_n are independent samples of a random variable X with mean μ and variance σ², the sample mean is

and E[X̄] = μ, Var(X̄) = σ²/n. Thus standard deviation decreases as 1/√n, not as 1/n. To reduce sampling error by a factor of 2, approximately four times as many independent samples are needed.

When samples are bounded, concentration inequalities can provide confidence guarantees. If X_i ∈ [0,1], Hoeffding’s inequality states

for ε > 0. To ensure failure probability at most δ, it is sufficient that

This is a sufficient bound, not necessarily the smallest possible sample size.

7. Randomized Graph Algorithms

Karger’s contraction algorithm estimates a minimum cut. It repeatedly selects a uniformly random edge and contracts its endpoints, while removing self-loops, until two supernodes remain. The edges between the two supernodes define a cut.

If the graph has n vertices and minimum cut value λ, then while the algorithm has i vertices, the number of edges is at least iλ/2. Hence the probability of contracting a minimum-cut edge at that stage is at most 2/i. The probability of avoiding all minimum-cut edges from n vertices down to 2 is at least

Thus one run succeeds with probability Ω(1/n²). Repeating independently Θ(n² log n) times raises the probability of missing the minimum cut to a small inverse-polynomial quantity. More sophisticated contraction algorithms improve this success probability and running time.

This example demonstrates a common pattern: a single randomized trial may be weak, but amplification converts a non-negligible success probability into high confidence.

8. Random Walks and Markov-Chain Methods

A random walk is a stochastic process whose next state depends probabilistically on the current state. A Markov chain consists of states and transition probabilities P_ij satisfying P_ij ≥ 0 and ∑_j P_ij = 1.

A stationary distribution π satisfies

where π is treated as a row vector. If a chain is irreducible and aperiodic, it has a unique stationary distribution, and the distribution of the state after sufficiently many transitions approaches π. The number of transitions needed for adequate approximation is related to the mixing time.

Markov-chain Monte Carlo (MCMC) generates samples from a difficult distribution by constructing a chain whose stationary distribution is the target. In machine learning, MCMC can be used for Bayesian posterior inference. Its practical analysis requires attention to burn-in, autocorrelation, effective sample size, convergence diagnostics, and sensitivity to initialization. Treating correlated MCMC samples as independent can severely understate uncertainty.

9. Probabilistic Algorithms in AI and Machine Learning

Randomness appears in several parts of AI/ML systems:

• stochastic gradient descent samples training examples or minibatches;
• randomized initialization can avoid identical neural-network units and explore different solutions;
• dropout randomly removes activations during training;
• random forests use bootstrap samples and random feature subsets;
• randomized sketching reduces the dimensionality of large matrices;
• approximate nearest-neighbour methods use random projections or randomized trees;
• Bayesian methods use Monte Carlo or variational approximations;
• differential privacy adds calibrated randomness to outputs or computations.

Randomization can improve generalization, but it does not itself prove that a model is unbiased or fair. Reproducibility requires recording seeds, software versions, data partitions, and random-number-generator algorithms. In distributed training, independent-looking workers may accidentally use correlated streams, invalidating theoretical assumptions.

10. Cryptography, Adversaries, and Randomness Quality

In non-adversarial analysis, a pseudorandom generator may be adequate if its outputs approximate the required distribution. In cryptography, unpredictability is essential. A predictable nonce, key, salt, or seed can compromise confidentiality or authentication even if the algorithm is mathematically correct.

The adversary model must therefore be stated. An oblivious adversary chooses the input before seeing random choices. An adaptive adversary may observe outputs and react. Security proofs often require stronger randomness, random oracles, computational assumptions, or fresh independent seeds. Using a general-purpose simulation generator for cryptographic secrets is unsafe.

11. Worked Example: Confidence in Randomized Estimation

A data team estimates the fraction μ of records satisfying a quality rule by independently sampling records. The estimator is X̄, where each observation is 1 if the rule is satisfied and 0 otherwise. The team wants absolute error at most ε = 0.02 with failure probability at most δ = 0.05.

Using Hoeffding’s sufficient bound,

Substitution gives

Therefore, n = 4612 independent observations are sufficient under the stated assumptions. This is a conservative guarantee. The calculation does not justify sampling 4612 records from a biased or duplicated source; independence and representative sampling remain methodological requirements.

12. Applied Case: Randomized Anomaly Inspection in a Data Pipeline

Background

An online service receives millions of events daily. Full manual inspection is impossible, but data engineers need to detect schema violations and unusual values quickly.

Problem

A deterministic policy that always inspects the newest events misses delayed or low-frequency failures. A full scan is too expensive. The organization requires an unbiased daily sample and a quantified estimate of violation prevalence.

Analysis

The system maintains a reservoir of 10,000 events using reservoir sampling. Every event has equal probability of entering the final reservoir, provided the stream-processing assumptions are met. Each sampled event is classified as valid or invalid. The sample proportion estimates the population proportion.

If the target error is ε and the desired confidence is 1 − δ, the team selects the sample size using a concentration bound. Stratified reservoirs are added for regions and event types because a single global reservoir could underrepresent rare but important categories. Independent pseudorandom streams are assigned to workers, and seeds are recorded for auditability.

Approach and solution

The pipeline uses:

1. reservoir sampling for bounded-memory selection;
2. stratification to protect minority categories;
3. Hoeffding or exact binomial intervals for reported uncertainty;
4. repeated runs with independent seeds to detect instability;
5. a manual review queue for high-risk categories;
6. access controls so sampled records do not expose unnecessary personal data.

Outcome

The organization obtains an unbiased overall estimate, category-level monitoring, and a reproducible audit trail. Random sampling reduces cost, while stratification and risk-based review prevent the statistical average from hiding rare catastrophic failures.

Learning points

Randomization must be matched to the operational objective. Uniform sampling supports population estimation, but safety-critical monitoring may require deliberate oversampling of rare events. Statistical validity and governance controls are complementary, not interchangeable.

13. Limitations and Design Risks

Randomized algorithms have several limitations:

• expected performance may conceal unacceptable tail latency;
• probability guarantees depend on correct assumptions about independence or distribution;
• weak or reused seeds can make outcomes predictable;
• pseudorandom generators introduce implementation dependencies;
• repeated experimentation can produce apparently strong results by chance;
• random sampling may underrepresent rare but consequential cases;
• randomized model training can make debugging and reproducibility difficult;
• adversarial inputs may exploit predictable or poorly analysed choices.

A complete analysis should report the probability space, success criterion, expectation or tail bound, random-source assumptions, and failure-handling policy. For production systems, empirical monitoring should accompany theoretical analysis.

14. Best Practices

1. State whether the algorithm is Las Vegas or Monte Carlo.
2. Specify whether probability is over inputs, internal randomness, or both.
3. Use independent random choices when the proof requires independence.
4. Prefer explicit tail bounds when latency or safety matters.
5. Amplify confidence only with fresh, adequately independent trials.
6. Record seeds and generator versions for reproducibility, but protect secrets.
7. Use cryptographically secure randomness for security-sensitive operations.
8. Test extreme inputs, duplicate values, adversarial patterns, and rare events.
9. Monitor empirical distributions against theoretical assumptions.
10. Report uncertainty rather than presenting a random estimate as exact.

Chapter Summary

Randomized algorithms use internal random choices to improve expected performance, simplify design, or support approximate computation. Las Vegas algorithms always return correct answers but have random running time; Monte Carlo algorithms have controlled running time but may err with bounded probability. Indicator variables, linearity of expectation, conditional expectation, Markov and Chebyshev inequalities, Chernoff bounds, and Hoeffding’s inequality provide the principal analytical tools.

Randomized quicksort achieves expected Θ(n log n) comparisons, randomized selection achieves expected Θ(n) time, and universal hashing provides expected constant-time dictionary operations under suitable assumptions. Reservoir sampling enables uniform sampling from an unknown stream, while randomized contraction illustrates amplification of a low-probability success event. Random walks and MCMC extend randomized computation to probabilistic inference.

In AI and ML, randomness supports optimization, ensembles, sampling, privacy, and scalable approximation. Correct design requires explicit assumptions, suitable random-number sources, reproducibility practices, attention to tail behaviour, and governance for privacy, fairness, and security.

Key Terms

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

Las Vegas algorithm: A randomized algorithm that always produces a correct result.

Monte Carlo algorithm: A randomized algorithm with bounded or controlled time but a possible error.

Expected running time: The mean running time over the algorithm’s random executions.

Indicator variable: A variable equal to 1 when an event occurs and 0 otherwise.

Linearity of expectation: The principle that the expectation of a sum equals the sum of expectations, even without independence.

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

Chernoff bound: An exponential tail bound for sums of independent random variables.

Amplification: Repetition used to reduce error probability or increase confidence.

Universal hashing: Hashing in which collision probability is bounded over a randomly chosen hash function.

Load factor: The ratio of stored keys to hash-table slots.

Reservoir sampling: Uniform sampling from a stream using bounded memory.

Monte Carlo estimation: Estimation based on repeated random samples.

Random walk: A stochastic process that moves among states according to transition probabilities.

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

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

Mixing time: The time required for a Markov chain to approach its stationary distribution.

Oblivious adversary: An adversary that fixes the input before observing random choices.

Tail probability: The probability that a random variable deviates substantially from its typical value.

Pseudorandom generator: A deterministic generator designed to produce outputs resembling random sequences.

Review Questions

Short Answer Questions

1. Distinguish a Las Vegas algorithm from a Monte Carlo algorithm.
2. Why does linearity of expectation remain valid when indicator variables are dependent?
3. State the purpose of amplification in randomized algorithms.
4. What problem does reservoir sampling solve?
5. Why is a cryptographically secure random generator required for secret keys?

Long Answer Questions

1. Derive the expected comparison recurrence for randomized quicksort and explain why its solution is Θ(n log n).
2. Explain universal hashing and relate collision probability to expected hash-table performance.
3. Present the reservoir-sampling algorithm and prove that each stream item has equal probability of selection.
4. Compare Markov, Chebyshev, Chernoff, and Hoeffding bounds in terms of assumptions and usefulness.
5. Explain how randomization is used in AI/ML, including benefits, reproducibility challenges, and governance risks.

Analytical / Application Questions

1. Design a sampling plan for estimating a rare data-quality violation in a distributed event stream. State how you would handle stratification, independence, confidence, and privacy.
2. A randomized service has expected latency 20 ms but occasionally experiences very long delays. Explain why the expectation is insufficient and propose additional analyses or safeguards.
3. Compare randomized quickselect with deterministic worst-case linear-time selection for a production system. Make a recommendation under both ordinary and adversarial input conditions.

Multiple Choice Questions with Answers

Question 1

Which statement correctly characterizes a Las Vegas algorithm?

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

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

C. It requires a deterministic input distribution.

D. It cannot use pseudorandom numbers.

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

Question 2

For an event E with indicator variable I_E, what is E[I_E]?

A. 1 for every input

B. Pr(E)

C. Var(E)

D. The running time of E

Correct Answer: B. Pr(E)

Question 3

What is the expected comparison complexity of randomized quicksort on distinct keys?

A. Θ(log n)

B. Θ(n)

C. Θ(n log n)

D. Θ(n²) for every execution

Correct Answer: C. Θ(n log n)

Question 4

In reservoir sampling of one item from a stream, when item i arrives, what is its probability of replacing the current item?

A. 1/2

B. 1/i

C. i/n

D. 1/n²

Correct Answer: B. 1/i

Question 5

Which condition is required for the stated standard Chernoff bounds for a sum of Bernoulli variables?

A. The variables must be independent.

B. The variables must all have different means.

C. The sum must be negative.

D. The input must be sorted.

Correct Answer: A. The variables must be independent.

Question 6

Using Hoeffding’s sufficient bound for observations in [0,1], what sample-size expression ensures error at most ε with failure probability at most δ?

A. n ≥ ε² ln(2/δ)

B. n ≥ ln(2/δ)/(2ε²)

C. n ≥ 2ε²/ln(2/δ)

D. n ≥ δ/(2ε)

Correct Answer: B. n ≥ ln(2/δ)/(2ε²)

Question 7

What is the main error type of a standard Bloom filter?

A. It necessarily produces false negatives.

B. It may produce false positives but not false negatives for correctly inserted items.

C. It cannot represent duplicate items.

D. It always returns exact counts.

Correct Answer: B. It may produce false positives but not false negatives for correctly inserted items.

Question 8

Why is randomized contraction repeated in Karger’s minimum-cut algorithm?

A. One run has a nonzero but relatively small success probability.

B. The algorithm is deterministic and repetition changes nothing.

C. Repetition removes all graph edges.

D. The algorithm requires sorted vertices.

Correct Answer: A. One run has a nonzero but relatively small success probability.

Question 9

If independent trials each fail with probability p, and all k trials must fail for an amplified one-sided failure, what is the failure probability?

A. kp

B. p/k

C. p^k

D. 1 − p^k

Correct Answer: C. p^k

Question 10

What equation defines a stationary distribution π for transition matrix P?

A. π = Pπ²

B. π = πP

C. π = P + π

D. π = 0 for every state

Correct Answer: B. π = πP