Chapter 134

Home

Probability and Expected Value

Expected value E[X] = Σ x × P(X = x). Linearity of expectation: E[X+Y] = E[X] + E[Y] even if X and Y are dependent. This is the most powerful tool for probability problems in CP.

Linearity of Expectation

C++ — expected number of distinct faces after K dice rolls

// Expected distinct faces = Σ P(face i appears at least once)
// = Σ (1 − P(face i never appears))
// = Σ (1 − (5/6)^K)
// = 6 × (1 − (5/6)^K)

double expected_distinct(int k) {
    return 6.0 * (1.0 - pow(5.0 / 6.0, k));
}
// Using linearity: E[sum of indicators] = sum of E[indicator]

📐 Indicator random variables

Define Iᵢ = 1 if event i happens. Then E[count] = Σ P(event i). This trick solves most CP expected-value problems — no complex probability distributions needed.