What expected running time actually means
The previous guide split randomized algorithms into two camps: a Las Vegas algorithm always returns the right answer but its running time is a random variable, while a Monte Carlo algorithm runs in a fixed time but its answer is right only with high probability. In both worlds we need a single number to summarize a random quantity — how long it tends to run, or how many times it tends to fail. That number is the expectation, and learning to compute it well is most of what analyzing a randomized algorithm comes down to.
A random variable X is just a number that depends on the coin flips: the running time on a fixed input, the number of comparisons, the depth of a recursion. Its expectation E[X] is the weighted average of every value it can take, each value weighted by how likely it is: E[X] = sum over outcomes v of (v times Pr[X = v]). Concretely, if a routine takes 10 steps with probability 1/2 and 30 steps with probability 1/2, then E[X] = 10 times 1/2 + 30 times 1/2 = 20. The expectation is a balance point, not a promise — X itself may never equal 20.
The rule that makes everything easy
Here is the workhorse of the entire rung, the linearity of expectation. For any random variables X and Y, and any constants a and b, E[a*X + b*Y] = a*E[X] + b*E[Y]. Said in words: the expected value of a sum is the sum of the expected values, always. You can split a complicated random total into pieces, take the expectation of each piece on its own, and add the answers back up.
The astonishing part — the reason this rule is so powerful — is the word ALWAYS. Linearity holds even when X and Y are tangled together, even when knowing one tells you everything about the other, even when they are positively or negatively correlated. Compare this to variance or to E[X*Y], which require independence to factor nicely. Independence is a strong, fragile assumption that random algorithms rarely satisfy; linearity asks for nothing. That gap is exactly why it shows up in almost every analysis you will meet from here on.
Why is it true with no strings attached? Group the outcomes not by the value of X and Y separately but by the full underlying outcome of all the coin flips. On each individual outcome, (X + Y) is literally the number X plus the number Y at that outcome; summing 'value times probability' over all outcomes splits cleanly into the X-part and the Y-part because addition of numbers distributes over the weighted sum. Correlation only affects WHICH outcomes occur together, never the arithmetic of adding two numbers within a single outcome — so it cannot break linearity.
Indicator variables: counting by adding zeros and ones
Linearity becomes a counting machine when paired with the indicator random variable. An indicator I_A is 1 when some event A happens and 0 when it does not. Its expectation is delightfully simple: E[I_A] = 1*Pr[A] + 0*Pr[not A] = Pr[A]. So the expected value of an indicator IS the probability of its event. This tiny fact is the bridge that turns probabilities into expected counts.
The standard move, which you will reuse constantly, has three beats. Write the quantity you care about as a SUM of indicators, one per thing that might be counted. Take the expectation, and let linearity slide it inside the sum. Now you only need each individual probability Pr[A_i], which is usually easy, and you add them up — no independence, no joint distribution, no mess.
X = I_1 + I_2 + ... + I_n where I_i = 1 if event A_i occurs, else 0
E[X] = E[I_1] + ... + E[I_n] (linearity, no independence needed)
= Pr[A_1] + ... + Pr[A_n] (E of an indicator = probability)A clean warm-up: shuffle n distinct cards uniformly at random; how many land in their original position (a 'fixed point')? Let I_i indicate that card i stays put. By symmetry Pr[card i is fixed] = 1/n, since it is equally likely to land anywhere. So E[fixed points] = sum from i=1 to n of 1/n = 1, no matter how large n is. The indicators here are NOT independent — fixing one card slightly changes the odds for the others — yet linearity never noticed, and the answer is exactly 1.
A real example: comparisons in randomized quicksort
Now the payoff. Consider randomized quicksort, which on each recursive call picks its pivot uniformly at random. We want the expected number of element comparisons. The slick analysis never writes a recurrence at all — it counts directly with indicators. Sort the values mentally as z_1 < z_2 < ... < z_n, and let I_ij be the indicator that z_i and z_j are ever compared during the run. Total comparisons X = sum over all pairs i < j of I_ij, so E[X] = sum over pairs of Pr[z_i and z_j are compared].
The whole cleverness is in one probability. Two elements z_i and z_j are compared exactly when one of them is chosen as a pivot BEFORE any element strictly between them is. Look at the block of values z_i, z_(i+1), ..., z_j — that is j - i + 1 elements. The first of those to be picked as a pivot decides everything: if it is z_i or z_j, the pair gets compared; if it is one of the middle ones, that pivot splits z_i and z_j into separate sides and they never meet. Each of the j - i + 1 is equally likely to be the first pivot, so Pr[compared] = 2/(j - i + 1).
Summing the probabilities is now arithmetic. E[X] = sum over i<j of 2/(j-i+1); collecting terms by the gap j - i gives a sum of fractions 2/2 + 2/3 + 2/4 + ... that, across all pairs, totals less than 2*n times the harmonic number H_n. Since H_n is about ln n, this is O(n log n). That is the famous expected bound for randomized quicksort — derived with nothing but indicators and linearity, no expectation recurrence and no Master Theorem needed.
Pitfalls, and what expectation does not tell you
Linearity is sturdy, but two traps catch beginners. First, linearity is for SUMS, not products: in general E[X*Y] is NOT E[X]*E[Y]. That factoring needs X and Y independent, and most random variables in an algorithm are not. Second, the expectation of a function is not the function of the expectation — E[1/X] is usually not 1/E[X], and E[X^2] is not E[X]^2 (the gap between them is precisely the variance). Reach for linearity only when you have an honest sum.
There is a deeper limit worth internalizing: an expectation is a single number, and a single number can hide enormous spread. A lottery with expected winnings of a dollar might pay zero almost always and a fortune once in a million tries. So E[X] = O(n log n) for randomized quicksort tells you the AVERAGE behaviour, not that bad runs are rare. To claim 'the running time is within a constant factor of n log n with high probability,' you need a concentration result — a tail bound — that the next guide develops with Markov, Chebyshev, and the Chernoff bound.
Even so, expectation is often all you need, and not only for timing. The same indicator trick estimates how many buckets a hash table touches under universal hashing, bounds the expected number of trials before a Karger min-cut run succeeds, and underlies the entire probabilistic method in combinatorics: if the expected number of 'bad' objects is below 1, then some outcome has zero bad objects, proving a good configuration must exist. One rule about adding averages, applied again and again, carries a remarkable amount of the randomized-algorithms course.