MMath Mathematics / Course details

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₅₂ 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. Hence the course suits well for anyone with any interest to any of these topics even if weaker in the others. We will revise all the topics in the beginning of the course.

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 cyclic group Z__N, 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.

As prerequisites it helps to be comfortable with probabilistic language of “probability of an event’’, “expectation’’, “independence’’, which are presented in the first year probability course, but we will revise these notions in the beginning. On group theory it helps to be familiar with basic examples such as the symmetric group. From analysis it helps to be comfortable with complex numbers and sequences and series.

The course will show how fundamental concepts and tools from analysis, probability and algebra can be used together to describe long-time asymptotic behaviour of random walks on groups.

On successful completion of this course unit students will be able to: 

- define total variation distances between probability distributions on the group Z_N, calculate and estimate these distances for various distributions in Z_N

- define entropy of probability distributions in Z_N, compute and estimate entropy for various examples in Z_N and relate entropy to the total variation distance

- define and compute convolutions of probability distributions on Z_N, model random walks as iterated convolutions and estimate probabilities of events using iterated convolutions,

- define Fourier transforms on the group Z_N and estimate Fourier transforms of probability distributions and their convolutions on Z_N,

- prove fundamental theorems in harmonic analysis such as convolution theorem and Plancherel’s theorem in Z_N

- outline the calculations and estimates of finding the total variation distances of convolutions of probability distributions to the uniform distribution in Z_N and alter these proofs in other examples with different constants or parameters,

- explain the key ideas of the theorems and methods presented in the course and describe how each component (harmonic analysis, random walks and group theory) come into play,

- apply the methods presented in the course and prove similar results for analogous contexts such as random walks on higher dimensional lattices (hypercube Z₂^d and the torus Z_N^d), matrix groups (GL(Z_N)), models for card shuffling in the symmetric group or models for Rubik's cube scrambling as subgroups of the symmetric group

Introduction to natural models for random walks on groups such as card shuffles, Rubik’s cube and Ehrenfest Urn (2 lectures)

 Discrete circle group Z_N (2 lectures)

• Revision on fundamentals of group theory in the group Z_N
• Revision on fundamentals of probability and analysis in the group Z_N
• Probability distributions in distributions in Z_N, Lebesgue/Uniform and Dirac/Singular distributions

 Convolution of probability distributions on Z_N (2 lectures)

• Definition and heuristics of convolution
• Realising random walks as iterated convolutions on Z_N

Measuring randomness on Z_N (3 lectures)

• Definition of total variation distance between probability distributions on Z_N
• Entropy of probability distributions in Z_N
• Computing the entropy and total variation distances in Z_N, L¹ identity and Pinsker’s inequality

Introduction to Fourier analysis on Z_N (3 lectures)

• Fourier transform in Z_N 
• Convolution theorem in Z_N
• L² theory of Fourier transform: Plancherel theorem in Z_N 

Long-time asymptotic behaviour of random walks on Z_N (6 lectures)

• Concepts from dynamical systems: ergodicity and mixing of the random walk in Z_N
• Concentration of random walks on subgroups of Z_N, connection to additive combinatorics in Z_N
• Quantitative rates: Proof of the Upper Bound Lemma by Diaconis and Shashahani in Z_N. The result applies Fourier analysis to compute upper bounds of the distance to the uniform distribution on groups
• Applying the Upper Bound Lemma to prove ergodicity of a random walk in Z__N when there is a spectral gap
• Applying the Upper Bound Lemma to find explicit mixing times of random walks in Z__N

Extending the ideas to general groups (6 lecture)

• Showing how probability distributions, total variation distance, convolution and random walks can all be done with same proofs in general finite groups such as the hypercube Z₂^d, torus Z_N^d and symmetric group
• Introduction to harmonic analysis on finite groups (representation theory), applying harmonic analysis to prove the Upper Bound Lemma in general finite groups
• Applying the ideas to give explicit mixing times for random walks in the symmetric group
• Modelling card shuffling as a random walk on the symmetric group such as random transpositions, Borel’s shuffles, riffle shuffles, overhand shuffles and using the mixing times to find the number of shuffles it takes to mix a deck

Coursework: Single piece of take-home coursework weighting 20%.

End of semester examination: weighting 80%.

 

Weekly tutorials will provide an opportunity for students’ work to be discussed and provide feedback on their understanding. If necessary, couple of the tutorials might be used as lectures.

[1] core (beginning on the easy parts): P. Diaconis: Group Representations in Probability and Statistics, IMS Lecture Series volume 11, Institute of Mathematical Statistics, Hayward, California, 1988
[2] further: D. Bayer, P. Diaconis: Trailing the dovetail shuffle to its lair. Ann. Probab., 2, 294-313,1992.
[3] essential (beginning on the easier parts): F. Ceccherini-Silberstein, T. Scarabotti, F. Tolli: Harmonic Analysis on Finite Groups. Cambridge University Press, 2008.
[4] further: R. Lyons, Y. Peres: Probability on Trees and Networks, Cambridge Series in Statistical and Probabilistic Mathematics, 2017
[5] recommended: E. M. Stein, R. Shakarchi: Fourier Analysis: An Introduction, Princeton Lectures in Analysis, 2011
[6] further: T. Tao, V. Vu: Additive Combinatorics, Cambridge university Press, 2006
[7] further: P. Walters: An Introduction to Ergodic Theory, Springer, 1982

This course unit detail provides the framework for delivery in 20/21 and may be subject to change due to any additional Covid-19 impact.  

Please see Blackboard / course unit related emails for any further update.