0

Is there a special name (or case) for a finite Markov chain which all states are reachable from any state with positive probability? Does anyone familiar with a problem modeled by this kind of chain?

ori
  • 105
  • 2
    Reachable in one step: Markov chain on the complete graph. Reachable in one or several steps: irreducible Markov chain. – Did Aug 20 '13 at 08:35
  • thanks for the answer, I wrote a comment to the first answer... – ori Aug 20 '13 at 11:53
  • 1
    To answer the question in your comment: every stationary distribution corresponds to some transition matrices with positive entries. Conversely, no information about the stationary distribution can follow from the hypothesis that the transition matrix has only positive entries. – Did Aug 20 '13 at 12:04

1 Answers1

0

To elaborate on what @Did already said, I think you are referring to the reducibility or regularity property of a Markov chain. For the definitions, see the Wikipedia article on Markov chains or chapter 11 section 3 of Grinstead and Snell's Introduction to Probability. Another closely related property is connectedness in graph theory.

Markov chains of this type are very important (specifically when they do not contain temporal cycles i.e. aperiodic) for thermodynamics and the Ergodic Hypothesis. The chain isn't irreducible unless it aperiodic in addition to all states being mutually reachable. If all states can be visited then the time average is equal to an ensemble average of microstates in equilibrium allowing for the powerful idea of statistical ensembles to become useful.

If all states are reachable (and aperiodic), it also allows for important analytic statements to be made, most importantly, the Perron-Frobenius theorem.

If you mean a Markov chain that is 1-step connected, then one can think of the Markov chain of biased dice. Another application area where 1-step connect Markov chains might be useful is in the study of random searches with search locations chosen at random with replacement.

Did
  • 279,727
jdwhitfield
  • 151
  • Hey, thank you for the answer. – ori Aug 20 '13 at 11:43
  • Hey, thank you for the answer. Maybe I asked a general question and therefore I will elaborate on it. Indeed, My Markov chain is irreducible, aperiodic (discrete also) and 1-step connected including each state to itself, but I'm more interesting in the stationary distribution and it's structure. With my transition probabilities I get that the distribution is "bell shaped" and I wonder the reason for this. Is there a connection to the connectivity of the chain? – ori Aug 20 '13 at 11:52
  • "The chain isn't irreducible unless it aperiodic in addition to all states being mutually reachable"... Not true. – Did Aug 20 '13 at 12:00
  • @ori What is a "bell shaped" distribution on a finite set? – Did Aug 20 '13 at 12:01
  • Let me explain better, First, the chain is irreducible since we have only single communicating class. In addition each state has positive probability to remain at the same state therefore all the states are aperiodic hence the chain is aperiodic, correct me if I'm wrong. regarding the "bell shaped" distribution: if I plot the distribution in Mathematica -> although it's discrete I can see a "bell shaped" tendency. Thanks – ori Aug 20 '13 at 12:26
  • @ori How do you order the vertices to see the bell shape? (Unrelated: please use @.) – Did Aug 21 '13 at 17:40