Randomized Algorithms

A randomized algorithm treats random bits as part of its input. For one fixed ordinary input $x$, different random strings may produce different execution paths, running times, or answers. The analysis must therefore quantify over the algorithm's own choices: what is always correct, what is merely likely, and which random experiment makes the probability statement true?

Randomization is useful when it avoids hostile structure, samples an enormous search space, breaks symmetry, or gives a simple procedure whose bad executions are provably rare. It is not a substitute for a proof. The probability distribution and the failure event are part of the contract.

The two fundamental contracts #

A Las Vegas algorithm may occasionally take a long path, but it never trades correctness for speed. A Monte Carlo algorithm stops within its promised resource bound but accepts a controlled chance of error.

Monte Carlo errors can be:

• one-sided: one answer is conclusive, while the other may be wrong. A Miller–Rabin witness proves compositeness; "probable prime" may be a false positive.
• two-sided: either answer may be wrong, each within a stated bound.

Probability is over named random choices #

Write $A(x;R)$ for algorithm $A$ on fixed input $x$ and random string $R$. A typical worst-input, random-choice guarantee is

$$\forall x\quad \Pr_R[A(x;R)\text{ fails}]\le\varepsilon.$$

This is stronger than assuming inputs themselves are random. An adversary may choose the worst $x$ before the independent seed is drawn. If it can observe or influence $R$ first, the quantifier order changes and the proof may no longer apply.

Three common performance statements are different:

• in expectation: $\mathbb E_R[T(x,R)]=O(f(n))$;
• with probability at least $1-\delta$: $T(x,R)\le g(n,\delta)$ except on a $\delta$ fraction of random choices;
• with high probability: conventionally at least $1-n^{-c}$ for a stated or arbitrary constant $c>0$.

An expectation does not prohibit a heavy tail. Markov's inequality gives only

$$\Pr[T\ge a\,\mathbb E T]\le\frac1a$$

for a nonnegative $T$ without additional structure. Stronger tail bounds require stronger hypotheses such as independence or bounded differences.

Worked analysis: randomized quicksort #

Choose the pivot uniformly from the current subarray, partition, and recurse. Partitioning is exact, so the output is always sorted: this is Las Vegas randomization. Its worst-case work remains $\Theta(n^2)$, but the expected comparison count is $O(n\log n)$ for every fixed ordering of distinct keys.

Sort the keys by rank, and let $X_{ij}$ indicate whether ranks $i<j$ are ever compared. They are compared exactly when the first pivot selected from ranks $i,i+1,\ldots,j$ is one of the two endpoints. Each element of that interval is equally likely to be first, hence

$$\Pr[X_{ij}=1]=\frac{2}{j-i+1}.$$

By linearity of expectation—no independence between the indicators is needed—

$$\mathbb E[C] =\sum_{i<j}\mathbb E[X_{ij}] =\sum_{i<j}\frac{2}{j-i+1} =O(n\log n).$$

The analysis explains the mechanism: random pivots prevent any fixed input order from consistently forcing extremely unbalanced partitions. Randomizing the input once is equivalent only if the shuffle is actually uniform and independent of the input arrangement.

Worked analysis: Karger's contraction algorithm #

For an undirected multigraph, repeatedly choose a uniformly random current edge and contract its endpoints, retaining parallel edges and deleting self-loops. When two supervertices remain, their crossing edges define a cut.

Fix one minimum cut of size $\lambda$. When $r$ supervertices remain and none of its edges has yet been contracted, every vertex has degree at least $\lambda$, so the graph has at least $r\lambda/2$ edges. The probability that the next chosen edge avoids the fixed cut is therefore at least

$$1-\frac{\lambda}{r\lambda/2}=1-\frac2r.$$

Surviving from $n$ vertices down to two has probability at least

$$\prod_{r=n}^{3}\left(1-\frac2r\right) =\frac{2}{n(n-1)}.$$

One run has a small but explicit success probability. Run it $t$ times independently and keep the smallest cut found. The probability that every run misses this fixed minimum cut is at most

$$\left(1-\frac{2}{n(n-1)}\right)^t \le e^{-2t/(n(n-1))}.$$

This is the standard amplification pattern: identify an independently repeatable trial, combine answers in a correctness-preserving way, and calculate the number of trials from the desired failure budget.

One-sided error: Miller–Rabin #

For an odd candidate $n>3$, write $n-1=2^s d$ with $d$ odd. A round chooses a base $a$, computes $a^d\bmod n$, and repeatedly squares. For a prime $n$, Fermat's theorem and the structure of the multiplicative group force the sequence to begin at $1$ or reach $-1\bmod n$ before reaching $1$. A base that violates this pattern certifies that $n$ is composite.

For any fixed odd composite $n$, at most one quarter of admissible bases are strong liars. Thus $k$ independent uniformly sampled bases give

$$\Pr[\text{composite survives all }k\text{ rounds}]\le 4^{-k}.$$

The conditional language matters: the bound is over independent base choices for a fixed composite. Reusing a predictable base list against adversarially selected numbers, introducing modulo bias, or accidentally correlating rounds invalidates the multiplication of error probabilities. A conclusive primality proof is a different contract from a probable-prime test.

Amplification and verification #

Suppose one trial fails with probability at most $p<1$ and trials use independent randomness.

• Repeat a one-sided test $k$ times and accept only if every trial accepts: failure is at most $p^k$.
• For a two-sided test correct with probability $1/2+\gamma$, take a majority of independent trials; concentration bounds make majority error fall exponentially in $k\gamma^2$.
• For Las Vegas search, verify a candidate deterministically and retry on failure. If each independent attempt succeeds with probability at least $q$, expected attempts are at most $1/q$.

flowchart TD
    R["Draw independent random bits"] --> A["Run one trial"]
    A --> V{"Certificate check available?"}
    V -->|"yes"| C["Verify; return or retry — Las Vegas"]
    V -->|"no"| M["Combine repeated answers — Monte Carlo"]
    C --> G["Always-correct answer; random cost"]
    M --> P["Bounded cost; quantified failure probability"]

The combination rule must match the error direction. Repetition cannot repair a systematic implementation error or a biased generator that concentrates on bad choices.

Turning mathematical randomness into bits #

Analysis often assumes independent uniform samples; an implementation receives bits from a pseudorandom generator or operating-system entropy interface.

1. Uniform range sampling: random_word % m is biased unless the word range is divisible by $m$. Reject the incomplete high tail and redraw.
2. Reproducibility: record the algorithm version, input, seed, and generator identity for debugging and experiments. A seed without generator/version semantics may not reproduce a stream later.
3. Independence: cloning generator state or seeding many workers from a coarse clock can duplicate streams. Parallel substreams require a designed split/jump/counter scheme.
4. Adversaries: a simulation-quality generator is not automatically unpredictable. When the random choices protect security, fairness, or denial-of-service resistance, use the system's cryptographic randomness contract.
5. Testing: statistical tests can reveal defects but cannot prove that all future outputs are independent and uniform. Validate the generator separately from the algorithmic proof.

The details of generator construction and testing belong in PRNG algorithms and PRNG statistical tests. The randomized algorithm's obligation is to state exactly which properties it consumes.

Derandomization and controlled determinism #

Randomness can sometimes be removed:

• enumerate all choices when the sample space is small;
• use the method of conditional expectation to fix choices one at a time without worsening the expected objective;
• replace full independence with a proven limited-independence family;
• exploit an input-specific deterministic witness set;
• use randomization during discovery, then verify the result deterministically.

Derandomization is theorem-specific. Replacing random() with a fixed seed does not create a deterministic guarantee; it merely selects one path whose quality still needs proof.

Audit checklist #

1. What is fixed, and what is random—input distribution, seed, samples, schedule?
2. Is the algorithm Las Vegas or Monte Carlo? If Monte Carlo, which answer can be wrong?
3. Is the guarantee expected, high-probability, or worst-case?
4. What exact event counts as failure, and what is its bound for every allowed input?
5. Which steps require uniformity or independence, and does the implementation supply them?
6. Does amplification combine results in a way that preserves the promised answer?
7. Can a candidate be checked deterministically and converted to Las Vegas behavior?
8. Are seed and generator version captured for reproduction without exposing security-sensitive state?
9. Does adversarial observation or control change the quantifier order assumed by the proof?
10. Are random-number generation costs, retries, and tail latency included in the resource model?