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.
Similar content being viewed by others
References
Bhakta, P., Miracle, S., Randall, D., Streib, A.P.: Mixing times of markov chains for self-organizing lists and biased permutations. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1–15. SIAM (2013)
Guruswami, V.: Rapidly mixing markov chains: a comparison of techniques. http://cs.washington.edu/homes/venkat/pubs/papers.html (2000)
Gómez-Gardeñes, J., Latora, V.: Entropy rate of diffusion processes on complex networks. Phys. Rev. E 78(6), 065102 (2008)
Ochab, J.K.: Static and dynamic properties of selected stochastic processes on complex networks. PhD thesis, Institute of Physics (2013)
Burda, Z., Duda, J., Luck, J.M., Waclaw, B.: Localization of the maximal entropy random walk. Phys. Rev. Lett. 102(16), 160602 (2009)
Billingsley, P.: Ergodic Theory and Information. Wiley, New York (1965)
Boyd, Stephen, Diaconis, Persi, Xiao, Lin: Fastest mixing markov chain on a graph. SIAM Rev. 46(4), 667–689 (2004)
Bremaud, P.: Markov Chains: Gibbs fields, Monte Carlo Simulation, and Queues, vol. 31. Springer, New York (1999)
Dixit, P.D., Dill, K.A.: Inferring microscopic kinetic rates from stationary state distributions. J. Chem. Theory Comput. 10(8), 3002–3005 (2014)
Dixit, P.D., Jain, A., Stock, G., Dill, K.A.: Inferring transition rates of networks from populations in continuous-time markov processes. J. Chem. TheoryComput. 11(11), 5464–5472 (2015)
Monthus, C.: Non-equilibrium steady states: maximization of the Shannon entropy associated with the distribution of dynamical trajectories in the presence of constraints. J. Stat. Mech. 2011, P03008 (2011)
Mihelich, Martin, Dubrulle, Bérengère, Paillard, Didier, Herbert, Corentin: Maximum entropy production versus kolmogorov-sinai entropy in a constrained asep model. Entropy 16(2), 1037–1046 (2014)
Acknowledgements
Martin Mihelich thanks IDEEX Paris-Saclay for financial support. Quentin Kral was supported by the French National Research Agency (ANR) through contract ANR-2010 BLAN-0505-01 (EXOZODI).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Mihelich, M., Dubrulle, B., Paillard, D. et al. Maximum Kolmogorov-Sinai Entropy Versus Minimum Mixing Time in Markov Chains. J Stat Phys 170, 62–68 (2018). https://doi.org/10.1007/s10955-017-1874-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10955-017-1874-z