Velocity formulae between entropy and hitting time for Markov chains

DOI10.1016/J.SPL.2018.05.026MaRDI QIDQ722658zbMATH OpenOpenAlexWikidataFDO

Authors Michael C. H. Choi

Publication date 27 July 2018

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

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

zbMATH Keywords

entropyrandom walkhitting timecommute timeeigentime

Mathematics Subject Classification ID

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

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.

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

Cites work

• Eigentime identity for asymmetric finite Markov chains
• Elements of Information Theory
• Logarithmic Sobolev inequalities for finite Markov chains
• Maximum entropy mixing time of circulant Markov processes
• The Entropy of Conditional Markov Trajectories
• The entropy of 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)