Spring 2019

Analysis, Random Walks and Groups
Undergraduate course offered in the School of Mathematics, University of Manchester

How many times should we shuffle a deck of 52 cards to make it “sufficiently random’’? What types of shuffling work best? These questions can be answered by realising the card shuffling as a random walk on the symmetric group $$S_{52}$$ of 52 elements and employing fundamental tools from Harmonic Analysis to compute the answers. In the case of riffle shuffles the surprising answer is that after roughly 6 shuffles the deck will still be quite ordered, but at the 7th shuffle the deck suddenly becomes very random. Similar ideas can also be realised when scrambling a Rubik’s Cube and asking how “random’’ the scramble is.

The topics of the course form an introduction to a currently a very exciting and emerging field, using ideas involving the combinatorial properties of groups, analysis and probability theory. The course starts with the basics by reviewing first year probability notions and introducing probabilistic tools such as convolution, which are natural in the context of groups. For simplicity we will first concentrate on the circle group $$\mathbb{Z}_p$$ of $$p$$ elements, but many of the core ideas are similar in more complicated groups such as the symmetric group. We will introduce fundamental topics from Harmonic Analysis such as Fourier transform and demonstrate how they can be applied here.

Based on the books: