### General

### Welcome to Analysis, Random Walks and Groups!

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 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! How about what are the typical transmutation sequences that transform the genome of a human’s X chromosome into that of a mouse? Moreover, 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, dynamical systems and probability theory. The course has interest from both real world perspective but also in modern pure mathematics research (harmonic analysis and connections to mixing rates of of dynamical systems, random walks and representation theory on groups, modeling chaos theory in quantum mechanics, fractal geometry, etc.). The course suits well for anyone with any interest to analysis, probability or algebra 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 circle group \(\mathbb{Z}_p\), 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.

### Course Schedule:

Week 1:

**Introduction, probability measures and information theory on \(\mathbb{Z}_p\)**- Introduction to natural models for random walks on groups such as card shuffles, Rubik’s cube, dice rolling, random mutations of genes and the Ehrenfest Urn model in statistical mechanics
- Revision on fundamentals of group theory in the group \(\mathbb{Z}_p\)
- Revision on fundamentals of probability and analysis in the group \(\mathbb{Z}_p\)
- Probability distributions in distributions in \(\mathbb{Z}_p\), Lebesgue/Uniform and Dirac/Singular distributions
- Definition of total variation distance between probability distributions on \(\mathbb{Z}_p\)
- Entropy of probability distributions in \(\mathbb{Z}_p\)
- Computing the entropy and total variation distances in \(\mathbb{Z}_p\), \(L^1\) identity and Pinsker’s inequality

Week 2:

**Convolution, additive combinatorics, dynamics and random walks on \(\mathbb{Z}_p\)**- Definition and heuristics of convolution
- Sumsets, additive combinatorics and relation to the support of the convolution
- Realising random walks as iterated convolutions on \(\mathbb{Z}_p\)
- Transfer operator and entropy growth under convolutions
- Ergodicity of a random walk in \(\mathbb{Z}_p\)
- Non-concentration of random walks on subgroups
- Ergodic theorem

Week 3:

**Introduction to harmonic analysis and \(L^2\) theory in \(\mathbb{Z}_p\)**- Mixing of a random walk in \(\mathbb{Z}_p\)
- Fourier transform in \(\mathbb{Z}_p\)
- Inverse Fourier transform in \(\mathbb{Z}_p\)
- Spectral gap of probability distributions
- \(L^p\) norms, inner product, Cauchy-Schwartz and Hölder inequalities

Week 4:

**Convolution theorem, \(L^2\) theory and long-time asymptotic behaviour of random walks on \(\mathbb{Z}_p\)**- Convolution theorem in \(\mathbb{Z}_p\)
- Plancherel theorem in \(\mathbb{Z}_p\)
- Upper Bound Lemma and Lower Bound Lemma in \(\mathbb{Z}_p\)
- Applying the Upper Bound Lemma to prove ergodicity and mixing of a random walk in \(\mathbb{Z}_p\)
- Applying the Lower Bound Lemma to find spectral gap for random walks in \(\mathbb{Z}_p\)

Weeks 5-6:

**Extending the ideas to general finite groups \(G\) and applications**- Examining how probability distributions, total variation distance, convolution and random walks can all be defined and analysed with same proofs in general finite groups G such as the hypercube \(\mathbb{Z}_p^2\), torus \(\mathbb{Z}_p^d\) and symmetric group \(S_n\)
- Introduction to harmonic analysis / representation theory on finite groups: irreducible representations of \(G\) Schur’s lemma, dual group \(\widehat{G}\), Hilbert-Schmidt inner products and Plancherel’s theorem in \(G\)
- Upper Bound Lemma in \(G\) and its proof
- 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 Upper Bound Lemma for \(G = S_{52}\) to establish mixing of random transposition shuffles to find the number of shuffles it takes to mix a deck to be sufficiently random
- How to extend the ideas presented here to
**continuous**groups (e.g. unit circle \(\mathbb{S}^1=\mathbb{R}/\mathbb{Z}\)) leading to introduction to Lebesgue measures and Haar measures, and Erdös-Turán inequality

### Intended Learning Outcomes

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 \(\mathbb{Z}_p = \{0,1,...,p-1\}\) equipped with addition \(\mod p\), calculate and estimate these distances for various distributions in \(\mathbb{Z}_p\)
- define entropy of probability distributions in \(\mathbb{Z}_p\), compute and estimate entropy for various examples in \(\mathbb{Z}_p\) and relate entropy to the total variation distance
- define and compute convolutions of probability distributions on \(\mathbb{Z}_p\), model random walks as iterated convolutions and estimate probabilities of events using iterated convolutions,
- define Fourier transforms on the group \(\mathbb{Z}_p\) and estimate Fourier transforms of probability distributions and their convolutions on \(\mathbb{Z}_p\),
- prove fundamental theorems in harmonic analysis such as convolution theorem and Plancherel’s theorem in \(\mathbb{Z}_p\)
- outline the calculations and estimates of finding the total variation distances of convolutions of probability distributions to the uniform distribution in \(\mathbb{Z}_p\) 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 (the torus \(\mathbb{Z}_p^d\), matrix groups \(\mathrm{GL}(\mathbb{Z}_p)\), models for card shuffling in the symmetric group, dice rolling or models for Rubik’s cube scrambling as subgroups of the symmetric group

### Pre- and co-requisites

The purpose of the course is to be available to wider mathematical audience and thus the course does not assume much prerequisites. The completion of the courses MS-A01xx Differential and integral calculus 1, MS-A050x First Course in Probability and Statistics, MS-C1342 Linear algebra is sufficient. The following courses are also recommended and could help with the understanding but are not at all necessary: MS-C1081 Abstract Algebra, MS-C1541 Metric Spaces, MS-C2111 Stochastic Processes. We plan to introduce and revise any ideas and tools we use in the course.

### Study methods

Lectures and/or recorded videos, self-study (see Materials section) and exercise sessions (see Exercises section)

### Assessment:

There are three ways to pass the course,

**please choose one and only one of them:**- Individual written research project on the topics of the course, please discuss with the lecturer on the possible topics and details
- Weekly exercises (100% of the grade comes from these)
- Final exam (100% of the grade comes from this)

- Introduction to natural models for random walks on groups such as card shuffles, Rubik’s cube, dice rolling, random mutations of genes and the Ehrenfest Urn model in statistical mechanics