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

Abstract: 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.

analysis of PDEscombinatoricsprobability

Audience: researchers in the topic

( video )

Probability and Stochastic Analysis at Tecnico Lisboa

Series comments: To receive the series announcements, please register in math.tecnico.ulisboa.pt/seminars/ps/index.php?action=subscribe#subscribe