Counting, conditional expectation, correlation and descriptive statistics

Counting

Multiplication rule. If a task has stages with $n_1, n_2, \dots$ choices each, there are $n_1 n_2 \cdots$ ways in all.

Situation	Count
Ordered selection of $r$ from $n$ (a permutation)	$^nP_r = \frac{n!}{(n - r)!}$
Unordered selection of $r$ from $n$ (a combination)	$\binom{n}{r} = \frac{n!}{r!(n - r)!}$
Arrangements of $n$ items with repeats $n_1, n_2, \dots$	$\frac{n!}{n_1!\,n_2!\cdots}$
$n$ people round a table	$(n - 1)!$
$r$ choices from $n$ types, repetition allowed, order irrelevant	$\binom{n + r - 1}{r}$
Sequences of length $r$ from $n$ symbols	$n^r$

Examples.

• MISSISSIPPI has $\frac{11!}{4!\,4!\,2!} = 34{,}650$ arrangements.
• The equation $x_1 + x_2 + x_3 = 10$ has $\binom{12}{2} = 66$ solutions in non-negative integers, by stars and bars: arrange 10 stars and 2 bars.
• A committee of 3 chosen from 5 men and 4 women, with at least one woman: $\binom93 - \binom53 = 84 - 10 = 74$.

Inclusion–exclusion. $\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert - \lvert A \cap B\rvert$, and for three sets add back the triple intersection. Among 1 to 100, the numbers divisible by 2 or 3 number $50 + 33 - 16 = 67$.

Derangements. A derangement is a permutation with no fixed point. There are

$D_n = n!\left(1 - \frac1{1!} + \frac1{2!} - \dots + \frac{(-1)^n}{n!}\right) \approx \frac{n!}{e}$

of them. For example $D_3 = 2$ and $D_4 = 9$. So the chance that a random permutation has no fixed point tends to $1/e \approx 0.368$.

Pigeonhole principle. Putting $n + 1$ items into $n$ boxes puts at least two in one box. Among any 13 people, two share a birth month.

Probability by counting

When all outcomes are equally likely, $P(A) = \frac{\lvert A\rvert}{\lvert S\rvert}$.

Example 1. Two cards drawn from a deck are both aces with probability $\frac{\binom42}{\binom{52}{2}} = \frac{6}{1326} = \frac{1}{221}$.

Example 2: the birthday problem. In a group of $k$ people, assuming 365 equally likely birthdays, $P(\text{all different}) = \frac{365 \cdot 364 \cdots (365 - k + 1)}{365^k}.$ For $k = 23$ this is about 0.493, so a shared birthday is more likely than not (0.507).

The hypergeometric distribution. Draw $n$ items without replacement from $N$ items, of which $K$ are "successes": $P(X = k) = \frac{\binom{K}{k}\binom{N - K}{n - k}}{\binom{N}{n}}, \qquad E[X] = n\frac{K}{N}.$

Example 3. A batch has 10 items, 3 of them defective. Pick 4 at random.

• $P(\text{exactly 1 defective}) = \frac{\binom31\binom73}{\binom{10}{4}} = \frac{3 \times 35}{210} = 0.5$.
• The expected number of defectives is $4 \times 0.3 = 1.2$.

Conditional expectation

Definition. $E[X \mid Y = y] = \sum_x x\,P(X = x \mid Y = y)$, or $\int x\,f(x \mid y)\,dx$. As $y$ varies, $E[X \mid Y]$ is itself a random variable, a function of $Y$.

Law of total expectation: $E[X] = E\big[E[X \mid Y]\big].$ To average over everything, average within each case, then average the cases.

Law of total variance: $\operatorname{Var}(X) = E\big[\operatorname{Var}(X \mid Y)\big] + \operatorname{Var}\big(E[X \mid Y]\big).$ The total spread is the average spread within groups plus the spread between the group means.