Lesson 290
Probability & Expected Value
Expectation & Linearity
1:00How to compute expected value, why linearity of expectation works for any random variables, and how the indicator trick powers average-case algorithm analysis.
By the end, you can
- Compute P(event) from a sample space and identify favorable outcomes.
- Calculate E[X] = Σ x · P(x) for a discrete distribution.
- Apply linearity of expectation to find the expected sum of multiple random variables without enumeration.
- Explain why linearity of expectation does not require independence, and contrast this with variance.
- Define indicator variables, state that E[I] = P(event), and use them to solve the hat-check problem.
- State the variance formula Var(X) = E[X²] − (E[X])² and identify when variances can be added.
- Recognize how randomized quicksort, treaps, skip-lists, and reservoir sampling all rely on expectation and linearity.
Up next in String Algorithms, Advanced DP & Competitive Techniques
