Probability and Expected Value

The problem

Randomness enters competitive programming in three ways.

• Probability: how likely is an outcome? "What is the chance the die shows 6?"
• Expected value (EV): the average result if you repeated the process many times. "On average, how many rolls until the first 6?"
• Modular answers: the expected value is a fraction $p/q$, and the statement asks for $p \cdot q^{-1}$ modulo a prime.

Definition: $E[X] = \sum_x x \cdot P(X = x)$, each outcome weighted by its probability.