En poursuivant votre navigation sur ce site, vous acceptez l'utilisation d'un simple cookie d'identification. Aucune autre exploitation n'est faite de ce cookie. OK
1

Random walk on random digraph

Sélection Signaler une erreur
Multi angle
Auteurs : Salez, Justin (Auteur de la Conférence)
CIRM (Editeur )

Loading the player...

Résumé : 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.

Codes MSC :
05C80 - Random graphs
60G50 - Sums of independent random variables; random walks
60J10 - Markov chains (discrete-time Markov processes on discrete state spaces)
05C81 - Random walks on graphs

    Informations sur la Vidéo

    Réalisateur : Hennenfent, Guillaume
    Langue : Anglais
    Date de publication : 29/01/16
    Date de captation : 07/01/16
    Sous collection : Research talks
    arXiv category : Combinatorics ; Probability
    Domaine : Combinatorics ; Probability & Statistics
    Format : MP4 (.mp4) - HD
    Durée : 00:59:32
    Download : https://videos.cirm-math.fr/2016-01-07_Salez.mp4

Informations sur la Rencontre

Nom de la rencontre : Spectrum of random graphs / Spectre de graphes aléatoires
Organisateurs de la rencontre : Bordenave, Charles ; Guionnet, Alice ; Virág, Bálint
Dates : 04/01/16 - 08/01/16
Année de la rencontre : 2016
URL Congrès : http://conferences.cirm-math.fr/1186.html

Données de citation

DOI : 10.24350/CIRM.V.18913103
Citer cette vidéo: Salez, Justin (2016). Random walk on random digraph. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.18913103
URI : http://dx.doi.org/10.24350/CIRM.V.18913103

Voir aussi

Bibliographie



Sélection Signaler une erreur