What is linearity of expectation?

easy

Answer

$For any random variables X, Y and constants a, b: E[aX + bY] = a*E[X] + b*E[Y].$
$Holds regardless of dependence between X and Y.$
$Very useful because it lets you decompose expectations of complex sums into pieces even when the pieces are dependent.$
$Example: expected number of collisions in a hash table with n keys and m slots is (n choose 2)/m — via linearity over the C(n,2) pairs.$

Check yourself — multiple choice

Requires independence
E[aX + bY] = a·E[X] + b·E[Y] regardless of dependence — decompose sums even under correlation
Only for discrete
Doesn't hold

Linearity of expectation: holds without any independence assumption.

#expectation#probability

215 interview questions in this topic.