ICM 1998, Berlin, Aug. 18–27

Abstracts of Plenary and Invited Lectures

Section:

0. Plenary Lectures

1991 MS Classification: Persi Diaconis, Department of Mathematics and ORIE, Cornell University; Departments of Mathematics and Statistics, Stanford University, USA From Shuffling Cards to Walking Around the Building

There has been spectacular progress in recent years in deriving sharp rates of convergence of Markov chains to their stationary distribution. A typical problem: How many times should a deck of cards be shuffled to mix it? The answer depends on how the cards are shuffled. For the usual method of riffle shuffling 52 cards, the answer is “about seven”. This is work of Gilbert, Shannon, Reeds, Aldous, Bayer and Diaconis. The analysis shows a sharp threshold in convergence; for n cards \frac{3}{2} log_{2} n shuffles are necessary and suffice. The analysis rests on an algebraic miracle which has ramifications in algebraic combinatorics (descent theory for Coxeter groups) and in giving Hodge type decompositions for Hochschild homology. In very recent work, Bidigare, Hanlon and Rockmore have found an elegant generalization of shuffling to random walk on the chambers of Euclidean hyperplane arrangements. This has been abstracted further to natural walks on buildings in joint work with Ken Brown. These generalizations illuminate the algebraic miracle and permit sharp analysis of a host of natural new Markov chains. Perhaps the most interesting of these is chains arising in random tiling models for quasi crystals (work with Billera and Brown).

ICM 1998 Berlin · Plenary and Invited Lectures