Syllabus

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:

1. define total variation distances between probability distributions on the group Zp = {0,1,...,p-1} equipped with addition mod p, calculate and estimate these distances for various distributions in Zp

2. define entropy of probability distributions in Zp, compute and estimate entropy for various examples in Zp and relate entropy to the total variation distance

3. define and compute convolutions of probability distributions on Zp, model random walks as iterated convolutions and estimate probabilities of events using iterated convolutions,

4. define Fourier transforms on the group Zp and estimate Fourier transforms of probability distributions and their convolutions on Zp,

5. prove fundamental theorems in harmonic analysis such as convolution theorem and Plancherel’s theorem in Zp

6. outline the calculations and estimates of finding the total variation distances of convolutions of prob- ability distributions to the uniform distribution in Zp and alter these proofs in other examples with dierent constants or parameters,

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

8. apply the methods presented in the course and prove similar results for analogous contexts such as random walks on higher dimensional lattices (hypercube Zd^2 and the torus Zd^p), matrix groups (GL(Zp)), models for card shuffling in the symmetric group, dice rolling or models for Rubik’s cube scrambling as subgroups of the symmetric group

Credits: 5

Schedule: 11.01.2023 - 23.02.2023

Teacher in charge (valid for whole curriculum period):

Teacher in charge (applies in this implementation): Tuomas Sahlsten

Contact information for the course (applies in this implementation):

CEFR level (valid for whole curriculum period):

Language of instruction and studies (applies in this implementation):

Teaching language: English. Languages of study attainment: English

CONTENT, ASSESSMENT AND WORKLOAD

Content

• valid for whole curriculum period:

  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 Zp, 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.   Detailed contents are listed below:

  Week 1: Introduction, probability measures and information theory on Zp
  - 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 Zp
  - Revision on fundamentals of probability and analysis in the group Zp
  - Probability distributions in distributions in Zp, Lebesgue/Uniform and Dirac/Singular distributions
  - Definition of total variation distance between probability distributions on Zp
  - Entropy of probability distributions in Zp
  - Computing the entropy and total variation distances in Zp, L identity and Pinsker’s inequality

  Week 2: Convolution, additive combinatorics, dynamics and random walks on Zp
  - Definition and heuristics of convolution
  - Sumsets, additive combinatorics and relation to the support of the convolution
  - Realising random walks as iterated convolutions on Zp
  - Transfer operator and entropy growth under convolutions
  - Ergodicity of a random walk in Zp
  - Non-concentration of random walks on subgroups
  - Ergodic theorem

  Week 3: Introduction to Fourier analysis and L2 theory in Zp
  - Mixing of a random walk in Zp
  - Fourier transform in Zp
  - Inverse Fourier transform in Zp
  - Spectral gap of probability distributions
  - Lp norms, inner product and Cauchy-Schwartz inequality

  Week 4: Convolution theorem, L2 theory and long-time asymptotic behaviour of random walks on Zp
  - Convolution theorem in Zp
  - Plancherel theorem in Zp
  - Upper Bound Lemma and Lower Bound Lemma in Zp.
  - Applying the Upper Bound Lemma to prove ergodicity and mixing of a random walk in Zp
  - Applying the Lower Bound Lemma to find spectral gap for random walks in Zp

  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 Zd^2, torus Zd^p and symmetric group S_n
  - Introduction to harmonic analysis / representation theory on finite groups: irreducible representations of G, Schur’s lemma, dual group 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

Assessment Methods and Criteria

• valid for whole curriculum period:

  There are three ways to pass the course, please choose one and only one of them::

  1. Individual written research project on the topics of the course, please discuss with the lecturer on the possible topics and details

  2. Exercises + Final exam with both counting towards final mark

  3. 100% Final exam

DETAILS

Substitutes for Courses

• valid for whole curriculum period:

  Substitutes for Courses

Prerequisites

• valid for whole curriculum period:

  Prerequisites

FURTHER INFORMATION

Further Information

• valid for whole curriculum period:

  Teaching Language : English

  Teaching Period : 2022-2023 Spring III
  2023-2024 No teaching

Description