Abstract: A finite ergodic Markov chain exhibits cutoff if its distance to equilibrium remains close to its initial value over a certain number of iterations and then abruptly drops to near 0 on a much shorter time scale. Originally discovered in the context of card shuffling (Aldous-Diaconis, 1986), this remarkable phenomenon is now rigorously established for many reversible chains. Here we consider the non-reversible case of random walks on sparse directed graphs, for which even the equilibrium measure is far from being understood. We work under the configuration model, allowing both the in-degrees and the out-degrees to be freely specified. We establish the cutoff phenomenon, determine its precise window and prove that the cutoff profile approaches a universal shape. We also provide a detailed description of the equilibrium measure.
Recording during the thematic meeting: "Spectrum of random graphs" the January 7, 2016 at the Centre International de Rencontres Mathématiques (Marseille, France)
Filmmaker: Guillaume Hennenfent
Find this video and other talks given by worldwide mathematicians on CIRM's Audiovisual Mathematics Library: http://library.cirm-math.fr. And discover all its functionalities:
- Chapter markers and keywords to watch the parts of your choice in the video
- Videos enriched with abstracts, bibliographies, Mathematics Subject Classification
- Multi-criteria search by author, title, tags, mathematical area
Justin Salez : Random walk on random digraph mathematics museum | |
| 4 Likes | 4 Dislikes |
| 299 views views | 10K followers |
| Science & Technology | Upload TimePublished on 3 Feb 2016 |
Không có nhận xét nào:
Đăng nhận xét