Maximum Kolmogorov-Sinai Entropy Versus Minimum Mixing Time in Markov Chains

Martin Mihelich (1) , Bérengère Dubrulle (1) , Didier Paillard (2, 3) , Quentin Kral (4, 5) , Davide Faranda (2, 6)

1 SPHYNX - Systèmes Physiques Hors-équilibre, hYdrodynamique, éNergie et compleXes
2 LSCE - Laboratoire des Sciences du Climat et de l'Environnement [Gif-sur-Yvette]
3 CLIM - Modélisation du climat
4 LESIA (UMR_8109) - Laboratoire d'études spatiales et d'instrumentation en astrophysique
5 Institute of Astronomy [Cambridge]
6 ESTIMR - Extrèmes : Statistiques, Impacts et Régionalisation

We establish a link between the maximization of Kolmogorov Sinai entropy (KSE) and the minimization of the mixing time for general Markov chains. Since the maximisation of KSE is analytical and easier to compute in general than mixing time, this link provides a new faster method to approximate the minimum mixing time dynamics. It could be interesting in computer sciences and statistical physics, for computations that use random walks on graphs that can be represented as Markov chains.

Keywords: Entropy; Markov chain; Mixing time

Domains: Physics [physics]

Martin Mihelich, Bérengère Dubrulle, Didier Paillard, Quentin Kral, Davide Faranda. Maximum Kolmogorov-Sinai Entropy Versus Minimum Mixing Time in Markov Chains. Journal of Statistical Physics, 2018, 170, pp.62 - 68. ⟨10.1007/s10955-017-1874-z⟩. ⟨cea-01687782⟩