 ## Welcome

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

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.

If you have any questions do not hesitate in contacting me:

## Where to find course information

On the Course Information page you will find important information about this course including: course learning outcomes and details of the course syllabus. In addition you will want to read Succeeding in this Course Unit, also in the Course Information section.

Your course assessment information will appear on the Assessment & Feedback page where you will also find details here of what feedback you will receive during the course, when you will receive it and how it can help in your future assessment tasks.

Course materials and resources can be found below.

## Lectures and tutorials

The lectures and tutorials will take place in the University Place Room 3.214.

• The lectures will be held on every Thursday at 3-4 pm and every Friday 10-11 am.

• The tutorial of the course will be on every Friday at 9-10 am starting on the 2nd week.
There will be no lectures or tutorials during the easter holiday period April 8 - April 28.2019.

## Lecture material

The lectures follows the lecture notes below:

These notes should be the complete version but throughout the lectures if any mistakes/errors are spotted we will update the file above. Please let me know if you spot anything by emailing to tuomas.sahlsten@manchester.ac.uk and the mistake will be addressed.

## Lecture schedule

Topics through the lectures and what we aim to go through:

• Week 1: Introduction, Card shuffling and Rubik's cube

• Week 2: Pass the broccoli, group Z_p and probability distributions on Z_p

• Week 3: Total variation distance and entropy

• Week 4: Convolution and sumsets

• Week 5: Ergodicity, concentration on subgroups and mixing

• Week 6: Fourier transform in Z_p

• Week 7: L^2 theory and convolution theorem for Fourier transform, Bounding distance to uniform using harmonic analysis (Upper Bound Lemma)

• Week 8: Explicit computations of the mixing time using the Upper Bound Lemma using spectral gap, starting theory of random walks on general finite groups. Beginning harmonic analysis on the examples Z_2^p and Z_d^p

• Week 9: More on the random walks on general finite groups, difficulties with the non-Abelian case. Developing harmonic analysis in Z_2^d (Plancherel's theorem) and proving mixing time results for Z_2^d (Upper Bound Lemma in Z_2^d). Interpretation of these using the Ehrenfest Urn model.

• Week 10: Random walks on the symmetric group and back to card shuffling examples. Applying the general group formalism in the symmetric group to connect mixing time to ``sufficiently random'' order of cards

• Week 11: Overview of the general methods presented in the course and how to apply them beyond the examples presented here

• Week 12: Revision for the final exam

## Tutorial schedule

We will have a weekly tutorial on every Friday next to the lecture. The first tutorial is on Friday 8.2.2019. They provide an opportunity to discuss about the content of the course and we will try to go together some exercises during them. Any exercises or material gone through the tutorials will be posted here.

• 8.2.2019: Modeling a `weak' Borel shuffle as a random permutation, Exercises and solutions (pdf)

• 15.2.2019: Examples of computing probabilities of simple events and integrals, Exercises and solutions (pdf).

• 22.2.2019: Total variation distance, Exercises and solutions (pdf).

• 1.3.2019: Convolution and entropy, Exercises (pdf), Solutions (pdf).

• 8.3.2019: Dynamics, ergodic theory and concentration on subgroups, Exercises (pdf), Solutions (pdf).

• 15.3.2019: Fourier transform, Exercises (pdf), Solutions (pdf).

• 22.3.2019: Applying Fourier series, the convolution theorem, Plancherel's theorem and Cauchy-Schwartz, Exercises (pdf), Solutions (pdf).

• 29.3.2019: Applying Upper Bound Lemma to mixing time, Exercises (pdf) , Solutions (pdf).

• 5.4.2019: Modeling card shuffling using the convolution notation, proofs in the group Z_2^d, Exercises (pdf) , Solutions (pdf).

• 3.5.2019: Dynamics of random walks on general groups

• 10.5.2019: Revision
It is highly recommended that you attend the tutorials as they can provide extra examples and strategies for proofs not found in the lecture notes.