Velocity formulae between entropy and hitting time for Markov chains

DOI10.1016/J.SPL.2018.05.026zbMATH Open1395.60077arXiv1805.02162OpenAlexW2802485683WikidataQ129729565 ScholiaQ129729565MaRDI QIDQ722658FDOQ722658

Authors: Michael C. H. Choi 

Publication date: 27 July 2018

Published in: Statistics \& Probability Letters (Search for Journal in Brave)

Abstract: In the absence of acceleration, the velocity formula gives "distance travelled equals speed multiplied by time". For a broad class of Markov chains such as circulant Markov chains or random walk on complete graphs, we prove a probabilistic analogue of the velocity formula between entropy and hitting time, where distance is the entropy of the Markov trajectories from state $i$ to state $j$ in the sense of [L. Ekroot and T. M. Cover. The entropy of Markov trajectories. IEEE Trans. Inform. Theory 39(4): 1418-1421.], speed is the classical entropy rate of the chain, and the time variable is the expected hitting time between $i$ and $j$. This motivates us to define new entropic counterparts of various hitting time parameters such as average hitting time or commute time, and prove analogous velocity formulae and estimates between these quantities.

Full work available at URL: https://arxiv.org/abs/1805.02162

Recommendations

• The entropy of Markov trajectories
• Trajectorial dissipation and gradient flow for the relative entropy in Markov chains
• Sum rules for hitting times of Markov chains
• Variational principles of hitting times for non-reversible Markov chains
• On the entropy for semi-Markov processes

zbMATH Keywords

entropyrandom walkhitting timecommute timeeigentime

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Cites Work

• Elements of Information Theory
• Logarithmic Sobolev inequalities for finite Markov chains
• Maximum entropy mixing time of circulant Markov processes
• Eigentime identity for asymmetric finite Markov chains
• The entropy of Markov trajectories
• The Entropy of Conditional Markov Trajectories

This page was built for publication: Velocity formulae between entropy and hitting time for Markov chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q722658)