1

Let $P$ denote the $s\times s$ Markov transition matrix. We know that irreducibility and aperiodicity implies the following:

There exists an integer $N\geq 1$, such that $[P^n]_{ij}>0$ for all $i,j$ and all $n\geq N$.

Is the following property true for irreducible and aperiodic chains?

Fix $i,j$. Suppose $[P^n]_{ij}>0$ for some integer $n$, then $[P^{m}]_{ij}>0$ for all $m\geq n$.

oacikgoz
  • 41

2 Answers2

0

Nevermind, the statement is incorrect. I found a counterexample:

Suppose $P$ is $3\times 3$. Let $P_{11}=P_{13}=P_{22}=0$ and $P_{12}=1$. All other entries are positive. This chain is aperiodic and irreducible. You can check that $[P^2]_{12}=0$ even though $P_{12}>0$.

oacikgoz
  • 41
-1

If the chain is irreducible, and we have $[P^n]_{ij}>0$ for all $i,j$ and all $n\geq N$, it means we communicate states $i$ and $j$ with some probability.

Your assumption is false, since the value $P_{ij}^n$ doesn't make sense (in the probabilistic mean.). for $n=1$, this represents the probability of going from state $i$ to state $j$, but to power it, means what?.

On the other hand, what you may want to do, it to factorize you matrix, using it's eigenvalues and eigenvectors, so you can operate matrix power much faster. We have $$P^m =U^{-1} \Sigma^m U,$$ where the matrix $U$ is composed by the eigenvectors of $P$ and $\Sigma$ is the diagonal matrix with the eigenvalues of $P$. And the nice thing about $\Sigma$ is that $\Sigma^m= \left(\sigma_{i,j}^m \;;\; (i,j) \in |s|^2\right),$ where $\sigma_{i,j} = 0$ if $i \neq j$.

Guilherme Thompson
  • 917
  • 2
    I think you are confused about the notation. $P^n$ means $P\times P...\times P$ $n$ times. It's not ij transition probability to the power $n$. I'm pretty sure that the first statement is correct. I was asking about the validity of the second one. But nevermind, I found a counter example. – oacikgoz Dec 16 '15 at 15:03
  • "Fix $i,j$. Suppose $P^n_{ij}>0$ for some integer $n$, then $P^{m}_{ij}>0$ for all $m\geq n$." Either you can't write or have no idea about what you are speaking. Just before, you used Please. – Guilherme Thompson Dec 16 '15 at 15:10
  • 1
    I see what you mean. I fixed it above. No need for petty insults. – oacikgoz Dec 16 '15 at 15:37