5
$\begingroup$

The definitions pertaining to Markov chains are generally different for finite state space and general state space Markov chains. This is mainly due to the fact that one cannot talk about moving to a state $x$ for general state spaces, and one cannot write down the transition "matrix". However, in my experience, most definitions for general state space Markov chains like irreducibility, recurrence etc are a general extension from the finite state space.

I recently realized that this is not true for the definition of periodicity. For general state space $\mathcal{X}$ the definition of aperiodicity is (you can find a reference here):

A Markov chain with stationary distribution $ \pi(\cdot)$ is aperiodic if there does not exists $d \geq 2$ and disjoint sets $\mathcal{X}_1, \dots, \mathcal{X}_d \subseteq \mathcal{X}$ with $P(x, \mathcal{X}_{i+1}) = 1$ for all $x$ in $\mathcal{X}_i$ ($1 \leq i\leq d-1$) and $P(x, \mathcal{X}_1) = 1$ for all $x$ in $\mathcal{X}_d$ such that $\pi(\mathcal{X}_1) > 0$. Otherwise the chain is periodic with period $d$.

This is the definition that makes more sense to me since it essentially means that the Markov chain cannot get stuck in a loop indefinitely.

For finite state space Markov chains, the definition is (can be found here).

For a state $x$, define its period $d_x$ as $$d_x = \gcd \{n\geq 1: P^n(x,x) > 0\} \,.$$ If the Markov chain is irreducible, then all states share the same period $d$. If $d = 1$, then the Markov chain is called aperiodic.

This definition does not necessarily say that the Markov chain will get stuck in a loop. So my question is, is there anyway that the general state space definition is a generalization from the finite state space definition?

$\endgroup$
  • $\begingroup$ Do you know if it is true that an aperiodic Markov chain with a unique stationary distribution $\pi$ satisfies the property that $\sup_{A\in \mathcal X}|P^n(x, A)-\pi(A)|\to 0$. If yes, do you also know of a proof? Thanks. $\endgroup$ – caffeinemachine Dec 20 '18 at 9:35
  • $\begingroup$ @caffeinemachine I believe the answer is no. Particularly, you may have convergence $\pi$-a.e, but not in the complete total variation sense. See the discussion of this counter-example here: stats.stackexchange.com/questions/331158/… $\endgroup$ – Greenparker Dec 20 '18 at 17:23
  • $\begingroup$ I checked the paper referenced in the post you linked to, and the symbol "$\|{\cdot}\|$" is used to denote the total variation distance. So according to the theorem the convergence occurs in total variation distance. However, the paper does not seem to provide a proof or a reference. I looked at Meyn and Tweedie, but could not locate the theorem (though it must be present in the book in some form, perhaps more general). $\endgroup$ – caffeinemachine Dec 21 '18 at 9:22
  • $\begingroup$ Sorry, it seems that the paper has indeed given an argument. $\endgroup$ – caffeinemachine Dec 21 '18 at 9:33
4
$\begingroup$

The following argument shows how the "gcd" criterion leads to "stuck in a loop."


For an irreducible Markov chain with state space $\cal S$, suppose that for some $i\in{\cal S}$ and $d\geq 1$, we have $(n\geq0: p_{ii}(n)>0)\subset d\mathbb{Z}$.

By irreducibility, for any state $j$ we can find non-negative integers $m,m^\prime$ so that $p_{ij}(m)>0$ and $p_{ji}(m^\prime)>0$. Then $0< p_{ij}(m)p_{ji}(m^\prime)\leq p_{ii}(m+m^\prime)$ so that $m+m^\prime \equiv 0 \pmod{d}$.

In particular, if $p_{ij}(m)>0$ and $p_{ij}(m^{\prime\prime})>0$, then $m\equiv m^{\prime\prime}\pmod{d}$. So for $0\leq r<d$ we can partition $\cal S$ as follows: $$C_r=\left\{j\in{\cal S}: p_{ij}(n)>0\Rightarrow n\equiv r\pmod{d}\right\}.$$ We also let $C_d=C_0$.

If $j\in C_r$ and $k\in C_s$, for any $n,n^\prime,n^{\prime\prime}$ with $0<p_{ij}(n)p_{jk}(n^\prime)p_{ki}(n^{\prime\prime})\leq p_{ii}(n+n^\prime+n^{\prime\prime})$, we get $n+n^\prime+n^{\prime\prime} \equiv 0 \pmod{d}$, or $n^\prime\equiv s-r \pmod{d}$. Taking $n^\prime=1$ for example, we see that $p_{jk}>0$ implies $s\equiv r+1\pmod{d}$ so $$\sum_{k\in C_{r+1}}p_{jk}=1 \mbox{ for any }j\in C_r.\tag 1$$

Note that $i\in C_0$ and therefore by (1) and induction, $C_r$ is non-empty for all $0\leq r<d$.


Added: What I mean by "stuck in a loop" is that the Markov chain will cycle through $d$ subsets of states. Here is a picture of what this looks like when $d=5$:

enter image description here

Notation:

  1. The notation $\sum_{k\in C_{r+1}}$ means that you sum over all states $k$ that lie in the subset $C_{r+1}.$

  2. The notation $\mathbb{Z}=\{\dots, -2,-1,0,1,2,\dots\}$ means the set of integers, and $d \mathbb{Z}=\{dz: z\in\mathbb{Z}\}=\{\dots, -2d,-d,0,d,2d,\dots\}$ is the subset that consists of all multiples of $d$.

$\endgroup$
  • $\begingroup$ Thanks for the answer. Could you fill in more details here? What is the last summation over? What does the notation $d\mathbb{Z}$ mean? And what exactly is your interpretation of "stuck in a loop"? $\endgroup$ – Greenparker May 4 '17 at 9:09

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.