# Utilizing Network Structure to Accelerate Markov Chain Monte Carlo Algorithms
## 3 Convergence Analysis
Now we can apply Lemma 1 for the comparison of (8) and (9). The roles for the quantities in Lemma 1 are assigned as \(x=\tilde{\pi}_{0}\), \(y=\tilde{\pi}\), \(k=t\), \(n=m\), and, for every \(\tau=1,\ldots,k\), \(B_{\tau}=\bar{P}_{\tau}(\pi_{0})\), \(C_{\tau}=\bar{P}_{\tau}(\pi)\). To find the value of \(\rho_{0}\) recall that by (7) we have \(L\leq\bar{P}_{\tau}(\pi_{0})\leq M\) and \(L\leq\bar{P}_{\tau}(\pi)\leq M\). Since any entry of \(U\) exceeds the corresponding entry of \(L\) at most by \(\epsilon\), therefore, by the definition of the ergodic coefficient, \(\rho\big{(}\bar{P}_{\tau}(\pi_{0})\big{)}\leq\rho+\epsilon m/2\) and \(\rho\big{(}\bar{P}_{\tau}(\pi)\big{)}\leq\rho+\epsilon m/2\) hold, where \(\rho\) is the upper bound on \(\rho(L)\). Thus, we can take \(\rho_{0}=\rho+\epsilon m/2\). With these role assignments we obtain from Lemma 1  
\[\sum_{i=1}^{m}\left|\pi_{t}(A_{i})-\pi(A_{i})\right|\leq 2(\rho+\epsilon m/2)^{ t}+\epsilon m\frac{1-(\rho+\epsilon m/2)^{t}}{1-\rho-\epsilon m/2}\]9  
where \(\mathcal{E}=\max_{\tau}\|P_{\tau}(\pi_{0})-P_{\tau}(\pi_{0})\|\) and the norms are as in Lemma 1. Taking (8) and (9) into account yields  
\[\|xB_{1}\ldots B_{k}-yC_{1}\ldots C_{k}\|\leq\rho_{0}^{k}\|x-y\|+\left(\sum_{j =0}^{k-1}\rho_{0}^{j}\right)\mathcal{E}\]0  
Thus, it only remains to estimate \(\|\tilde{\pi}_{0}-\tilde{\pi}\|\) and \(\mathcal{E}\). Given that \(\tilde{\pi}_{0},\tilde{\pi}\) are both stochastic vectors, we have \(\|\tilde{\pi}_{0}-\tilde{\pi}\|\leq\|\tilde{\pi}_{0}\|+\|\tilde{\pi}\|\leq 2\). Further,  
\[\|xB_{1}\ldots B_{k}-yC_{1}\ldots C_{k}\|\leq\rho_{0}^{k}\|x-y\|+\left(\sum_{j =0}^{k-1}\rho_{0}^{j}\right)\mathcal{E}\]1  
since (6) holds for any considered \(\pi_{0}\) (including \(\pi\)), and, by the definition of \(\epsilon\)-lumpability, \(u_{ij}-l_{ij}\leq\epsilon\). Substituting the estimations into (10), we obtain  
\[\|xB_{1}\ldots B_{k}-yC_{1}\ldots C_{k}\|\leq\rho_{0}^{k}\|x-y\|+\left(\sum_{j =0}^{k-1}\rho_{0}^{j}\right)\mathcal{E}\]2 \[\|xB_{1}\ldots B_{k}-yC_{1}\ldots C_{k}\|\leq\rho_{0}^{k}\|x-y\|+\left(\sum_{j =0}^{k-1}\rho_{0}^{j}\right)\mathcal{E}\]3  
proving the Theorem. If the chain happens to be exactly lumpable, then we get a \"cleaner\" result. Let \(\tilde{\pi}_{t}\) be the state distribution of the lumped chain after \(t\) steps and let \(\tilde{\pi}\) be its stationary distribution. For concise description let us apply a frequently used distance concept among probability distributions. If \(p,q\) are two discrete probability distributions on the same set \(S\), then their _total variation distance_\(D_{TV}(p,q)\) is defined as  
\[\|xB_{1}\ldots B_{k}-yC_{1}\ldots C_{k}\|\leq\rho_{0}^{k}\|x-y\|+\left(\sum_{j =0}^{k-1}\rho_{0}^{j}\right)\mathcal{E}\]4  
It is well known that \(0\leq D_{TV}(p,q)\leq 1\) holds for any two probability distributions. It is also clear from the definition of the ergodic coefficient that it is the same as the maximum total variation distance occurring between any two row vectors of the transition matrix. Note that exact lumpability is the special case of \(\epsilon\)-lumpability with \(\epsilon=0\). Therefore, we immediately obtain the following corollary. Corollary 1: _If the Markov chain in Theorem 2 is exactly lumpable, then in the lumped chain for any \(t=0,1,2,\ldots\) the following holds:_  
\[\|xB_{1}\ldots B_{k}-yC_{1}\ldots C_{k}\|\leq\rho_{0}^{k}\|x-y\|+\left(\sum_{j =0}^{k-1}\rho_{0}^{j}\right)\mathcal{E}\]5_where \(\rho=\rho(\bar{P})\) is the ergodic coefficient of the transition matrix \(\bar{P}\) of the lumped chain._  
Proof. : Take the special case \(\epsilon=0\) in Theorem 2.