# Utilizing Network Structure to Accelerate Markov Chain Monte Carlo Algorithms
## 4 Numerical Demonstration  
Let us consider the following situation. Let \(\mathcal{M}\) be a Markov chain with state space \(S\). Assume we want to estimate the stationary measure \(\pi(A)\) of a subset \(A\subseteq S\). A practical example of such a situation is to estimate the probability that there is at most \(k\) blocked links, for some constant \(k\), in a large communication network. Here the state space is the set \(S\) of all possible states of all the links. The state of a link is the current traffic load of the link, and it is blocked if the load is equal to the link capacity, so it cannot accept more traffic. Within this state space the considered subset \(A\) is the subset of states in which among all links at most \(k\) are blocked. Therefore, the relevant partition of \(S\) is \(\{A,S-A\}\). This is motivated by real-world application, since the number of blocked links critically affects network performance. When considering the loss of traffic due to blocking, the models of these networks are often called _loss networks_. For detailed background information on loss networks, see [4; 15; 16]. Of course, we can also consider other events in the network. For example, at most a given percentage of traffic is blocked, without specifying how many links are involved in the blocking. In many cases we are unable to directly compute \(\pi(A)\). This task frequently has enormous complexity, for the theoretical background see [5]. Then a natural way to obtain an estimation of \(\pi(A)\) is simulation. That is, we run the chain from some initial state, stop it after \(t\) steps and check out whether the stopping state is in \(A\) or not. Repeating this experiment a large enough number of times, the relative frequency of ending up in \(A\) will give a good estimation of the measure of \(\pi_{t}(A)\). If \(t\) is chosen such that \(\pi_{t}\) is close enough to the stationary distribution \(\pi\) for any initial state, then we also obtain a good estimation for \(\pi(A)\). This is the core idea of the Markov Chain Monte Carlo approach. Unfortunately, Markov chains with large state space often converge extremely slowly. Therefore, we may not get close enough to \(\pi\) after a reasonable number of steps. In such a case our result can do a good service, at least when the chain satisfies some special requirements. As an example, let us consider the following case. First we examine it using our bounds, then we also study it through numerical experiments. Assume the set \(A\subseteq S\) has the property that its elements behave similarly in the following sense: for any state \(x\in A\) the probability to move out of \(A\) in the next step, given that the current state is \(x\), is _approximately_ the same. Similarly, if \(x\
otin A\), then moving into \(A\) in the next step from the given \(x\) has approximately the same probability for any \(x\
otin A\). To make this assumption formal, assume there are values \(p_{0},q_{0},\epsilon\), such that the following conditions hold:  
1. If \(x\in A\) then \(p_{0}\leq p(x,\bar{A})\leq p_{0}+\epsilon\) where \(\bar{A}=S-A\). This means, the smallest probability of moving out of \(A\) from any state in \(x\in A\) is at least \(p_{0}\), and the largest such probability is at most \(p_{0}+\epsilon\). 2. If \(x\in\bar{A}\) then \(q_{0}\leq p(x,A)\leq q_{0}+\epsilon\). Similarly to the first case, this means that the smallest probability of moving into \(A\) from any state in \(x\
otin A\) is at least \(q_{0}\), and the largest such probability is at most \(q_{0}+\epsilon\). (We choose \(\epsilon\) such that it can serve for this purpose in both directions.) 3. To avoid degenerated cases, we require that the numbers \(p_{0},q_{0},\epsilon\) satisify \(p_{0}+\epsilon<1\), \(q_{0}+\epsilon<1\) and \(0<p_{0}+q_{0}<1\). The other state transition probabilities (within \(A\) and \(\overline{A}\)) can be completely arbitrary, assuming, of course, that at any state the outgoing probabilities must sum up to \(1\). Let us now apply our main result, Theorem 2, for this situation.