University of Cambridge > Talks.cam > Junior Algebra/Logic/Number Theory seminar > Random Walks on Groups: Shuffling Cards and the Cutoff Phenomenon

Random Walks on Groups: Shuffling Cards and the Cutoff Phenomenon

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

  • UserOliver Matheau-Raven, University of York
  • ClockFriday 18 October 2019, 15:00-16:00
  • HouseCMS, 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/Logic/Number Theory seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2019 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity