1
$\begingroup$

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)?

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – combo Jan 28 '17 at 19:38
  • $\begingroup$ 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. $\endgroup$ – rannoudanames Jan 28 '17 at 19:46
  • 1
    $\begingroup$ 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. $\endgroup$ – combo Jan 28 '17 at 20:24
  • $\begingroup$ @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 $\endgroup$ – rannoudanames Jan 28 '17 at 20:32
1
$\begingroup$

This answer is based on these lecture notes.

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$$

Putting this together with the proposition gives your aperiodicity result.

$\endgroup$
  • 1
    $\begingroup$ I see this now! that makes sense! I am now going to try proving the proposition from exercise 2.9 in order to make my argument valid. $\endgroup$ – rannoudanames Jan 28 '17 at 20:34
  • 1
    $\begingroup$ Good for you! It shouldn't be too hard, it seems like the notes are meant to lead you along to the proof. If that fails you can always see if you can find it in a paper somewhere :) $\endgroup$ – combo Jan 28 '17 at 20:35

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.