# Determining aperiodicity of markov chain

I am trying to show the following markov chain is aperiodic (it could very well not be)

$S = \mathbb{Z}$ and $h : S \rightarrow (0,1)$ with $h(i)>0 \space \forall i \in S$ and $\sum_{i \in S}h(i) = 1$
the probabilities on $S$ given by $p_{ij} = (1/4)min(1,h(j)/h(i))$ if $|i-j| \leq 2$ and $i \neq j$, and $p_{ii} = 1-p_{i,i-2}-p_{i,i-1}-p_{i,i+1}-p_{i,i+2}$, and $p_{ij} = 0$ otherwise.
($p_{ij}$ is defined as the probability to go from state $i$ to state $j$)

Now I have some reason to think this chain is aperiodic, this is my work so far:

Assume $h(i)=h(j) \space \forall i,j \in S$, given $\sum_{i\in S} h(i) =1$
$h(i) = h(j) = \lim_{n \to \infty} (1/n)\sum_{i \in S}h(i) = 0$ with $n$ being the number of elements composing S.
Therefore $h(i) = h(j) = 0\space \forall i,j \in S$ implying $\sum_{i \in S}h(i) = 0$ a contradiction, showing $h(i) \neq h(j)$ for some $i,j$.

Now what this shows is that for some states in the chain, $p_{ii} \neq 0$ meaning that state is aperiodic. I hope however the whole chain is. Fow now I have the impression that I would have some 100 consecutive states with probability 1/10000 each, making my chain periodic, or is that possibility somehow not possible (pardon my wording)?

• I don't agree with your proof. The statement $h(i)=h(j) \,\forall i,\, j \in S$ along with $\sum_{i \in S} h(i) = 1$ means that $h(i) = \frac{1}{\lvert S\rvert}$. This does not give you the contradiction, since $\sum_{i \in S} \frac{1}{\lvert S \rvert} = 1$, even as $\lvert S\rvert \to \infty$. Since you have a lot of (simple) structure in your transition matrix, I would try looking at the structure of the matrix exponential – combo Jan 28 '17 at 19:38
• I understand your criticism of the proof, however could you further elaborate on looking at the structure of matrix exponential? Moreover, what could I do to fix my proof, as I do think it is true that we can not have equal probabilities on an infinite set. – rannoudanames Jan 28 '17 at 19:46
• I think matrix exponential is the wrong word to use - but I meant $P^n$. The characterization of aperiodicity given by Exercise 2.8 here basically says a chain is aperiodic if and only if there isn't a capturing state. This is a moot point, since I think you can do this much more easily. After $t > n$ transitions, you should have $(P^t)_{i,j} > 0$, since your graph is connected. This means that your chain is irreducible, and since your graph contains self loops, use Exercise 2.9 to show that it is aperiodic. – combo Jan 28 '17 at 20:24
• @StefanJorgensen Ahh yes, I was going to mention that exercise 2.9 seems simpler to apply! Could you be kind enough to hint as to what would be a good way to show there is at least one self loop (i have already managed to show the chain is irreducible) I have the impression that showing at least one $h(i) \neq h(j)$ for i,j diffrent would be sufficient. but am still confused as to what argument would solve this – rannoudanames Jan 28 '17 at 20:32

Let $P$ be the transition matrix, with $(P)_{i,j} = p_{i,j}$. A chain is irreducible if for all $i$,$j$, there is some $t$ such that $(P^t)_{i,j} > 0$. Since $P$ is tridiagonal and all entries are positive, it is irreducible.
Now from the notes, we have the proposition (Excercise 2.9): "Suppose $P$ is irreducible and contains at least one self-loop (i.e., $(P)_{i,i} > 0$ for some $i$). Then $P$ is aperiodic."
Clearly $P$ has self-loops, since $p_{i,j} \in (0,\frac{1}{4})$ if $i\neq j$ and $\lvert i-j\rvert \le 2$, and from the definition: $$p_{i,i} = 1 - p_{i,i-1} - p_{i, i-2} - p_{i,i+1} - p_{i,i+2} > 1 - \frac{1}{4} - \frac{1}{4} - \frac{1}{4} - \frac{1}{4} = 0$$