Long-run Proportion of Markov Chain

Description:

• For a pair of state $i\ne j$, let $f_{i,j}$ be probability that the Markov chain, starting in the state $i$, will ever make a transition into state $j$.
• That is, $f_{i,j}=P(X_n=j\text{ for some }n>0|X_0=i)$
• Proposition: If state $i$ is recurrent and $i$ communicates with state $j$, then $f_{i,j}=1$
  • meaning the process will eventually enter state $j$ with probablity 1, sooner or later
• If state $j$ is recurrent
  • Let $m_j$ denotes the expected number of transitions it takes the markov chain when starting from $j$ to get to state $j$ again
  • With $N_j=\min \{n>0:X_n=j\}$
    • number of transition to $j$ from any state
  • $m_j=E[N_j|X_0=j]$
    • expected number of transitions until first met $j$, starting from $j$
  • The recurrent state $j$ is positive recurrent if $m_j<\infty$
  • And $j$ is null recurrent if $m_j=\infty$ meaning there must be infinite steps before it comes back to itself
• If the Markov chain is irreducible and recurrent, then for any initial state ${\pi }_j=\frac{1}{m_j}$
  • where ${\pi }_j$ denotes the long-run proportion of time that the Markov chain is in state $j$
• If $i$ is positive recurrent and $i\leftrightarrow j$ then $j$ is Positive recurrent
  • it follows that null recurrentce is also a class property
  • An irreducible finite state MC must be Positive recurrent
• theorem : Consider an irreducible MC. If the chain is positive recurrent then the long-run proportions are the unique solution of the equations: ${\pi }_j=\sum _i{\pi }_i{P}_{ij},j\ge 1$ and ${\sum }_j{\pi }_j=1$
  • ${\pi }_i{P}_{ij}=$ long-run proportion of transitions that go from state $i$ to state $j$
  • So the long run ratio of state $j$ is sum of each state’s long-run proportion times probability of transitioning to $j$
  • Moreover, if there is no solution of the preceding linear equation, then the MC is either transient or Null recurrent and all ${\pi }_j=0$

Another prove:

• For stationary distribution in AI
• Let $P_{\infty }(x)={\pi }_x$
• $P_{\infty }(X)=P_{\infty +1}(X)={\sum }_{x}P(X|x)P_{\infty }(x)={\sum }_{x}P(X|x){\pi }_x$