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

Martin Mihelich 1, * Bérengère Dubrulle 1 Didier Paillard 2 Quentin Kral 3, 4 Davide Faranda 2
* Corresponding author
1 SPHYNX - Systèmes Physiques Hors-équilibre, hYdrodynamique, éNergie et compleXes
SPEC - UMR3680 - Service de physique de l'état condensé, IRAMIS - Institut Rayonnement Matière de Saclay
2 LSCE - Laboratoire des Sciences du Climat et de l'Environnement [Gif-sur-Yvette]
3 LESIA - Laboratoire d'études spatiales et d'instrumentation en astrophysique
4 Institute of Astronomy [Cambridge]
Abstract : 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 : Mixing time Markov chain Entropy
Document type :
Journal articles
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download
https://hal-cea.archives-ouvertes.fr/cea-01687782
Contributor : Dominique Girard <>
Submitted on : Thursday, January 18, 2018 - 5:24:40 PM
Last modification on : Wednesday, May 15, 2019 - 3:57:49 AM
Long-term archiving on : Thursday, May 24, 2018 - 1:10:05 AM

File

1706.00930.pdf
Publisher files allowed on an open archive

Identifiers

Collections

CEA | OBSPM | DSM-IRAMIS | DSM-LSCE | UVSQ | IRAMIS-SPEC | LSCE | PSL | INSU | UNIV-PARIS-SACLAY | CEA-DRF | CEA-UPSAY | SORBONNE-UNIVERSITE | LESIA | UNIV-PARIS7 | USPC | SU-SCIENCES

Citation

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, Springer Verlag, 2018, 170, pp.62 - 68. ⟨10.1007/s10955-017-1874-z⟩. ⟨cea-01687782⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

402

Files downloads

125

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD