Expectation (Expected Value)

Math for CS · Axiom Academy

Expected value, linearity, and applications The expected value (or expectation ) of a random variable is its long-run average. If you repeat an experiment infinitely many times, the average outcome converges to E[X] . Multiply each possible value by its probability, then sum everything up. Apply the definition: enumerate all values, multiply by probabilities, sum. If you recognize the distribution, use the formula directly: This is the single most powerful tool in probabilistic analysis: An indicator variable I_A is 1 if event A occurs and 0 otherwise. This is a Bernoulli variable with E[I_A] = P(A) . Combined with linearity, indicators decompose complex counting problems: Expected Value of Common Distributions Uniform (a,b) : E[X] = (a+b)/2 Applications in Computer Science Let X_ ij = 1 if elements i and j are compared during sorting. This sum evaluates to , proving average-case efficiency. There are n distinct coupons. Each time you get a random one. How many draws until you have all n ? CS Application: Expected time for a randomized algorithm to cover all cases (e.g., random testing, load distribution). If an operation takes 2ms with probability 0.9 and 50ms with probability 0.1: The average is much closer to the fast path than the slow path. The expected value of X given that event B occurred: This lets you break a complex expectation into simpler conditional parts. Linearity: E[X+Y] = E[X] + E[Y] always (even if dependent)

This is the written version of the interactive lesson above. See the full Math for CS course.