Source: Comprehensive Guide to Probability Theory and Applications
Tags: expected value, mean, variance, standard deviation, random variable, inversions, permutation, lottery probability, hash function collision, probability applications
Difficulty: Intermediate Prerequisites: Probability foundations (sample spaces, events) and basic distributions (uniform, binomial). You should be comfortable with summation notation and the concept of a random variable.
Expected value and variance are the two numbers that summarise a random variable's behaviour: where its outcomes tend to cluster (expectation) and how spread out they are (variance). These measures show up everywhere, from evaluating gambling games to analysing algorithm performance. This final set of notes also covers practical applications of probability, including lottery odds and hash function collisions, which bridge the gap between textbook theory and problems you will encounter in computer science and engineering.
The expected value (mean) of a random variable is the probability-weighted average of its outcomes. Variance measures how far outcomes typically stray from that average. Together they give you a compact description of any distribution. Applications like lottery probability and hash collisions show how these tools work outside the classroom.
Random variable (X)
A function that assigns a numerical value to each outcome in a sample space. It turns "what happened" into a number you can do arithmetic with. Think of it as a scoreboard for a random experiment.
Expected value, E(X)
The long-run average value of a random variable if the experiment were repeated many times. Calculated as E(X) = Σ x · P(X = x). In simple terms, it is the "centre of gravity" of the distribution.
Variance, Var(X)
A measure of how spread out the values of a random variable are around the mean. Var(X) = E[(X − E(X))²] = E(X²) − [E(X)]². Think of it as quantifying the "typical surprise" each outcome delivers.
Standard deviation
The square root of the variance. It has the same units as X, making it easier to interpret than variance. In simple terms, it is the variance translated back into the original scale.
Inversion (in a permutation)
A pair of elements (i, j) where i appears before j in the sequence but i > j. Counting inversions measures how far a permutation is from being sorted. Think of it as: every swap that a simple sorting algorithm would need to fix.
Hash collision
When two distinct keys are mapped to the same location by a hash function. Probability analysis helps estimate how likely collisions are for a given number of keys and table size. In simple terms, two items trying to sit in the same chair.
Definition: E(X) = Σ x · P(X = x), summing over all possible values of X.
Linearity of expectation is one of the most powerful tools in probability:
E(aX + b) = a · E(X) + b for constants a and b.
E(X + Y) = E(X) + E(Y), regardless of whether X and Y are independent.
This linearity property lets you break a complicated random variable into simpler pieces, compute each expected value separately, and add them up.
For a fair six-sided die: E(X) = (1 + 2 + 3 + 4 + 5 + 6) / 6 = 3.5.
Definition: Var(X) = E[(X − E(X))²].
Computational shortcut: Var(X) = E(X²) − [E(X)]².
Often easier in practice because you avoid computing the squared deviations individually.
Properties:
Var(aX + b) = a² · Var(X). Adding a constant shifts the distribution but does not change its spread; scaling by a multiplies the variance by a².
If X and Y are independent, Var(X + Y) = Var(X) + Var(Y).
A permutation of {1, 2, …, n} has a random number of inversions.
Each pair (i, j) with i < j is inverted with probability 1/2 in a uniformly random permutation.
The total number of pairs is C(n, 2) = n(n − 1)/2.
By linearity of expectation, the expected number of inversions is:
E(inversions) = n(n − 1)/2 · 1/2 = n(n − 1)/4.
This result matters in algorithm analysis. Insertion sort, for example, performs a number of swaps equal to the number of inversions, so its average-case running time on a random input is Θ(n²/4) = Θ(n²).
A simple "pick 4 digits" lottery has 10,000 equally likely combinations (0000 through 9999).
P(winning) = 1/10,000 = 0.0001.
Lotteries are a straightforward application of the uniform distribution and counting.
For more complex lotteries (e.g. "choose 6 from 49"), the calculation uses combinations: P(winning) = 1 / C(49, 6).
Setup: n keys hashed into m locations, assuming each key maps to any location with equal probability (uniform hashing assumption).
The probability of no collisions among n keys:
P(no collision) = (m/m) · ((m − 1)/m) · ((m − 2)/m) · … · ((m − n + 1)/m)
= m! / ((m − n)! · mⁿ)
This is structurally identical to the Birthday Problem: with 23 people and 365 days, the probability of a shared birthday exceeds 50%.
In computing, hash table design uses this analysis to choose table sizes that keep collision probability acceptably low.
Name | Formula |
|---|---|
Expected value | E(X) = Σ x · P(X = x) |
Linearity of expectation | E(X + Y) = E(X) + E(Y) |
Variance (definition) | Var(X) = E[(X − E(X))²] |
Variance (shortcut) | Var(X) = E(X²) − [E(X)]² |
Expected inversions | E(inversions) = n(n − 1) / 4 |
Lottery (uniform) | P(win) = 1 / (total combinations) |
No hash collision | P = m! / ((m − n)! · mⁿ) |
Expected value is the basis of decision theory in finance: an investment's "expected return" is E(X). Variance (and its square root, standard deviation) is how risk is quantified in a portfolio. In computer science, expected-case analysis of algorithms (like quicksort's average O(n log n)) relies on linearity of expectation. Hash collision analysis directly informs database indexing and in-memory caching strategies.
Students often think the expected value must be a value that X can actually take. It need not be. A fair die has E(X) = 3.5, but you can never roll 3.5.
Confusing variance with standard deviation. Variance is in squared units; standard deviation is the square root and shares the original units. Exam questions sometimes ask for one when you have computed the other.
Assuming Var(X + Y) = Var(X) + Var(Y) always. This only holds when X and Y are independent. For dependent variables, you must account for covariance.
Treating the Birthday Problem / hash collision calculation as if the events are independent. The successive "no collision" probabilities are conditional on all previous keys having avoided collisions, so you multiply conditional probabilities, not independent ones.
⚠️ The variance shortcut formula E(X²) − [E(X)]² is faster than the definition in almost every exam problem. Memorise it and practise using it.
⚠️ Linearity of expectation questions are popular because they look hard but become simple once you decompose the random variable. The inversions example is a classic.
⚠️ Hash collision and Birthday Problem questions test whether you can set up a product of conditional probabilities. Write out the first few terms to avoid index errors.
⚠️ Know the distinction between expected value and most likely value (mode). They are not always the same.
True or false: E(X) must be one of the possible values of X.
Fill in the blank: Var(X) = E(X²) − ______.
True or false: Linearity of expectation requires X and Y to be independent.
For a random permutation of 10 elements, what is the expected number of inversions?
True or false: Standard deviation is the square of the variance.
Answers: 1. False (e.g. E(fair die) = 3.5). 2. [E(X)]². 3. False, linearity holds regardless of independence. 4. 10 × 9 / 4 = 22.5. 5. False, standard deviation is the square root of the variance.
Q: A fair six-sided die is rolled. What is E(X)?
A: E(X) = (1 + 2 + 3 + 4 + 5 + 6) / 6 = 21/6 = 3.5.
Q: If E(X) = 5 and Var(X) = 4, what is E(X²)?
A: From Var(X) = E(X²) − [E(X)]², we get E(X²) = Var(X) + [E(X)]² = 4 + 25 = 29.
Q: Why does linearity of expectation make the inversions problem tractable?
A: Because you can define an indicator variable for each pair and compute its expectation (1/2) independently, then sum over all C(n,2) pairs. Without linearity, you would need the full joint distribution of all pairs.
Q: In a hash table with 365 slots and 23 keys (uniform hashing), is a collision more likely than not?
A: Yes. This is the Birthday Problem. With 23 keys and 365 slots, the probability of at least one collision exceeds 50%.
Q: What is the probability of winning a "pick 4 digits" lottery?
A: 1/10,000 = 0.0001. Each of the four positions has 10 choices, giving 10⁴ = 10,000 equally likely combinations.
Expected value and variance are the first two "moments" of a distribution. Higher moments (skewness, kurtosis) describe shape and tail behaviour, which matter in statistics and finance.
The inversions-in-a-permutation result connects to sorting algorithm analysis, a core topic in data structures and algorithms courses.
Hash collision probability ties into the design of hash maps, Bloom filters, and cryptographic hash functions, all central to systems programming and security.
expected value formula, variance formula, standard deviation, linearity of expectation, random variable, E(X), Var(X), inversions permutation expected value, birthday problem, hash collision probability, lottery odds, uniform hashing assumption, algorithm average case, moment of distribution, STAT 101, CS foundations Purdue, probability applications