This course may be available through clearing

If you already have your exam results, meet the entry requirements and hold no offers, then you may be able to apply to this course now.

Contact the admissions team

If you're waiting for your results, then sign up to our clearing alerts to get all the information you need ahead of results day.

Sign up now

MMath Mathematics and Statistics / Course details

Year of entry: 2020

Coronavirus information for applicants and offer-holders

For the latest updates on how coronavirus will affect applicants and offer-holders, you can visit our FAQs.

Read our latest coronavirus information

Holding an offer for 2020 entry? Visit our dedicated offer-holders page.

Information for offer-holders

Course unit details:
Analysis, Random Walks and Groups

Unit code MATH42142
Credit rating 15
Unit level Level 4
Teaching period(s) Semester 2
Offered by Department of Mathematics
Available as a free choice unit? No

Overview

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 S52 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.

Pre/co-requisites

Unit title Unit code Requirement type Description
Real Analysis A MATH20101 Pre-Requisite Compulsory
Complex Analysis MATH20142 Pre-Requisite Compulsory

Aims

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.

Learning outcomes

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

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

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

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

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

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

- outline the calculations and estimates of finding the total variation distances of convolutions of probability distributions to the uniform distribution in ZN 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 Z2d and the torus ZNd), matrix groups (GL(ZN)), models for card shuffling in the symmetric group or models for Rubik's cube scrambling as subgroups of the symmetric group

Syllabus

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

 Discrete circle group ZN (2 lectures)

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

 Convolution of probability distributions on ZN (2 lectures)

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

Measuring randomness on ZN (3 lectures)

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

Introduction to Fourier analysis on ZN (3 lectures)

  • Fourier transform in Z
  • Convolution theorem in ZN
  • L2 theory of Fourier transform: Plancherel theorem in Z

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

  • Concepts from dynamical systems: ergodicity and mixing of the random walk in ZN
  • Concentration of random walks on subgroups of ZN, connection to additive combinatorics in ZN
  • Quantitative rates: Proof of the Upper Bound Lemma by Diaconis and Shashahani in ZN. 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 Z2d, torus ZNd 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

Assessment methods

Method Weight
Other 20%
Written exam 80%

Coursework: Single piece of take-home coursework (weighting within unit 20%).

End of semester examination: duration 3 hours (weighting within unit, 80%).

 

Feedback methods

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.

Recommended reading

[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

Study hours

Scheduled activity hours
Lectures 24
Tutorials 12
Independent study hours
Independent study 117

Teaching staff

Staff member Role
Tuomas Sahlsten Unit coordinator

Return to course details