Fenómenos de umbral en cadenas de Markov: dos ejemplos

Abstract

Una cadena de Markov es un proceso temporal aleatorio sin memoria. Es sabido que toda cadena de Markov irreducible y aperiódica en un conjunto finito tiene una única distribución estacionaria, a la cual converge cuando el tiempo tiende a infinito sea cual sea la distribución de probabilidad inicial. El comportamiento asintótico de la cadena frecuentemente presenta un fenómeno de umbral: existe un valor concreto del tiempo en el cual la distribución de probabilidad pasa bruscamente de estar alejada de la estacionaria a ser prácticamente la estacionaria. En este trabajo se introducen los conceptos básicos de cadenas de Markov y fenómenos de umbral y se estudian dos ejemplos de fenómenos de umbral en paseos aleatorios en grafos: paseos perezosos con sesgo en una cadena finita, y paseos en el modelo de configuración para grafos dirigidos.

A Markov chain is a random time process without memory. It is known that any irreducible and aperiodic Markov chain on a finite set has a unique stationary distribution, to which it converges when time tends to infinity whatever the initial probability distribution. The asymptotic behaviour of the chain frequently exhibits a cutoff phenomenon: there is a particular value of time at which the probability distribution abruptly changes from being far from stationary to being almost stationary. This paper introduces the basic concepts of Markov chains and cutoff phenomena and studies two examples of cutoff phenomena in random paths in graphs: lazy paths with laziness in a finite chain, and paths in the configuration model for directed graphs.