Trivial bounds on the power to prove matrix is regular

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 $$ 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 $$), 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.

• Thank you. Do you know if there is any reference to this fact in the literature ? Jun 17 '19 at 8:12
• 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. Jun 17 '19 at 8:23