Probabilistic Analysis And Randomized Algorithms

---
name: probabilistic-analysis-and-randomized-algorithms
description: Use when analyzing randomized algorithms, probabilistic analysis, indicator random variables, hiring and secretary problems, random permutations, balls-and-bins, birthday paradox, streaks, or average-case versus expected-time reasoning.
license: MIT
---

# Probabilistic Analysis and Randomized Algorithms

## Overview

Use probability to analyze either a distribution on inputs or random choices made by an algorithm. The core move is to name the sample space first, then convert events into expectations with indicator random variables whenever direct counting becomes messy.

## Shared CLRS Conventions

Follow the parent `clrs` skill for mathematical formatting, formula-free headings, direct polished answers, and CLRS-wide answer style.

## When to Use

- A problem asks for average-case cost under random input order.
- A randomized algorithm permutes, samples, searches, or makes random choices internally.
- Expected counts involve records, collisions, empty bins, inversions, fixed points, or repeated trials.
- A prompt asks whether a shuffle, sample, or randomized strategy is uniform.
- A problem asks for the birthday paradox, balls-and-bins, coupon collector, streaks, or online hiring.

Do **not** use this skill merely because an answer contains asymptotic notation. Use `characterizing-running-times` when probability is not part of the model.

## First Distinction

| Situation | Concept | Expectation is over | Required statement |
| --- | --- | --- | --- |
| Deterministic algorithm, random input model | Average-case analysis | Input distribution | State the assumed input distribution |
| Algorithm makes random choices | Expected running time or expected cost | Random-number generator outcomes | State the guarantee for each fixed input if applicable |

Do not conflate these. Randomizing the input inside the algorithm removes the need to assume a random input distribution, but it adds work for the randomization step.

## Indicator Random Variable Workflow

Use this whenever the quantity is a count of events.

1. Define one event per item, trial, pair, or position.
2. Define the indicator:

$$
X_i = I\{A_i\}.
$$

3. Use Lemma 5.1:

$$
E[X_i] = \Pr\{A_i\}.
$$

4. Express the total count as a sum:

$$
X = \sum_i X_i.
$$

5. Apply linearity of expectation:

$$
E[X] = \sum_i E[X_i].
$$

Independence is **not required** for linearity of expectation. Independence matters only when multiplying probabilities or using distribution facts that require it.

## Hiring Problem

For `HIRE-ASSISTANT`, a candidate in position:

$$
i
$$

is hired exactly when that candidate is the best among the first:

$$
i
$$

candidates.

Use:

$$
X_i = I\{\text{candidate } i \text{ is hired}\}.
$$

Under a uniform random arrival order:

$$
\Pr\{\text{candidate } i \text{ is hired}\} = \frac{1}{i}.
$$

Therefore:

$$
E[X] = \sum_{i=1}^{n}\frac{1}{i} = \ln n + O(1).
$$

The average-case hiring cost is:

$$
O(c_h\ln n),
$$

excluding the unavoidable interviewing cost:

$$
c_i n.
$$

Worst case still hires every candidate when ranks arrive in increasing order, giving hiring cost:

$$
O(c_h n).
$$

## Random Permutations

A uniform random permutation means every one of the possible permutations has probability:

$$
\frac{1}{n!}.
$$

It is **not enough** to prove that each element has probability:

$$
\frac{1}{n}
$$

of landing in each position. That condition is only marginal uniformity.

Use `PERMUTE-BY-CYCLE` as the counterexample: choose a random cyclic offset and rotate all elements by that offset. Each element lands in each position with probability:

$$
\frac{1}{n},
$$

but only the cyclic rotations can occur. Most of the possible permutations have probability zero, so the distribution is not uniform.

For `RANDOMLY-PERMUTE`, also called `RANDOMIZE-IN-PLACE` in some editions, which swaps the current array position with a random position from the current suffix, prove uniformity with this invariant: just before iteration:

$$
i,
$$

each possible prefix of length:

$$
i - 1
$$

occurs with probability:

$$
\frac{(n-i+1)!}{n!}.
$$

Maintenance: a fixed next element is selected from the remaining positions with probability:

$$
\frac{1}{n-i+1}.
$$

At termination, each full permutation has probability:

$$
\frac{1}{n!}.
$$

## Random Sampling

To show a sampling procedure returns a uniform subset, prove the subset distribution, not just per-element inclusion probabilities. `RANDOM-SAMPLE` makes only:

$$
m
$$

calls to `RANDOM` and maintains that the returned set is a uniform subset of the current prefix size after each loop iteration.

## Birthday Paradox

For exact collision probability, analyze the complement that all birthdays are distinct:

$$
\Pr\{\text{all distinct}\} = \prod_{i=1}^{k-1}\left(1-\frac{i}{n}\right).
$$

Use:

$$
1+x \le e^x
$$

to get the threshold where collision probability is at least one half:

$$
k(k-1) \ge 2n\ln 2.
$$

For the indicator approximation, define one indicator per pair of people. The expected number of matching pairs is:

$$
\binom{k}{2}\frac{1}{n} = \frac{k(k-1)}{2n}.
$$

Remember the two questions differ: probability of at least one collision and expected number of colliding pairs need not have the same threshold.

## Balls and Bins

For a fixed bin after tossing:

$$
n
$$

balls into:

$$
b
$$

bins, the expected load is:

$$
\frac{n}{b}.
$$

The expected tosses until a fixed bin receives a ball is:

$$
b.
$$

For the coupon collector question, partition the process into stages where a hit means landing in an empty bin. In stage:

$$
i,
$$

the hit probability is:

$$
\frac{b-i+1}{b}.
$$

The expected time to fill every bin is:

$$
\sum_{i=1}^{b}\frac{b}{b-i+1} = b(\ln b + O(1)).
$$

## Streaks of Heads

For a streak of at least:

$$
k
$$

heads beginning at a fixed position:

$$
\Pr\{A_{ik}\} = \frac{1}{2^k}.
$$

Use a union bound to show long streaks are unlikely. For length about twice the logarithm, the probability of a streak anywhere is at most:

$$
\frac{1}{n}.
$$

For the lower bound, partition flips into groups of length about half the logarithm and show a full-heads group occurs with high probability. The expected longest streak has length:

$$
\Theta(\lg n).
$$

For an approximate indicator analysis of streaks of length at least:

$$
k,
$$

use:

$$
E[X_k] = \frac{n-k+1}{2^k}.
$$

## Online Hiring Problem

For `ONLINE-MAXIMUM`, reject the first:

$$
k
$$

candidates, then hire the first later record. Assume a uniform random order and distinct scores.

Let:

$$
S_i
$$

be success when the best applicant appears in position:

$$
i.
$$

There is no success for the first:

$$
k
$$

positions. For later positions:

$$
\Pr\{S_i\} = \frac{1}{n}\cdot\frac{k}{i-1}.
$$

Therefore:

$$
\Pr\{S\} = \sum_{i=k+1}^{n}\frac{k}{n(i-1)} = \frac{k}{n}\sum_{i=k}^{n-1}\frac{1}{i}.
$$

Integral bounds give the useful approximation:

$$
\Pr\{S\} \approx \frac{k}{n}(\ln n - \ln k).
$$

Maximize the lower-bound expression by choosing:

$$
k \approx \frac{n}{e}.
$$

Then the success probability is at least about:

$$
\frac{1}{e}.
$$

## Common Patterns

| Problem shape | Indicator choice | Result to reach |
| --- | --- | --- |
| Expected hires or records | One indicator per position being a new maximum | Harmonic sum |
| Hat-check fixed points | One indicator per customer getting own hat | Expected value one |
| Random inversions | One indicator per pair out of order | Half of all pairs |
| Birthday matches | One indicator per pair sharing a day | Pair count divided by days |
| Empty bins | One indicator per bin empty | Multiply by probability a fixed bin is empty |
| Streak starts | One indicator per possible starting position | Count starts times single-start probability |

## Common Mistakes

| Mistake | Correction |
| --- | --- |
| Using indicator variables but trying to prove independence before summing expectations | Linearity of expectation does not require independence |
| Saying average-case and expected running time are the same thing | Average-case is over input distribution; expected time is over algorithmic random choices |
| Proving each element is equally likely in each position and calling the shuffle uniform | Prove every full permutation has equal probability; use `PERMUTE-BY-CYCLE` as the marginal-uniform counterexample |
| Ignoring the cost model in the hiring problem | Separate unavoidable interview cost from random hiring cost |
| Treating expected number of birthday matches as the same as probability of at least one match | These are related but answer different questions |
| Multiplying probabilities without checking independence or conditional probability | Use conditional probability explicitly when events are not obviously independent |
| Claiming online hiring always finds the best with high probability | The classic threshold succeeds with probability only about the reciprocal of Euler's number |