Università degli Studi di Padova

“Mixing times and cutoffs for Markov chains”

Thursday 6 February 2025 h. 14:30 - Room 2BC30 - Giacomo Passuello (Padova, Dip. Mat.)

Abstract

How long does it take to shuffle a deck of 40 cards? This simple question, together with the seminal work of Aldous and Diaconis on the cutoff phenomenon, has generated, in the last 40 years, a rich research area in the field of discrete probability.

A cutoff is a dynamical phase transition for a random process, which appears as the size of the system becomes large. It occurs when the distance to equilibrium of the process abruptly drops from its maximum value to zero at a critical time scale.

Establishing the occurrence of the cutoff is a delicate matter, which may require a precise understanding of the spectral and diffusive properties of the underlying system.

In this talk, I will review some basic concepts on Markov chains and their convergence to the stationary equilibrium. After that, I will introduce the concept of mixing time and discuss bounds on its limiting behaviour. Finally, I will focus on the cutoff phenomenon and present some results on the mixing time of the simple random walk on a directed random graph.


The video of the seminar will appear shortly afterwards in this Mediaspace channel.


Seminario Dottorato