# Reference request: convergence for periodic Markov chains

Consider an irreducible but possibly periodic Markov chain on a finite state space with transition matrix $$P$$. We know there exists a unique stationary distribution $$\pi$$. If the Markov chain were aperiodic, we would have $$P^n_{ij} \to \pi(j)$$ as $$n \to \infty$$. This fails if the chain is periodic, but we have convergence of the Cesaro averages: $$\frac{1}{n}\sum_{k=1}^n P^k_{ij} \to \pi(j) \text{ as } n \to \infty.$$ Can anyone point me to a reference that states this fact? Every reference I've seen only considers convergence for aperiodic chains, or "fixes" periodicity by considering a lazy version of the chain. Alternatively, is there a simple way to obtain this result using the result for aperiodic chains?

• I don't see how you go from $\sum xP^t$ to $\sum \lambda^j$ in your answer. But I would really prefer to cite a reference that states this if there is one out there. By $P^k_{ij}$ I mean the $ij$-entry of the $k$th power of the matrix $P$. Is $P^{(k)}$ typically used to denote the $k$th power of $P$? Would $(P^k)_{ij}$ be clearer?
– kccu
Jun 3 '20 at 23:07

I'd like to present a different elementary approach. I'm omitting some details.

From irreducibility, for any pair of states $$i,i'$$, there exists $$n_{i,i'}$$ such that $$p^{n_{i,i'}}_{i,i'}>0$$. Therefore the probability of visiting $$i'$$ by time $$n_{i,i'}$$ or earlier, starting from $$i$$, is at least $$p^{n_{i,i'}}_{i,i'}$$. Let $$\bar p = \min p^{n_{i,i'}}_{i,i'}>0$$, and let $$\bar n= \max n_{i,i'}<\infty$$.

That's the key to everything.

Thus, regradless of the current state and entire past, the probability that the process will visit $$i'$$ at least once in the next $$\bar n$$ steps is at least $$\bar p$$. In particular, the probability that state $$i'$$ was not visited by time $$L{\bar n}$$ is bounded above by $$(1-{\bar p})^L$$. Let $$\tau_{i'}$$ be the first time the chain hits state $$i'$$. Then we showed $$P_i(\tau_{i'}>L \bar n) \le (1-{\bar p})^L \to 0$$. In particular $$\tau_{i'}$$ has finite expectation under $$P_i$$. That's true for all $$i,i'$$.

Write $$S_n (i,j)= \sum_{k=0}^n p^k_{ij}$$.

Then

\begin{align*} S_n(i,j)&= E_i[\sum_{k=0}^n {\bf 1}_{X_k}(j)] \\& \le E_i[ \sum_{k=0}^n {\bf 1}_{X_k} (j), \tau_{i'}n)\\ &\le E_i [\tau_{i'}]+ E_{i'} [\sum_{k=\tau_{i'}}^n {\bf 1}_{X_j}(j),\tau_{i'}\le n] +(n+1) P_i (\tau_{i'}>n)\\ & \le E_i [\tau_{i'}] + S_n (i',j) + (n+1) P_i(\tau_{i'}>n). \end{align*}

Therefore,

$$\limsup_{n\to\infty} \frac{1}{n+1} (S_n (i,j) -S_n(i',j))\le 0.$$

Since this is true for all choices of $$i,i'$$, the limit exists and is equal to $$0$$.

Finally, suppose the states are $$1,\dots,K$$ and let $$\pi$$ be the stationary measure. Then

$$\pi(j) = \frac{1}{n+1} \sum_{i=1}^K \pi(i)S_n(i,j) =\frac{1}{n+1} S_n (1,j)+ \sum_{i'>1}\pi(i') \frac{1}{n+1} ( S_n (i',j) - S_n (1,j) ).$$

As the sum on the rightand tends to $$0$$, the result follows.

• Thank you for this elementary approach! Do you know if this is presented in any texts?
– kccu
Jun 4 '20 at 23:21
• Not sure... I you do find a reference, let me know. Jun 5 '20 at 15:03

The result follows immediately from applying the elementary renewal theorem to delayed renewal processes.

Here's a more elementary algebraic proof, using telescoping.
(problem 16, page 468 of Grinstead and Snell's free book https://math.dartmouth.edu/~prob/prob/prob.pdf )

for stochastic, $$\text{m x m}$$ matrix $$P$$

$$\mathbf \pi^T P = \mathbf \pi^T$$ and $$P\mathbf 1 = \mathbf 1$$,
$$W:= \mathbf 1 \mathbf \pi^T$$ and $$\text{trace}\big(W\big) = 1$$

consider the following telescope
$$\Big(I+P+P^2+....+ P^{n-1}\Big)\Big(I-P+W\Big) = I -P^n +nW$$

thus
$$\frac{1}{n}\Big(I+P+P^2+....+ P^{n-1}\Big)$$
$$= \frac{1}{n}\big(I -P^n +nW\big)\Big(I-P+W\Big)^{-1}$$
$$= \frac{1}{n}\Big\{\Big(I-P+W\Big)^{-1}\Big\} -\frac{1}{n}\Big\{P^n\Big(I-P+W\Big)^{-1}\Big\} +\frac{1}{n}\Big\{nW\Big(I-P+W\Big)^{-1}\Big\}$$
$$= \frac{1}{n}\Big(I-P+W\Big)^{-1} -\frac{1}{n}P^n\Big(I-P+W\Big)^{-1} +W$$

now pass limits

$$\lim_{n\to\infty}\Big\{ \frac{1}{n}\Big(I-P+W\Big)^{-1} -\frac{1}{n}P^n\Big(I-P+W\Big)^{-1} +W\Big\}$$
$$= \Big\{\lim_{n\to\infty}\frac{1}{n}\Big(I-P+W\Big)^{-1}\Big\} -\Big\{\lim_{n\to\infty} \frac{1}{n}P^n\Big(I-P+W\Big)^{-1}\Big\} +W$$
$$=0+0+W$$

so
$$W=\lim_{n\to\infty} \frac{1}{n}\Big(I+P+P^2+....+ P^{n-1}\Big)$$

That's the argument in its entirety. I've left three book-keeping details for the end.

re: the third term simplification $$W\Big(I-P+W\Big)^{-1}=W$$
suppose $$\Big(I-P+W\Big)^{-1}$$ exists, then consider the inverse problem
$$W\Big(I-P+W\Big) = W-WP +W^2 = W-W + W = W$$
now multiply both sides on the right by $$\Big(I-P+W\Big)^{-1}$$

re: the second limit
observe that
$$\Big\Vert \frac{1}{n}P^n\Big(I-P+W\Big)^{-1} - \mathbf 0\Big\Vert_F$$
$$= \frac{1}{n}\Big\Vert P^n\Big(I-P+W\Big)^{-1}\Big\Vert_F$$
$$\leq \frac{1}{n}\Big\Vert P^n\Big\Vert_F\cdot \Big\Vert \Big(I-P+W\Big)^{-1}\Big\Vert_F$$
$$\leq \frac{1}{n} \mathbf 1^T P^n \mathbf 1 \cdot \Big\Vert \Big(I-P+W\Big)^{-1}\Big\Vert_F$$
$$= \frac{1}{n} \mathbf 1^T \mathbf 1 \cdot \Big\Vert \Big(I-P+W\Big)^{-1}\Big\Vert_F$$
$$= \frac{m}{n} \cdot \Big\Vert \Big(I-P+W\Big)^{-1}\Big\Vert_F$$
$$\lt \epsilon$$
for large enough n
(The second to last inequality follows from triangle inequality)

re: the invertibility of $$\Big(I-P+W\Big)$$
we prove $$\det\Big(I-P+W\Big)=\prod_{j=2}^n (1-\lambda_j)$$ and hence the matrix is invertible.

the nicest proof involves (partial) symmetrization:
using Perron Frobenius theory, we know that $$\lambda_1 =1$$ is simple since $$P$$ is irreducibile.

$$\mathbf v_1 := \mathbf \pi^\frac{1}{2}\cdot \frac{1}{\big \Vert \mathbf \pi^\frac{1}{2}\big \Vert_2}$$
(where the square root is interpretted to be taken component-wise)

diagonal matrix $$D:=\text{diag}\big(\mathbf v_1\big)$$

Consider the similar matrix
$$D\Big(I-P+W\Big)D^{-1} = I- (DPD^{-1}) +DWD^{-1} = I - B + \mathbf v_1\mathbf v_1^T$$

$$B$$ has $$\mathbf v_1$$ as its left and right eigenvectors (check!).
Working over $$\mathbb C$$ and applying Schur Triangularization to $$B$$:

$$V := \bigg[\begin{array}{c|c|c|c}\mathbf v_1 & \mathbf v_2 &\cdots & \mathbf v_{n}\end{array}\bigg]$$
$$B = VRV^{-1} = VRV^{*} =V\begin{bmatrix} 1 & \mathbf x_{m-1}^*\\ \mathbf 0 & \mathbf R_{m-1} \end{bmatrix}V^* =V\begin{bmatrix} 1 & \mathbf 0^T\\ \mathbf 0 & \mathbf R_{m-1} \end{bmatrix}V^*$$
note $$\mathbf x_{m-1} = \mathbf 0$$ because $$\mathbf v_1^T = \mathbf v_1^* =\mathbf v_1^* B = 1\cdot \mathbf v_1^* + \sum_{j} x_j\cdot \mathbf v_j^*$$
and the columns of $$\mathbf V$$ (or rows of $$\mathbf V^*$$) are linearly independent so every $$x_j =0$$

By simplicity of the Perron root: $$\mathbf R_{m-1}$$ does not have eigenvalues of 1, so
$$I -B + \mathbf v_1 \mathbf v_1^T = V\big(I-R + \mathbf e_1\mathbf e_1^T\big)V^{*} =V\begin{bmatrix} 1 & \mathbf 0^T \\ \mathbf 0 & I_{m-1} -\mathbf R_{m-1} \end{bmatrix}V^*$$
hence the determinant is $$1\cdot \prod_{j=2}^n (1-\lambda_j) \neq 0$$.