# Utilizing Network Structure to Accelerate Markov Chain Monte Carlo Algorithms
## 1 Introduction
On the other hand, if we only want to estimate the relative size of a _specific_ subset \(A\), then it is enough for us if we reach a distribution in which the measure of \(A\) is close to the stationary measure, but this does not have to hold for every other set. In other words, if \(\pi_{t}\) denotes the state distribution after \(t\) steps and \(\pi\) is the stationary distribution, then we want to choose \(t\) such that \(|\pi_{t}(A)-\pi(A)|\) is small, but the same does not have to hold for all other sets. This makes it possible to reduce the required value of \(t\), that is, to speed up the algorithm. In this paper we investigate under what conditions it is possible to obtain such a speed-up. The main result is that the structure of the chain, that is, the _network structure_, can significantly help, if it has some special properties. Specifically, if the Markov chain is close to a so called _lumpable_ chain, then remarkable speedup is possible. In other words, in this case we can indeed capitalize on the particular network structure to accelerate the method. Below we informally explain what the concept of lumpability means. The formal definition will follow in the next section. The concept of lumpability stems from the following observation: it is very useful if the state space can be _partitioned_ such that the states belonging to the same partition class \"behave the same way,\" in the sense defined formally in the next section. This is the concept of _lumpability_[7]. Informally speaking, it means that some sets of states can be lumped together (aggregated) and replaced by a single state, thus obtaining a Markov chain which has a much smaller state space, but its essential behavior is the same as the original. In some cases, the lumpability of the Markov chain can have a very significant effect on the efficiency of the model. A practical example is discussed in [8; 9], where the authors present a fast algorithm to compute the PageRank vector, which is an important part of search engine algorithms in the World Wide Web. The PageRank vector can be interpreted as the stationary distribution of a Markov chain. This chain has a huge state space, yielding excessive computation times. This Markov chain, however, is lumpable. Making use of the lumpability, the computation time can be reduced to as low as 20% of the original, according to the experiments presented in [8]. Unfortunately, it happens relatively rarely that the Markov chain satisfies the definition of lumpability _exactly_. This motivates the concept of _quasi-lumpability_[10; 11]. Informally, a Markov chain is quasi-lumpable if its transition matrix is obtainable by a small _perturbation_ from a matrix that exactly satisfies the lumpability condition (see the formal definition in the next section). In this paper we are interested in the following problem, which is often encountered in applications: how long do we have to run the Markov chain if we want to get close to the stationary distribution within a prescribed error? While the general question is widely discussed in the literature (see, e.g., [6; 12]), we focus here on a less researched special case: how much gain can the convergence speed enjoy, if we can capitalize on the special structure of _quasi-lumpability_.