A finite $n$-state Markov chain with transition matrix $P$ can be said to be ergodic, if there exists a power $a \in \mathbb{N}$ such that $P^a > 0$ entry-wise (the matrix is regular).

Are there any obvious bounds on the value of $a$ (depending on $n$), or can I construct examples for which $a$ is arbitrarily large ?


From irreducibility, you can reach state $j$ from state $i$ in $<n$ steps.

From aperiodicity, we have two coprime periods $p_1,p_2\leq n$ in our class. For any state $i$, we find paths to and from these cycles (each $<n$), so we have three coprime-length cycles (but not-necessarily pairwise coprime) starting from $i$:

  • go to cycle 1 (but not follow it) then go to cycle 2 (again not follow it) and back.
  • go to cycle 1, follow it once, then go to cycle 2 but not following it and back.
  • go to cycle 1 but not following it then go to cycle 2, follow it once and back.

These have lengths $<3n$, $<4n$, $<4n$ respectively. So we can represent all integers $\geq c(n)$ with positive integer multiples of these three numbers, so $p_{ii}^{(m)}>0$ for all $m\geq c(n)$. We can bound $c(n)\leq2(2n-1)^2-1$ (Lewin bound on the Frobenius number).

So $a<c(n)+n<8n^2$.

  • $\begingroup$ Thank you. Do you know if there is any reference to this fact in the literature ? $\endgroup$
    – geo.wolfer
    Jun 17 '19 at 8:12
  • $\begingroup$ I don't know if it fact is referenced anywhere. It is far easier to show irreducibility and aperiodicity separately than to compute a very high power of a matrix and check it has positive entries. $\endgroup$ Jun 17 '19 at 8:23

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.