# Utilizing Network Structure to Accelerate Markov Chain Monte Carlo Algorithms
## 3 Convergence Analysis
Therefore, the best value of \(\epsilon\) is the smallest value which still satisfies Definition 2 for the considered state partition. For the proof of Theorem 2 we need a lemma about stochastic vectors and matrices (Lemma 3.4 in [13], see also [14]):  
**Lemma 1**. : (Hartfiel [13; 14]) _Let \(x,y\) be \(n\)-dimensional stochastic vectors and \(B_{1},\ldots,B_{k};\ C_{1},\ldots,C_{k}\) be \(n\times n\) stochastic matrices. If \(\rho(B_{i})\leq\rho_{0}\) and \(\rho(C_{i})\leq\rho_{0}\) for all \(i,\ 1\leq i\leq k\), then_  
\[\|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}\]  
_where \(\mathcal{E}=\max_{i}\|B_{i}-C_{i}\|.\) The vector norm used is the \(L_{1}\)-norm \(\|x\|=\sum_{i=1}^{n}|x_{i}|\) and the matrix norm is_  
\[\|A\|=\sup_{z\
eq 0}\frac{\|zA\|}{\|z\|}=\max_{i}\sum_{j=1}^{n}|a_{ij}|\]  
_for any \(n\times n\) real matrix \(A=[a_{ij}]\)._  
Lemma 1 can be proved via induction on \(k\), see [13; 14]. Now, armed with the lemma, we can prove our theorem. Proof of Theorem 2.: Let \(\pi_{0}\) be an initial state distribution of the Markov chain \(\mathcal{M}\), let \(\pi_{t}\) be the corresponding distribution after \(t\) steps and \(\pi=\lim_{t\to\infty}\pi_{t}\) be the (unique) stationary distribution of \(\mathcal{M}\). For a set \(A\subseteq S\) of states the usual notations \(\pi_{t}(A)=\mathrm{P}(X_{t}\in A),\ \pi(A)=\lim_{t\to\infty}\pi_{t}(A)\) are adopted. Using the sets \(A_{1},\ldots,A_{m}\) of the partition \(\mathcal{Q}\), let us define the stochastic vectors  
\[\tilde{\pi}_{t}=\big{(}\pi_{t}(A_{1}),\ldots,\pi_{t}(A_{m})\big{)} \tag{3}\]  
for \(t=0,1,2,\ldots\) and the \(m\times m\) stochastic matrices  
\[\tilde{P}_{t}(\pi_{0})=[p_{t}^{(\pi_{0})}(i,j)]=\big{[}\mathrm{P}(X_{t+1}\in A _{j}\mid X_{t}\in A_{i})\big{]} \tag{4}\]  
for \(t=1,2,\ldots\). Let us call them aggregated state distribution vectors and aggregated transition matrices, respectively. Note that although the entries in (4) involve only events of the form \(\{X_{t}\in A_{k}\}\), they may also depend on the detailed state distribution within these sets, which is in turn determined by the initial distribution \(\pi_{0}.\) In other words, if two different initial distributions give rise to the same probabilities for the events \(\{X_{t}\in A_{k}\}\) for some \(t\), they may still result in different conditional probabilities of the form \(\mathrm{P}(X_{t+1}\in A_{j}\mid X_{t}\in A_{i})\), since the chain is not assumed lumpable in the ordinary sense. This is why the notations \(\tilde{P}_{t}(\pi_{0}),\ p_{t}^{(\pi_{0})}(i,j)\) are used. Also note that the conditional probabilities are well defined for any initial distribution allowed by the assumptions of the lemma, since then \(\mathrm{P}(X_{t}\in A_{i})>0\). For any fixed \(t\) the events \(\{X_{t}\in A_{i}\},\ i=1,\ldots,m\), are mutually exclusive with total probability \(1\), therefore, by the law of total probability,  
\[\mathrm{P}(X_{t+1}\in A_{j})=\sum_{i=1}^{m}\mathrm{P}(X_{t+1}\in A_{j}\mid X_ {t}\in A_{i})\mathrm{P}(X_{t}\in A_{i}),\ \ \ \ \ j=1,\ldots,m\]  
holds. This implies \(\tilde{\pi}_{t+1}=\tilde{\pi}_{t}\tilde{P}_{t}(\pi_{0})\), from which  
\[\tilde{\pi}_{t}=\tilde{\pi}_{0}\tilde{P}_{1}(\pi_{0})\cdot\ldots\cdot\tilde{P} _{t}(\pi_{0}) \tag{5}\]  
follows. We next show that for any \(t=1,2,\ldots\) the matrix \(\tilde{P}_{t}(\pi_{0})\) falls between the lower and upper transition matrices, i.e., \(L\leq\tilde{P}_{t}(\pi_{0})\leq M\) holds.