# Markov chain property

Suppose $\{Y_{n}, n \ge 0\}$ is a Markov chain consisting of $N$ states. Suppose that $i$ and $j$ are states of this Markov chain and that $i \hookrightarrow j$, i.e state $j$ can be reached from state $i$. Show that:

i) There exists some integer $n \le N$ such that $P_{ij}^{n} \gt 0$.

ii) The period state $i$ can be at most $N$.

For the first part, will the Kolmogorov-Chapman equations be of any use here?

-
I don't know what $i\hookrightarrow j$ means. – Gerry Myerson Mar 18 '13 at 4:35
State j can be reached from state i. Sorry for the confusion. – Schrodinger Mar 18 '13 at 4:58

## 1 Answer

I take it $P$ is the transition matrix for your Markov chain. That means $P_{ij}$ is the probability of a one-step transition from state $i$ to state $j$. Taking $P_{ij}^n$ to mean the $ij$ entry in $P^n$, do you understand that this is the probability of a transition from $i$ to $j$ in $n$ steps? Well, then, if you can get from $i$ to $j$ at all, you can get there in some finite number, $n$, of steps.

I don't know what "the period state $i$" means.

-
but you have to prove that $n \leq N$. We could have $P^n_{ij} = 0$ for all $n \leq N$, and $P^{N+1}_{ij} > 0$. – Djaian Mar 18 '13 at 12:25
@Djaian, I missed that, but I think the gap is easily filled. If there a path from $i$ to $j$ in $m$ steps, with $m\gt N$, then some state $k$ shows up twice in that path, so you could shorten the path by leaving out all the states between the two appearances of $k$. So, the shortest path can't visit any state twice, so it has length at most $N$. – Gerry Myerson Mar 18 '13 at 22:50
@Gerry that is a much nicer argument than the thought I had, which concerned the use of Cayley-Hamilton and/or the characteristic polynomial/interpolating a polynomial with $N$ zeros... I could probably use some practice thinking in terms of state transitions... – adam W Mar 18 '13 at 23:50
@GerryMyerson The question was edited after your answer, so maybe it was not there at the time. Yes, of course it is not difficult to prove that $n \leq N$, I just wanted to say that you should add it to your answer. I think the second part of the question is : if $i$ is a periodic state, show that the period $p \leq N$. – Djaian Mar 19 '13 at 8:01
@Djaian, you may be right about the second part, but if OP can't be bothered to clarify the question, then I can't be bothered to try to answer it. – Gerry Myerson Mar 19 '13 at 9:10