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 \mathrm{Pr}\{X=x\}.$$ For a fair die, $E[X]=\frac{1}{6}(1+2+\cdots +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 \mathrm{Pr}\{A\}+0\cdot \mathrm{Pr}\{\bar{A}\}=\mathrm{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],E\left[\sum _i{X}_i\right]=\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]=\mathrm{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 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ — 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 $\mathrm{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

• $\mathrm{Pr}\{\bar{A}\}=1-\mathrm{Pr}\{A\}$, and the union bound $\mathrm{Pr}\{\bigcup A_i\}\le \sum \mathrm{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.