Random Walks on Groups: Shuffling Cards and the Cutoff Phenomenon

Add to your list(s) Download to your calendar using vCal

• Oliver Matheau-Raven, University of York
• Friday 18 October 2019, 15:00-16:00
• CMS, MR9.

If you have a question about this talk, please contact Liam Jolliffe.

Random walks on Groups is an area of mathematics that has flourished since the 80s with beautiful connections between algebra and probability being discovered. In this talk we present an overview of the techniques that enable the use of irreducible representations of a group G to study the convergence time of random walks on G to the uniform distribution. This convergence often becomes sharp if we consider a family of random walks on G_n where |G_n| tends to infinity as n tends to infinity, we call this the cutoff phenomenon. We specialise to two examples of random walks on S_n; the random transpositions shuffle, and the one-sided transposition shuffle. The random transposition shuffle is defined by our hands independently choosing cards each to transpose every step. The one-sided transposition shuffle restricts our hands to cross each other when choosing cards. The former is a classical problem studied by Diaconis and Shahshahani, who proved it exhibits a cutoff at time (n/2)log(n). The latter is a recent problem, and in joint work with Michael Bate and Stephen Connor we uncovered a remarkable branching structure for the eigenspaces involving Young diagrams and paths between them. After analysis of the eigenvalues we prove a cutoff at time (n)log(n).

This talk is part of the Junior Algebra and Number Theory seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• CMS, MR9
• DPMMS Lists
• DPMMS Pure Maths Seminar
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• Junior Algebra and Number Theory seminar
• School of Physical Sciences
• bld31
• ndb35's list

Note that ex-directory lists are not shown.