# Question regarding irreducibility, recurrency and aperiodicity of a finite Markov chain

I'd like to know if the follow markov chain is irreducible, recurrent and aperiodic. I try to proof it but I'm not sure if I'm right.

The transition matrix of my Markov Chain is:

Look my attempts:

1-Irreducibility:

If a markov chain is irreductible so all states comunicate to each other that's there exists a $$n$$ such that $$P_{ij}^n>0$$ and a $$m$$ such that $$P_{ji}^m>0$$ for all $$i,j$$. (We can have a $$n,m$$ depending which states we are looking at but I liked to make the notation easier.)

I went in R and I've powered $$\mathbf{P}$$ to 1000.

Since all elements are greater than zero so it seems enough to take $$n=1000$$ for the chain to be irreducible.

2-Recurrency:

As that's a finite markov chain so there exist at least one state which is recurrent but by its supposed irreducibility, all states are recurrent.

3-Aperiodicity:

I don't have any clue how proof it by its classic definition:

If $$i$$ has period $$d$$ so $$P_{ii}^n=0$$ whenever $$n$$ is not divisible by $$d$$ and $$d$$ is the greatest integer with such property.

• In this particular case you only needed $P^2$ to find a suitable $m$ and $n$ for irreducibility Nov 19, 2021 at 23:50
• You can see $P_{ii}>0$ for at least one $i$ (in fact all of them) so $P^n_{ii}$ is never $0$ so $d$ must be $1$ as $1$ is the only positive integer which divides all $n$ Nov 19, 2021 at 23:53
• you're sure @Henry Nov 20, 2021 at 0:59
• I am sure that transition matrix is irreducible, recurrent and aperiodic Nov 20, 2021 at 1:20
• Concerning @Hentry's Comment about aperiodicity. If you can ever stay in the same state for one transition, then you can stay in the same state for any number of transitions. This breaks periodicity. If a state is periodic of period $d,$ then a state can be visited only every $d$th step. Nov 20, 2021 at 6:55

A Markov chain, with finite state space, that is irreducible, recurrent, and aperiodic is called ergodic. That is, for each state $$j$$ in the state space $$S,$$ we have $$\lim_{n\rightarrow\infty}p_{ij}(n) = p_j \ge 0$$ with $$\sum_{j\in S}p_j = 1,$$ so that the chain has a long run or limiting distribution.

You have already shown, by finding the transition matrix to the 1000th power, that the limiting distribution is $$p_1 = 1/4 = 0.025$$ and $$p_2=p_3 = 3/8 = 0.375.$$ This limiting distribution is also the stable or steady state distribution $$\sigma = (1/4,3/8,4/8),$$ such that $$\sigma P = \sigma.$$

This means that $$\sigma$$ is a left eigen vector of $$P.$$ It turns out that that $$\sigma$$ is real and is proportional to the eigen vector having the smallest modulus among the eigen vectors.

R will find right eigen vectors, so the following R code will find the stationary (thus limiting) distribution of an ergodic chain.

P = (1/12)*matrix(c(6,3,3,
4,4,4,
0,6,6), byrow=T, nrow=3)
P
[,1]      [,2]      [,3]
[1,] 0.5000000 0.2500000 0.2500000
[2,] 0.3333333 0.3333333 0.3333333
[3,] 0.0000000 0.5000000 0.5000000

g = eigen(t(P))\$vector[,1]
sg = as.numeric(g/sum(g));  sg
[1] 0.250 0.375 0.375

sg %*% P     # verify
[,1]  [,2]  [,3]
[1,] 0.25 0.375 0.375


Notes: Taking the transpose t changes left eigen vectors to right eigen vectors; notation [,1] selects the first eigen vector from R, which is the one with smallest modulus, and as.numeric gets rid of irrelevant complex number notation (in case one of the other eigen vectors happens to be complex-valued).

Some non-ergodic Markov Chains have steady state distributions. [An example is the two-state periodic chain with $$p_{12} = p_{21} = 1,$$ which has steady state distribution $$\sigma = (1/2,1/2).]$$ So use this method of computing limiting distributions only for ergodic chains.

By the way, taking the 1000th power of $$P$$ is overkill. The 16th power suffices in for this chain.

P2 = P %*% P;  P4 = P2 %*% P2; P4
[,1]      [,2]      [,3]
[1,] 0.2592593 0.3703704 0.3703704
[2,] 0.2530864 0.3734568 0.3734568
[3,] 0.2407407 0.3796296 0.3796296

P8 = P4 %*% P4;  P16 = P8 %*% P8; P16
[,1]  [,2]  [,3]
[1,] 0.25 0.375 0.375
[2,] 0.25 0.375 0.375
[3,] 0.25 0.375 0.375


Ref: If you want to know more about eigen vectors, you can read the relevant Wikipedia article. But for computing the steady state distribution of an ergodic Markov Chain, the demonstration above is probably all you need to know.

• Should that not be positive recurrent? Nov 20, 2021 at 9:14
• Unfortunately, terminology differs from author to author. But in a chain with finite state space, I think irreducible, recurrent, and aperiodic suffices. Nov 20, 2021 at 16:00