0

Let $P=(p_{ij})_{i,j\in E}$ denote the transition matrix of a Markov chain with finite state space $E$. Why does the following implication hold:

$$ \exists n\in\mathbb{N}: p_{ij}^{(n)}>0~\forall i,j\in E~~\implies P^n\text{ is irreducible for all }n\in\mathbb{N} $$

As far as I see $P^n$ irreducible for a $n\in\mathbb{N}$ means that for each pair $(i,j)$ there exists a $m\in\mathbb{N}$ such that $$ p_{ij}^{(mn)}>0? $$

If yes, then my idea would be that because of the assumption it is $p_{ij}^{(n)}>0$ and $p_{jj}^{(n)}>0$ so that $$ p_{ij}^{(mn)}\geq \underbrace{p_{ij}^{(n)}\cdot p_{jj}^{(n)}\cdot\ldots\cdot p_{jj}^{(n)}}_{\text{m-times}}>0, $$ so that for each pair $(i,j)$ there is a $m\in\mathbb{N}$ such that $p_{ij}^{(mn)}>0$.

Does this make sense or is it nonsense?

2 Answers2

1

Consider the following transition matrix: $$P=\left(\begin{array}{cc}0 & 1 \\ 1 & 0 \end{array} \right) $$

Here I would say $P$ is irreducible but $P^2$ is not. More generally, $P^k$ is irreducible if $k$ is odd but not if $k$ is even. Do you agree, or am I missing something?

All of this is to say the RHS of your statement is false here but the LHS is true ($n=1$ works), so I would seem to have contradicted the statement. What am I missing?

I'm not sure what you're up to with the $m$'s. Could you add a little more text to motivate your operations?

Shane
  • 1,325
  • I simply do not know what P^n irreducible means in general. –  Nov 04 '14 at 22:55
  • Do you understand what it means for $P$ to irreducible? A Markov chain is irreducible if the state space consist of only one class, i.e., for any $i,j \in S$, $i\leftrightarrow j$. That is, $i$ communicates with $j$. That is, there exists an $n \in \mathbb{N}$ such that $p_{ij}^{(n)}>0$. – Shane Nov 04 '14 at 23:02
  • Yes for P I know this but not for P^n with n >= 2 –  Nov 04 '14 at 23:03
  • 1
    It seems to me that if $P$ is irreducible, $P^n$ would be irreducible also so long as there is no deterministic cyclical behavior such as that included in my answer. It might have something to do with periodicity. May I ask where you found the statement you posted? – Shane Nov 04 '14 at 23:07
  • Anyway, does the implication hold the other way round? –  Nov 05 '14 at 09:08
  • @math12 May I ask why you systematically refuse answering queries about your, or the question's, background (such as you just did in your last comment)? – Did Nov 05 '14 at 09:23
  • @Did Sorry, forgot it. The source of this question is a row of statements which equivalence is to show. And so I guessed that this statement may hold. –  Nov 05 '14 at 09:24
  • This is not what I call explaining where one found a statement. Please continue to play word games (but do not complain afterwards if this has consequences). – Did Nov 05 '14 at 09:26
  • 1
    Indeed, it seems to me that the statement is not true as shown by the counterexample in my answer. It's possible I'm missing some context or something in the original question, but it's impossible for us to evaluate that without being able to see the question in its original form, or at least knowing where it was presented. – Shane Nov 05 '14 at 14:00
0

I believe the answer is given by the theorem.

Theorem. (Gantmacher F.R. The Theory of Matrices, 1960, Vol. 2, P. 80, Theorem 8.) A matrix $A \geq 0$ is primitive if and only if some power of $A$ is positive: $A^p > 0$ ($p \geq 1$).

Proof of the theorem can be found in the book.

Actually the answer depends if the statement should be understood like this $$ (\forall i,j\in E)(\exists n\in\mathbb{N})[p_{ij}^{(n)}>0]~~\implies (P^n\text{ is irreducible for all }n\in\mathbb{N}), $$ or like this $$ (\exists n\in\mathbb{N})(\forall i,j\in E)[p_{ij}^{(n)}>0]~~\implies (P^n\text{ is irreducible for all }n\in\mathbb{N}). $$ The first interpretation is false and is hold for any irreducible matrix, while the second is true due to the theorem above.

Wormer
  • 266