# Utilizing Network Structure to Accelerate Markov Chain Monte Carlo Algorithms
## 2 Aggregation in Markov Chains  
We assume the reader is familiar with the basic concepts of Markov chains. We adopt the notation that a Markov chain \(\mathcal{M}\) is given by a set \(S\) of states and by a transition probability matrix \(P\), so we write \(\mathcal{M}=(S,P)\). This notation does not include the initial distribution, because it is assumed arbitrary. Let us first define the concept _lumpability_ of a Markov chain. Informally, as mentioned in the Introduction, a chain is lumpable if its states can be aggregated into larger subsets of \(S\), such that the aggregated (lumped) chain remains a Markov chain with respect to the set-transition probabilities (i.e., it preserves the property that the future depends on the past only through the present). Note that this is generally not preserved by _any_ partition of the state space. Let us introduce now the formal definition. Definition 1: (Lumpability of Markov chain) _Let \(\mathcal{M}=(S,P)\) be a Markov chain. Let \(\mathcal{Q}=\{A_{1},\ldots,A_{m}\}\) be a partition of \(S\). The chain \(\mathcal{M}\) is called _lumpable_ with respect to the partition \(\mathcal{Q}\) if for any initial distribution the relationship  
\[\Pr(X_{t}\in A_{j}\,|\,X_{t-1}\in A_{i_{1}},\ldots,X_{t-k}\in A_{i_{k}})=\Pr(X _{t}\in A_{j}\,|\,X_{t-1}\in A_{i_{1}}) \tag{2}\]  
holds for any \(t,k,j,i_{1},\ldots,i_{k}\), whenever these conditional probabilities are defined (i.e., the conditions occur with positive probability). If the chain is lumpable, then the state set of the lumped chain is \(\mathcal{Q}\) and its state transition probabilities are defined by  
\[\hat{p}_{ij}=\Pr(X_{t}\in A_{j}\,|\,X_{t-1}\in A_{i})\]  
Checking whether a Markov chain is lumbable would be hard to do directly from the definition. That is why it is useful to have the following characterization, which is fundamental result on the lumpability of Markov chains, see [7]. For simple description, we use the notation \(p(x,A)\) to denote the probability that the chain moves into a set \(A\subseteq S\) in the next step, given that currently it is in the state \(x\in S\). Note that \(x\) itself may or may not be in \(A\). Theorem 2.1: (Necessary and sufficient condition for lumpability, see [7]) _A Markov chain \(\mathcal{M}=(S,P)\) is lumpable with respect to a partition \(\mathcal{Q}=\{A_{1},\ldots,A_{m}\}\) of \(S\) if and only if for any \(i,j\) the value of \(p(x,A_{j})\) is the same for every \(x\in A_{i}\). These common values define the transition probabilities \(\hat{p}(A_{i},A_{j})\) for the lumped chain, which is a Markov chain with state set \(\mathcal{Q}\) and state transition probabilities_  
\[\hat{p}(A_{i},A_{j})=p(x,A_{j})=\Pr(X_{t}\in A_{j}\,|\,X_{t-1}\in A_{i})\]  
_where \(x\) is any state in \(A_{i}\)._  
Informally, the condition means that a move from a set \(A_{i}\in\mathcal{Q}\) to another set \(A_{j}\in\mathcal{Q}\) happens with probability \(p(x,A_{j})\), no matter which \(x\in A_{i}\) is chosen. That is, any \(x\in A_{i}\) has the property that the probability of moving from this \(x\) to the set \(A_{j}\) in the next step is the same for every \(x\in A_{i}\). The sets \(A_{i},A_{j}\) are partition classes of \(\mathcal{Q}\). We also allow \(i=j\), so they may coincide. Whenever our Markov chain is lumpable, we can reduce the number of states by the above aggregation, and it is usually advantageous for faster convergence (a specific bound will be proven in Section 3). It is worth noting that lumpability is a rather special property, and one has to be quite lucky to encounter a real-life Markov chain that actually has this property. Sometimes it happens (see, e.g., the example in the Introduction about PageRank computation), but it is not very common. Therefore, let us now relax the concept of lumpability to broaden the family of the considered Markov chains. The extended condition, as explained below, is called _quasi-lumbability_.