MS-E1370 - Analysis, Random Walks and Groups, Luento-opetus, 10.1.2023-23.2.2023

Topic outline

• Select topic General

  General
  • Select activity Welcome to Analysis, Random Walks and Groups! How ...

    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
    • Mixing of a random walk in $\mathbb{Z}_p$

    Week 3: Introduction to harmonic analysis and $L^2$ theory 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
    • Convolution theorem in $\mathbb{Z}_p$ 
    • Plancherel theorem in $\mathbb{Z}_p$

    Week 4: Applications to long-time asymptotic behaviour of random walks on $\mathbb{Z}_p$ and moving to extend the theory to general finite groups

    • 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$
    • 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$
    • Basics on representation theory on finite groups: irreducible representations of $G$, morphisms of representations and the dual group $\widehat{G}$

    Week 5: Harmonic analysis and representation theory on finite groups $G$

    • Fourier transforms in $G$ using irreducible representations
    • Character theory in $G$ and relation to conjugate classes
    • Hilbert-Schmidt inner products and norms
    • Trace lemma and Fourier inversion in $G$
    • Plancherel’s theorem in $G$ and its proof

    
    

    Week 6: Applications to mixing times in models of dice rolling and card shuffling, and brief introduction to random walks on continuous groups (e.g circle, matrix groups)
    

    • Upper Bound Lemma in $G$ and its proof
    • Modeling dice rolling as a random walk on the symmetric group and applying upper bound lemma with the character tables to bound mixing times
      
    • 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
    • If time permits, the demonstration 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- and Haar measures, and Erdös-Turán inequality having applications to equidistribution of random back- and forth rotations generated by badly approximable numbers in metric number theory
      

    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:

    1. 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$
    2. 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
    3. 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,
    4. define Fourier transforms on the group $\mathbb{Z}_p$ and estimate Fourier transforms of probability distributions and their convolutions on $\mathbb{Z}_p$,
    5. prove fundamental theorems in harmonic analysis such as convolution theorem and Plancherel’s theorem in $\mathbb{Z}_p$
    6. 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,
    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 (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 and let the TA (Kai Hippi, kai.hippi@aalto.fi) know which one you want to do on the first week of the course. This will help us to know how many scripts we will expect for marking for the exercise points and how many will attend the final exam:

    1. Individual written research project on the topics of the course, please discuss with the lecturer on the possible topics and details, here is a list of some potential projects. This will be around 10 pages long document, on some topic related to the course. Also, If you got some topic related to the course also in mind, you can let me know and I can consider if this could be considered for marks.
    2. Weekly exercises (100% of the grade comes from these). There will be in total 5 sets of exercises, and each exercise sheet will have two types of exercises: (1) 1-2 homework exercises that are returned for marking and (2) 2-3 further exercises that will be discussed in the tutorial. The first exercise set is released on the first week, and there will not be tutorial on the first week, the tutorial begins on the second week of the course. The way you get marks comes from homework marks (weight 75%) and attendance marks (weight 25%). The way you get the homework marks is that you return to the TA (Kai Hippi) your solutions to the homework exercises every week for marking (Kai Hippi will set the way this is returned, it will be in person to a locker, and the deadline is Tuesday in the tutorial (14:15 on Tuesdays): so for Week 1 sheet, the deadline is on Tuesday tutorial the Week 2 and so on. If you cannot return the solutions in-person, which Kai prefers, email Kai on possible alternatives). This will award you a maximum of 75% of the marks. Then attending the tutorial for an attendance mark which in total is 25% (5% for each attendance). If you cannot attend the tutorial, but want to do the attendance marks, you can return before the tutorial your attempts of the further exercises that are discussed in the tutorial to Kai. Here Kai will not mark the further exercises, but will look if an attempt has been made and awards the attendance mark.
    3. Final exam (100% of the grade comes from this)

    
    

    Contact:

    The lecturer of the course is Tuomas Sahlsten (tuomas.sahlsten 'at' aalto.fi) and the Teaching Assistant is Kai Hippi (kai.hippi 'at' aalto.fi). If there are matters related to Sisu, research project, exam or lectures, contact Tuomas. In case of tutorial related questions (e.g. you cannot make it, or you need to return your further exercises solutions, or other questions), contact the TA Kai. On mathematical questions both of us can answer to questions you may have.
    

  • Select activity Announcements

    

    Announcements Forum