Show existence of an object by proving the probability of its existence is positive. Example: Lower bound for Ramsey numbers: If $\binom{n}{k} 2^{1-\binom{k}{2}} < 1$, then $R(k,k) > n$.

Linearity of expectation: $E[X+Y] = E[X] + E[Y]$ (always, even for dependent variables). Example: Expected number of fixed points in a random permutation of $n$ elements: Let $X_i = 1$ if $i$ is fixed, 0 otherwise. $E[X_i] = 1/n$. By linearity, $E[\sum X_i] = n \cdot 1/n = 1$. Join Discord PreviousBoolean AlgebraNextAlgebraic Structures