0
$\begingroup$

I don't fully understand ergodic. And I have trouble in this problem(21.8) from book introduction to information retrieval .

Consider a Markov chain with three states A,B and C, and transition probabilities as follows. From state A, the next state is B with probability 1. From B, the next state is either A with probability $P_{A}$,or state C with probability $1-P_{A}$. From C the next state is A with probability 1. For what values of $P_{A} \in [0,1]$ is this Markov chain ergodic?

I thought that I can construct the matrix and compute the probability many times. And if the result matrix is stable and no-zero. But I guess this method is not so good. Thanks.

$\endgroup$
5
$\begingroup$

Different people use different notions of what it means to be ergodic. As far as I know the weakest form of ergodicity is requiring that there is exactly one invariant distribution. Let us call this weakly ergodic. For a finite state Markov chain, this is equivalent to requiring that the chain is irreducible, i.e. it is possible to reach any state from any other in a finite number of transitions.

In your example, you have transition matrix $$ \begin{pmatrix} 0 & 1 & 0 \\ P_A & 0 & 1 - P_A \\ 1 & 0 & 0 \end{pmatrix} $$ Let $\pi = (\pi_A, \pi_B, \pi_C)$ denote any invariant distribution. The equations for invariance give $$\pi_B = \pi_A \quad \mbox{and} \quad \pi_C = (1-P_A) \pi_A,$$ or after normalization, $$ \pi = \frac{1}{3 - P_A} (1, 1, 1 - P_A).$$ So regardless of the value of $P_A$, there is a unique invariant distribution and the chain is weakly ergodic. For a weakly ergodic chain, time averages of functions converge to averages over the invariant distribution for every initial condition.

Often, people have something stronger in mind when talking about ergodicity. Let us say that a Markov chain is strongly ergodic if it is irreducible and aperiodic. In the above Markov chain, if $P_A = 1$, the state $C$ is transient (and so the chain is not irreducible) and if $P_A = 0$, the chain is periodic. So to have strong ergodicity we require $0 < P_A < 1$. For a strongly ergodic chain, the probability distribution of being in a particular state at time $n$ converges to the invariant distribution for large $n$.

I recommend Norris, Markov Chains for background reading.

$\endgroup$
  • 2
    $\begingroup$ (+1) Thank you for an exceptionally clear, well-explained, and authoritative answer. Welcome to our site! $\endgroup$ – whuber Jun 6 '16 at 13:41
  • $\begingroup$ I am confused at irreducible and aperiodic. Can you give a simple and understandable definition? Thanks. $\endgroup$ – Mark Jun 6 '16 at 14:02
  • 1
    $\begingroup$ The definition of these notions is a bit more involved, but very standard. I recommend looking up the definitions in the book by Norris, Section 1.2 (for irreducible) Section 1.8 (for aperiodic), available online at statslab.cam.ac.uk/~james/Markov $\endgroup$ – Joris Bierkens Jun 6 '16 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.