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

Donate · Contact Us · Site Map · Join SIAM · My Account