The Unreasonable Effectiveness of Martingales
I
will illustrate the effectiveness of Martingales and stopping times
with four examples, involving waiting times for patterns in coin tossing,
random graphs, mixing of random walks, and metric space embedding. A common
theme is the way stopping time arguments often circumvent the wasteful "union
bound" (bounding of the probability of a union by the sum of the individual
probabilities).
Yuval Peres, Microsoft Research