Consider any Markov chain on a state space with exactly $r$ states. We want to find the largest $N>0$ such that there exists states $i,j$ for every $n < N$ we have $p_{ij}^{(N)} > 0$ and $p_{ij}^{(n)} = 0$.

My Thoughts:

Therefore $N$ is a recurrent state, and $n$ is transient state. The period of states $i,j$ here would need to more than N. I don't see how knowing we have exactly $r$ states helps us identify the recurrent states. I think we want to find a transient state such that all the states before it are recurrent. Wouldn't this be the first transient state of the Markov chain? Since the Markov chain is arbitrary, I am not sure how to find $N$. I looked through the different theorems in the textbook, but not sure which one I can apply here.


It is a theorem of Wielandt that the number you are looking for is $(r-1)^2+1$. A way to achieve this is to have $p_{12},p_{23},p_{34},\dots,p_{k-1,k},p_{k,1},p_{k,2}$ positive and all other $p_{ij}$ zero. A reference is H Wielandt, Unzerlegbare, nicht negative Matrizen, Math Z. 52 (1950) 642-648.

Perhaps a better reference is Hans Schneider, Wielandt’s proof of the exponent inequality for primitive nonnegative matrices, Linear Algebra and its Applications 353 (2002) 5–10, available here.

EDIT: I knew this sounded familiar. I won a 500-point bounty at If $P$ is a regular transition probability matrix then $P^{n^2}$ has no zero element for (an extended version) of what I've written here. A question with a bounty can't be closed as a duplicate, I think.


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.