Probability and Stochastic Analysis Seminar 

13/10/2020, 14:00 — 15:00 — Room P3.10, Mathematics Building Online
Persi Diaconis, Stanford University

The Mathematics of making a mess (an introduction to random walk on groups)

How many random transpositions does it take to mix up $n$ cards? This is a typical question of random walk on finite groups. The answer is $\frac{1}{2}n \log{n} + Cn$ and there is a sharp phase transition from order to chaos as $C$ varies. The techniques involve Fourier analysis on non-commutative groups (which I will try to explain for non specialists). As you change the group or change the walk, new analytic and algebraic tools are required. The subject has wide applications (people still shuffle cards, but there are applications in physics, chemistry,biology and computer science — even for random transpositions). Extending to compact or more general groups opens up many problems. This was the first problem where the ‘cutoff phenomenon’ was observed and this has become a healthy research area.

See also

Diaconis_notes.pdf