# Utilizing Network Structure to Accelerate Markov Chain Monte Carlo Algorithms
## 3 Convergence Analysis  
An important concept in [PERSON] chain convergence analysis is the _ergodic coefficient_, see, e.g., [12]. It is also called _coefficient of ergodicity_. Definition 4: **(Ergodic coefficient)** Let \(P=[p_{ij}]\) be an \(n\times n\) matrix. Its _ergodic coefficient_ is defined as  
\[\rho(P)=\frac{1}{2}\max_{i,j}\sum_{k=1}^{n}|p_{ik}-p_{jk}|.\]  
The ergodic coefficient is essentially the largest \(L_{1}\) distance that occurs between different row vectors of the matrix \(P\). That is, in a sense, it captures how diverse are the row vectors of the matrix. The \(1/2\) factor is only for normalization purposes. For stochastic matrices two important properties of the ergodic coefficient are the following [12]:  
1. \(0\leq\rho(P)\leq 1\)
2. \(\rho(AB)\leq\rho(A)\rho(B)\)  
The importance of the ergodic coefficient lies in its relationship to the convergence rate of the Markov chain. It is well known that the convergence rate is determined by the second largest eigenvalue of the transition matrix (that is, the eigenvalue which has the largest absolute value less than 1), see, e.g., [6]. If this eigenvalue is denoted by \(\lambda_{1}\), then the convergence to the stationary distribution happens at a rate of \(O(\lambda_{1}^{t})\), where \(t\) is the number of steps, see [12]. It is also known [12] that the ergodic coefficient is always an upper bound on this eigenvalue, it satisfies \(\lambda_{1}\leq\rho(P)\leq 1\). Therefore, the distance to the stationary distribution is also bounded by \(O(\rho(P)^{t})\). Thus, the smaller is the ergodic coefficient, the faster convergence we can expect. Of course it only provides any useful bound if \(\rho(P)<1\). If \(\rho(P)=1\) happens to be the case, then it does not directly provide a useful bound on the convergence rate, since then \(\rho(P)^{t}\) remains \(1\). In this situation a possible way out is considering the \(k\)-step transition matrix \(P^{k}\) for some constant integer \(k\). If \(k\) is large enough, then we can certainly achieve \(\rho(P^{k})<1\), since it is known [12] that \(\lim_{k\to\infty}\rho(P^{k})=0\). Now we are ready to present our main result, which is a bound on how fast will an \(\epsilon\)-lumpable Markov chain converge to its stationary distribution on the sets that are in the partition, which is used in defining the \(\epsilon\)-lumpability of the chain. We are going to discuss the applicability of the result in the next section. Theorem 2: _Let \(\epsilon\geq 0\) and \(\mathcal{M}=(S,P)\) be an irreducible, aperiodic Markov chain with stationary distribution \(\pi\). Assume the chain is \(\epsilon\)-lumpable with respect to a partition \(\mathcal{Q}=\{A_{1},\ldots,A_{m}\}\) of \(S\). Let \(\rho\) be any upper bound on the ergodic coefficient of the lower transition matrix \(L\) (Definition 3), that is, \(\rho(L)\leq\rho\). Let \(\pi_{0}\) be any initial probability distribution on \(S\), such that \(\mathrm{P}(X_{t}\in A_{i})>0\) holds for any \(i\), and \(t=0,1,2,\ldots\), whenever the chain starts from \(\pi_{0}\). Then for every \(t\geq 1\) the following estimation holds:_  
\[\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}\]  
_assuming \(\rho+\epsilon m/2<1\)._  
Remark:Recall that the parameter \(\epsilon\) quantifies how much the Markov chain deviates from the ideal lumpable case, see Definition 2. In the extreme case, when \(\epsilon=1\), every Markov chain satisfies the definition. This places an\"upward pressure\" on \(\epsilon\): the larger it is, the broader is the class of Markov chains to which \(\epsilon\)-lumpability applies. On the other hand, a downward pressure is put on \(\epsilon\) by Theorem 2: the convergence bound is only meaningful, if \(\rho+\epsilon m/2<1\) holds. This inequality can be checked for any particular \(\epsilon\), since it is assumed that \(\rho\) and \(m\) are known parameters. Furthermore, the smaller is \(\epsilon\), the faster is the convergence.