The Optimal Sink and the Best Source in a Markov Chain

Yuri Bakhtin, Leonid Bunimovich

Research output: Contribution to journalArticle

Abstract

It is well known that the distributions of hitting times in Markov chains are quite irregular, unless the limit as time tends to infinity is considered. We show that nevertheless for a typical finite irreducible Markov chain and for nondegenerate initial distributions the tails of the distributions of the hitting times for the states of a Markov chain can be ordered, i.e., they do not overlap after a certain finite moment of time. If one considers instead each state of a Markov chain as a source rather than a sink then again the states can generically be ordered according to their efficiency. The mechanisms underlying these two orderings are essentially different though. Our results can be used, e. g., for a choice of the initial distribution in numerical experiments with the fastest convergence to equilibrium/stationary distribution, for characterization of the elements of a dynamical network according to their ability to absorb and transmit the substance ("information") that is circulated over the network, for determining optimal stopping moments (stopping signals/words) when dealing with sequences of symbols, etc.

Original languageEnglish (US)
Pages (from-to)943-954
Number of pages12
JournalJournal of Statistical Physics
Volume143
Issue number5
DOIs
StatePublished - Jun 2011

Keywords

  • Markov chains
  • Sinks
  • Sources

ASJC Scopus subject areas

  • Statistical and Nonlinear Physics
  • Mathematical Physics

Fingerprint Dive into the research topics of 'The Optimal Sink and the Best Source in a Markov Chain'. Together they form a unique fingerprint.

  • Cite this