Several analyses in this course are statements about averages: the expected number of comparisons of a randomized sort, the expected number of collisions in a hash table, the expected number of repetitions of a randomized subroutine that sometimes fails. Each statement is a computation of an expectation, and the same tool makes all of them short: write the quantity as a sum of indicator variables, and add the expectations. This unit sets up the finite probability vocabulary that uses only counting, proves the two basic facts (linearity of expectation and Markov's inequality), and applies them. It builds on the counting units of this chapter, since a uniform probability is a ratio of two counts.
Definitions
Definition 1.5.1
(Finite probability space and events)
A finite probability space consists of a finite set (the sample space) and a function with . An event is a subset , with . The space is uniform if for every , in which case . From the definition, , and for any events the union bound holds:
because each outcome of the union is counted at least once on the right. Events are independent if . For , the conditional probability is .
Definition 1.5.2
(Random variables, expectation and indicators)
A random variable is a function . Its expectation (mean) is
where the second sum is over the finitely many values taken by ; the two forms agree by grouping outcomes with the same value. The indicator of an event is the random variable with for and otherwise. Then . Random variables are independent if for all values .
Linearity and Markov's inequality
Theorem 1.5.3
(Linearity of expectation)
For random variables on the same finite probability space and real constants ,
No independence of the is required.
Proof
(Exchanging two finite sums)
By the definition as a sum over outcomes, , where the order of two finite sums has been exchanged.
Theorem 1.5.4
(Markov's inequality)
If on every outcome and , then .
Proof
(Splitting the sum at the threshold)
Split the sum for into outcomes with and the others. Every term is nonnegative, so . Divide by .
Theorem 1.5.5
(Product of independent variables)
If and are independent, then .
Proof
(Independence factorizes the sum)
Grouping outcomes by the pair of values, .
The indicator method. To find for a count of "bad objects", write , where is the event that the th candidate object is bad. Then by linearity. Only the individual probabilities are needed; the possibly complicated dependence among the events never enters.
Proposition 1.5.6
(Expected waiting time)
Suppose an experiment succeeds with probability independently in each trial, and let be the number of the first successful trial. Then for , and .
Proof
(Summing the tail probabilities)
The event means that the first trials all fail, which has probability . For a variable with values in one has , because and the terms are nonnegative (the definitions above extend verbatim to countable sample spaces for nonnegative variables). Hence
Worked examples
Worked example 1.5.7
(fixed points of a random permutation)
Let be a uniformly random permutation of and let be its number of fixed points. Let . The number of permutations with is , so . Then and for every . The events are not independent, but linearity does not need that.
Check for by listing all six permutations: the identity has fixed points; each of the three transpositions has ; each of the two -cycles has . The total is fixed points over permutations, an average of .
Worked example 1.5.8
(collisions in hashing)
Hash keys independently and uniformly into slots. Let be the number of pairs of keys placed in the same slot, and let be the event that keys and collide. Given the slot of key , key must pick that slot: . There are pairs, so . For and this is . Since is integer valued, Markov's inequality with gives .
Worked example 1.5.9
(inversions of a random permutation)
An inversion of a permutation is a pair with . For fixed the permutation and the permutation obtained by swapping its values at positions are equally likely, and exactly one of them has an inversion at ; so . With pairs, the expected number of inversions is . For the six permutations have inversions, with total and mean . This is the expected number of element shifts made by insertion sort on a random input order.
Worked example 1.5.10
(expected number of repetitions)
A randomized subroutine returns a correct answer with probability on each independent run, and the answer can be recognized as correct. Repeating it until success takes runs with . If , then and .
Common mistakes and subtle points
Counterexample mode
Dropping independence from the product rule
A tempting rule says for all variables, as linearity does. Let take the values and with probability each and let . Then , so , while . The variables are not independent: . The product rule needs the independence hypothesis of the theorem above; linearity does not.
Common mistake
(Mistaking the mean for a typical value)
An expectation is a weighted average, not a value the variable typically takes. A die has mean , which is never rolled; the fixed-point count in the first worked example has mean but equals with positive probability when .
Common mistake
(Moving expectation inside a nonlinear function)
In general . For uniform on , while , and while .
Common mistake
(Over-reading crude bounds)
The union bound is valid for any events, but it can exceed and then says nothing. Markov's inequality needs and gives only a crude tail bound; for the variable equal to with probability and otherwise (mean ) it is tight, which shows its constant cannot be improved in general.
Finally, in the indicator method the probability must be computed for the random experiment as stated. In the hashing example the independence of the key hashes is what makes ; for a weaker hash family one proves separately and the same argument gives an upper bound.
Exercises
Quick check
(A fair coin is tossed times. Find the expected number of heads, and the expected number of positions at which tosses and are both heads.)
Solution · Answer
Let indicate that toss is heads, with . The expected number of heads is . For adjacent pairs, the event "tosses and both heads" has probability because the tosses are independent, and there are such positions, so the expectation is by linearity.
Quick check
(For a uniformly random permutation of , a descent is a position with . Find the expected number of descents, and evaluate it for .)
Solution · Answer
For fixed , the pair of values is as likely to be as , so . With positions the expectation is , equal to for .
Quick check
(A nonnegative random variable has mean . Use Markov's inequality to bound , and give a random variable showing that this bound cannot be improved.)
Solution · Answer
Markov gives . Let with probability and otherwise. Then and , so equality is attained.
Quick check
(A test accepts a composite number with probability at most in each independent run. Show that the probability of accepting a composite number in all of runs is at most , and find the least for which this is below .)
Solution · Answer
The runs are independent, so the probability that all runs accept the composite number is the product of the individual acceptance probabilities, each at most : at most . We need , that is . Since and , the least is .
Exercise 1.5.11
(Two balls are thrown independently and uniformly into bins. Find the expected number of empty bins by (a) indicators and (b) conditioning on whether the balls land together.)
Core
Solution(3)
- 1
Count by indicators
Let indicate that bin is empty. Neither ball lands there, so , and by linearity the expected number of empty bins is .
- 2
Condition on whether the balls land together
With probability the second ball joins the first, leaving empty bins; otherwise (probability ) two bins are occupied and are empty. The expectation is .
- 3
Compare
Both methods give expected empty bins.