# Utilizing Network Structure to Accelerate Markov Chain Monte Carlo Algorithms
## 1 Introduction  
The Markov Chain Monte Carlo (MCMC) method is one of the most frequently used algorithms to solve hard counting, sampling and optimization problems. This is relevant for many areas, including complex networks, physics, communication systems, computational biology, optimization, data mining, big data analysis, forecast problems, prediction tasks, and innumerable others. The success and influence of the method is shown by the fact that it has been selected as one of the top 10 of all algorithms in the 20 th century, see [1]. The MCMC algorithm also plays an important role in large, complex networks. In this paper, building on our earlier conference presentations [2; 3], we consider the following regularly occurring application of the MCMC method:  
Consider a very large graph \(G\), with node set \(S\), and let \(A\subseteq S\) be a subset of the nodes. We would like to estimate the relative size of \(A\), that is, the goal is to obtain a good estimate of the value  
\[p=\frac{|A|}{|S|} \tag{1}\]  
More generally, if a random walk is considered on the graph, with stationary distribution \(\pi\), then we would like to estimate \(\pi(A)\), the stationary probability of being in \(A\). In the special case when \(\pi\) is the uniform distribution, we get back the formula (1). If we can take random samples from \(S\), according to the stationary distribution, then an obvious estimate with good properties is the relative frequency of the event that the sample falls in \(A\)Unfortunately, in most nontrivial cases of interest, this sampling task is not feasible. The reason is that often the large set \(S\) is defined _implicitly_. Examples are the set of all cliques in a graph, or the set of all feasible solutions to an optimization problem, and many others. No efficient general method is known to sample uniformly at random from such complex sets. An important application in telecommunication networks is to estimate blocking probabilities, see [4; 5]. More generally, if we have a large system, with an enormous state space, we may want to estimate that the actual state falls in a specific subset. For example, if the state space consists of all possible load values of the network links, which leads to a state space of astronomical size, we may want to know what the probability is that at most \(k\) links are overloaded, for some value of \(k\). At this point, the MCMC does a very good service. If we define a Markov chain in which the states are the elements of \(S\) and the transitions are based on simple local operations, then we can very often obtain a Markov chain with uniform, or some other simple stationary distribution over \(S\). Then, if we run this chain long enough so that it gets close to the stationary distribution, then the state where we stop the chain will be a good approximation of a random sample over \(S\), distributed according to the stationary distribution. Then by repeating the process sufficiently many times, and by counting the relative frequency that the random sample falls in \(A\), we can get a good estimate of the probability measure of \(A\). The key difficulty is, however, that we should run the chain long enough to get sufficiently close to the stationary distribution. This time is often referred to as _mixing time_[6]. If the mixing time grows only polynomially with the size of the problem, e.g. with the size of the graph, then we say that the chain is _rapidly mixing_. Unfortunately, in many cases of interest the mixing time grows exponentially with the problem parameters, so in many important cases the Markov chain is mixing very slowly. What we are interested in is whether it is possible to speed up the running time. It is clear that if we want to estimate the size of _any_ possible subset, then we really need to get close to the stationary distribution, since only this distribution can guarantee that the probability of the random state falling in the set is really the relative size of the set.