Probability & expectation in one page

The one page you need (the rest is in Module 2)

This course uses probability only as a *tool* — for randomized quicksort (2.4), selection (2.7), and hashing (3.4). You do not need measure theory; you need three things.

1. Random variables and expectation. A random variable $X$ is a function from outcomes to numbers. Its expected value (mean) is $$E[X] = \sum_x x \cdot \Pr\{X = x\}.$$ For a fair die, $E[X] = \frac{1}{6}(1+2+\dots+6) = 3.5$.

2. Indicator random variables. An indicator $X_A$ for an event $A$ is $1$ if $A$ happens, $0$ otherwise. Its expectation equals the event's probability: $$E[X_A] = 1\cdot\Pr\{A\} + 0\cdot\Pr\{\bar A\} = \Pr\{A\}.$$ This tiny fact is the bridge from *probabilities* to *counts*: to count how many of many events occur, sum their indicators.

3. Linearity of expectation. For any random variables, $$E[X + Y] = E[X] + E[Y], \qquad E\Big[\sum_i X_i\Big] = \sum_i E[X_i].$$ The magic word is *any* — this holds even when the variables are dependent. No independence is required. (Independence is only needed for $E[XY] = E[X]\,E[Y]$ and for variances to add — not for sums of expectations.)

The pattern: indicators + linearity

Put 2 and 3 together and you get the single most useful technique in randomized analysis: to find the expected *number* of times something happens, define an indicator for each opportunity, take each one's expectation (a probability), and sum them — dependence be damned.

Worked example — expected number of heads. Flip a biased coin (heads with probability $p$) $n$ times; let $X$ = number of heads. Let $X_i = 1$ if flip $i$ is heads. Then $X = \sum_{i=1}^{n} X_i$, and $E[X_i] = \Pr\{\text{flip } i \text{ heads}\} = p$, so $$E[X] = \sum_{i=1}^{n} E[X_i] = \sum_{i=1}^{n} p = np.$$ No combinatorics, no $\binom{n}{k}$ — just $n$ indicators and one line of linearity. (Even if the flips were correlated, $E[X] = np$ would still hold; only the *variance* would change.)

Where this goes. In randomized quicksort (Module 2.4) the indicator $X_{ij} = 1$ if elements $i$ and $j$ are ever compared, with $\Pr\{X_{ij} = 1\} = \frac{2}{j - i + 1}$. Summing those indicators gives $E[\text{comparisons}] = \sum_i \sum_j \frac{2}{j-i+1}$, and that double sum is a harmonic series — which (from Lesson 0.2) is $\Theta(\lg n)$ per element, yielding the famous expected $\Theta(n \lg n)$. This is why the harmonic series sits in your toolkit: it is the seam where probability meets running time.

A few facts to keep nearby

- $\Pr\{\bar A\} = 1 - \Pr\{A\}$, and the union bound $\Pr\{\bigcup A_i\} \le \sum \Pr\{A_i\}$ (true even when events overlap) — handy for bounding "any bad event" probabilities. - A geometric wait-for-first-success has mean $1/p$ (probe counts in hashing); a binomial count of successes in $n$ trials has mean $np$ (the indicator argument above) — both will reappear in Module 3.