1

If I understood well, a Markov Chain with state space $E$ is said to be irreductible if for all $x,y\in E$ there is $n$ such that $$P^n(x,y)>0,$$ where $P$ is the transition matrix.

Also, I know that a Markov chain is aperiodic if and only if for all $x,y\in E$ there is $N$ such that for all $n>N$: $$P^n(x,y)>0.$$

Then it seems clear to me that every aperiodic Markov chain is irreductible. That is, in fact, true? If not, what have I got wrong and what is a counter-example?

Thank you

Gabriel
  • 4,513
  • I believe that it is not true that any aperiodic markov chain is irreducible. Consider a chain with state space (0,1) with conditional probabilities: 1 of going from state 0 to state 1, and 1 of going from state 1 back to state 0. This is irreducible (clear). This is not aperiodic as the possible return times are 2,4,6,8,..... Therefore you can not find an N s.t. the condition for aperiodicity holds. – Locally unskillful Feb 16 '19 at 14:34
  • @Alexandros, in your example we have a Markov chain which is irreductible but not aperiodic. I want to find a Markov chain which is aperiodic but not irreductible. – Gabriel Feb 16 '19 at 14:36
  • 1
    Oh I misread your question. In that case, using your definition of an aperiodic markov chain, then yes any aperiodic markov chain must be irreducible. (However, keep in mind that you can find examples where you have two aperiosic classes, which do not communicate with each other, ie not an irreducible Markov chain, most trivial example would be Markov chain where E=(0,1) and the probability of staying at 0 or 1 is 1.) – Locally unskillful Feb 16 '19 at 14:50
  • @GabrielRibeiro The usual definition of aperiodicity is that of the greatest common divisor of the $n$ such that $P^n_{x,x} > 0.$ – William M. Feb 18 '19 at 23:09
  • @Will M. Yeah, I know. But this definition is equivalent to mine's, isn't it? If the gcd of a infinite set of positive integera is 1, then every sufficiently large integer is in this set. – Gabriel Feb 20 '19 at 15:24
  • 1
    @Gabriel: That lemma in your comment isn't true, BTW. For example, the set of primes is clearly infinite and its GCD is 1, but not all sufficiently large integers are prime. – Ilmari Karonen Aug 28 '22 at 09:39
  • @IlmariKaronen oh of course! Thank you! – Gabriel Sep 03 '22 at 13:35

2 Answers2

1

Your statement is correct. Aperiodicity implies irreducibility but is stronger. Whereas in the case of irreducibility your integer variable $n$ generally depends on the pair $x,y$ chosen, aperiodicity allows one to choose $n$ independent of any pair $x,y$.

alexl
  • 421
1

Your definition of aperiodicity is incorrect and not equivalent to the usual one that $\ \gcd\big\{n\,\big|\,P^n(x,x)>0\,\big\}=1\ $ for all states $\ x\ $. Apart from the problem pointed out by Ilmari Koronen in the comments, you're requiring $\ P^n(x,y)>0\ $ for all $\ x\ $ and $\ y\ $. In the definition of aperiodicity, you take the gcd over only those $\ n\ $ for which $\ P^n(x,\color{red}{x})>0\ $, not over those for which $\ P^n(x,y)>0\ $ where $\ y\ne x\ $.

If $\ P_1, P_2\ $ are transition matrices for two aperiodic Markov chains, then the Markov chain with transition matrix $$ \pmatrix{P_1&0\\0&P_2} $$ is not irreducible, but it will be aperiodic.

lonza leggiera
  • 28,646
  • 2
  • 12
  • 33