TIME: 1:30 -- 2:30 pm, Tuesday, Feb 10, 2009

SPECIAL PLACE: Gates Commons (6th floor of CSE Building)

SPEAKER: Yuval Peres, Microsoft Research 

TITLE: The Unreasonable Effectiveness of Martingales

ABSTRACT:

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).