Randomized algorithms: expectation and the union bound

Linearity holds regardless

For any random variables $X_1, \dots, X_n$,

$\mathbb{E}\left[\sum_i X_i\right] = \sum_i \mathbb{E}[X_i]$

with no independence assumption. This is worth stating loudly because almost every clever expectation argument in this course leans on exactly that.

The standard use: to count occurrences of something, define an indicator $X_i$ for each candidate, sum them, and take expectations. The indicators are usually wildly dependent and it does not matter.