Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 1 down vote favorite

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?

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

1 Answer

up vote 1 down vote

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.

share|improve this answer
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 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 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 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 at 8:01
1  
@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 at 9:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.