Engineering / Mathematics — Discrete Probability
Expectation and Variance
Expectation, variance, their algebraic properties and their use in analysing randomised algorithms.
Executive summary
Expectation is the weighted average of a random variable and is linear without qualification. Variance measures spread and is additive only under independence.
The asymmetry between these two facts governs how randomised algorithm analyses are structured.
Learning objectives
- Compute expectation and variance from a distribution.
- Apply linearity of expectation to sums of indicators.
- State the conditions for variance additivity.
01Expectation
Expectation
E[X] = Σ_s s · P(X = s), equivalently Σ_{ω} X(ω) P(ω).
Linearity
E[aX + bY] = aE[X] + bE[Y] for all random variables X, Y on the same space and all constants a, b, with no independence assumption.
A frequently useful alternative form for a non-negative integer variable is the tail sum.
E[X] = Σ_{k ≥ 1} P(X ≥ k) for X taking values in {0, 1, 2, ...}This form is often easier to evaluate, because tail probabilities are what an algorithm analysis naturally produces — the probability that a loop runs at least k times.
02Variance
Variance and standard deviation
Var[X] = E[(X − E[X])²] = E[X²] − E[X]².
The standard deviation is √Var[X], in the same units as X.
| Property | Statement | Condition |
|---|---|---|
| Scaling | Var[aX] = a²Var[X] | Always |
| Translation | Var[X + c] = Var[X] | Always |
| Additivity | Var[X+Y] = Var[X]+Var[Y] | X, Y uncorrelated |
| Sum of n terms | Var[ΣXᵢ] = ΣVar[Xᵢ] | Pairwise independent |
03Standard distributions
- Bernoulli(p)
E = p, Var = p(1−p)A single indicator; the atom of most analyses - Binomial(n,p)
E = np, Var = np(1−p)Successes in n independent trials - Geometric(p)
E = 1/p, Var = (1−p)/p²Trials until first success; unbounded - Uniform on 1..n
E = (n+1)/2, Var = (n²−1)/12Random index selection
The geometric distribution is the one that appears whenever an algorithm repeats until success — random prime generation, rejection sampling, finding a quadratic non-residue. Its expectation 1/p is what converts a per-trial success probability into an expected running time.
04Frequently asked questions
Why use E[X²] − E[X]² rather than the definition?
Because it needs only two moments and both are usually easier to compute directly, especially for sums of indicators where the square expands into pairwise products that pairwise independence handles.
Does a finite expectation guarantee finite variance?
No. Distributions with heavy tails can have finite mean and infinite variance. For the bounded variables arising from terminating algorithms the question does not arise, but it matters for unbounded loops.
Is expected running time the right measure?
It is the standard one but it hides tail behaviour. An algorithm with good expectation may still be slow with uncomfortable probability, which is why concentration inequalities are applied on top rather than instead.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 111-117.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.