1
$\begingroup$

I need the proof of the following theorem or a link where I can get the proof,

If a Markov chain is irreducible and aperiodic with stationary distribution $\pi$, then for all states $i$ and $j$ $$\lim_{n\rightarrow\infty}\mathbb P_i(X_n=j)=\pi_j$$

I have some question regarding the theorem like:

  • Why irreducible and aperiodic need here? What's their role?
  • What's the meaning of this theorem?

Irreducibility is the property that regardless the present state we can reach any other state in finite time. Mathematically it is expressed as $$\forall i,j\in S,\exists m<\infty : \mathbb P(X_{n+m}=j|X_n=i)>0$$ The period $d(k)$ of a state $k$ of a homogeneous Markov chain with transition matrix $P$ is given by $$d(k)=\gcd\{m\geq1:P_{k,k}^m>0\}$$ if $d(k)=1$, then we call the state $k$ aperiodic. A Markov chain is aperiodic if and only if all its states are aperiodic.

Hence, what does $P(X_n=j) \to \pi_j$ or $P(X_n=j|X_0=i) \to \pi_j$ for every $i$ mean?

It will be a great help if someone help me to understand the theorem statement along the proof.

$\endgroup$
5
  • $\begingroup$ Markov Chains by Isaacson and Madsen. $\endgroup$ Aug 10, 2021 at 6:37
  • $\begingroup$ I couldn't manage any soft copy of that book. Could you suggest/provide one? @KaviRamaMurthy $\endgroup$ Aug 10, 2021 at 6:43
  • $\begingroup$ Any textbook on Markov chains. For example, Chapter 4 of this one: pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf $\endgroup$
    – user711689
    Aug 10, 2021 at 11:11
  • $\begingroup$ Thanks, @PeterMorfe. I have gotten some insight about irreducibility and periodicity from section 1.3. But still there isn't the proof in chapter 4 as you mentioned (if I am not wrong). $\endgroup$ Aug 10, 2021 at 12:02
  • $\begingroup$ @WhyMeasureTheory, check out Section 4.3. $\endgroup$
    – user711689
    Aug 10, 2021 at 20:25

1 Answer 1

1
$\begingroup$

I found the statement in Klenke. I only have the German version, it is 18.12 / 18.13 there. Maybe that helps.

For the intuition: The statement tells you that, no matter in which state $i$ you started, the probability of being in state $j$ converges to the stationary distribution if you keep sampling from the chain long enough. That fits the intuition for a stationary / invariant distribution: Once this distribution is reached, the distribution will not change anymore if more samples are drawn. And the power of the theorem lies in the part "no matter where you started".

For irreducibility: I think, reducible Markov chains could have more than one invariant distribution, so that would make the theory more complicated. (Imagine, a chain $X$ had two distinct irreducible sub-chains $Y$ and $Z$ with all transition probabilities between the two being zero, i.e. from states in $Y$, you cannot reach any state in $Z$ and vice versa. Assume $Y$ and $Z$ have invariant distributions. Then there are multiple ways to combine these two to get an invariant distribution of $X$.)

For periodicity: Assume $i$ is a periodic state, i.e. $$ d(i) = \text{gcd}(\{ n \geq 1: \mathbb{P}_i(X_n = i) > 0 \}) > 1 .$$ This means, if $\mathbb{P}_i(X_n = i) > 0 \}) > 1$, then $d(i) \mid n$. Conversely, if $d(i) \nmid n$, we must have $\mathbb{P}_i(X_n = i) = 0$.

Hence, the sequence $$(\mathbb{P}_i(X_n = i))_{n \in \mathbb{N}}$$ contains infinitely many zeros, for all $n$ which are not a multiple of $d(i)$ and thus will not converge to anything $> 0$. But the invariant distribution can't be all $0$. Intuitively, the period $d(i)$ tells us: Given we start in $i$, after how many steps can we possibly be in $i$ again? If e.g. $d(i) = 2$, then we can only be there after 2 or 4 or 6 ... steps, never after 1 or 3 or 5...

A counterexample: enter image description here

$\endgroup$
8
  • $\begingroup$ OK, irreducibility make sense to me now but still couldn't manage to understand the role of periodicity. Like I understand, When considering periodicity we always look at the set of possible times we can be in a certain state. Like if a state $s_i$ have period is $2$ the chain can be in $s_i$ every second time, that is on even or odd times depending on where we start, but not both. @AdaLovelace $\endgroup$ Aug 10, 2021 at 11:37
  • $\begingroup$ I added some more details, does this help? $\endgroup$ Aug 10, 2021 at 12:02
  • $\begingroup$ Thanks, again for your response. The details clear some confusion but still I couldn't get the role of its in this theorem. If I am not wrong then there is another theorem stated Let $X$ be an irreducible and aperiodic Markov chain with finite state space and transition matrix $P$. Then there exists an $M<\infty$ such that $(P^m)_{i,j}>0$ for all states $i$and$j$ and all$m\geq M$ Where is the difference between these two theorem? It seems like I am missing the necessary of periodicity or unable to interpret its role in different places @AdaLovelace.Sorry, If I am asking too many questions. $\endgroup$ Aug 10, 2021 at 12:14
  • $\begingroup$ Your statement does not contradict the above theorem, it is just a weaker statement. But in both, you need an aperiodic chain, otherwise it won't work - my explanation above works for both of the two. Not sure I understand your question? $\endgroup$ Aug 10, 2021 at 12:45
  • $\begingroup$ YES, YES. both statement are same in some weaker or stronger sense. I knew that. But the question I want to ask is, "Why periodicity involve in those statement and its role in both case." Actually, I have taken this course recently and studying it by myself. @AdaLovelace. $\endgroup$ Aug 10, 2021 at 13:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .