Averaging instead of fearing the worst
Probabilistic analysis studies an algorithm's behavior on average rather than in its single worst case. The average is taken either over a probability distribution of inputs or over the algorithm's own random choices. The result is an expected running time, the mean across all the outcomes weighted by their probability.
The hiring problem intuition
A common teaching example interviews candidates in random order and hires whenever someone is better than all seen so far. The worst order forces hiring at every step, but in a random order the expected number of hires is small, because a new candidate is the best so far only occasionally. This expectation is computed by summing the small probabilities that each position is a new maximum.
- Indicator random variables turn each event into a zero or one and make expectations easy to sum.
- Linearity of expectation lets you add per event expectations even when the events are dependent.
Worst case versus expected
Expected case is not the same as best case; it is a weighted average that includes bad outcomes with their true probabilities. A randomized algorithm's expected time holds for every input, because the averaging is over coin flips, not over a hopeful input distribution.
Key idea
Probabilistic analysis computes expected behavior by averaging over input or coin flip distributions, using indicator variables and linearity of expectation to sum per event contributions into an expected running time.