Faster mixing and small bottlenecks (Q863483)

A new bound on the mixing time of Markov chain (MC) is proved by considering the conductance of its connected subsets. A finite MC is a digraph \(G\) on vertex set \(V_n=\{1,\dots,n\}\) with transition matrix \(P=\| p_{ij}\| _{i,j\in V_n}\) such that \(p_{ij}>0\) precisely iff \(ij\) is an edge of \(G\). MC is assumed to be ergodic and reversible, i.e. there exists \(\lim_{t \to \infty} P^t=\pi>0\) and \(\pi(i) p_{ij}=\pi(j) p_{ji}\) for all \(i,j \in V_n\). The mixing time is defined as \[ T_{\text{mix}}=\sup_i \min \{t:d_{\text{TV}}(P^t_i,\pi)<1/e\}, \] where \(d_{\text{TV}}\) stands for the total variation distance and \(P^t_i\) is the probability distribution on MC at the time step \(t\) given that the initial state was \(i\). In the article the lazy MC is considered. The lazy MC stays at each time step at current state with probability 1/2 and takes a step of the original MC with probability 1/2. This does not change the limit distribution and at most doubles the mixing time. For a set \(S \subset V_n\) the conductance of \(S\) is defined as \[ \Phi(S)=\frac{\sum_{i\in S, j\notin S} \pi(i)p_{ij}}{\pi(S)\pi(V_n \setminus S)} \] and \(\Phi(p)= \min \Phi(S)\), s.t. \(S\) is connected and \(p/2 \leq \pi(S) \leq p\). For an ergodic reversible lazy MC the following upper bound is proved \[ T_{\text{mix}} \leq C \sum_{j=1}^{\log \pi_{\min}^{-1}} \Phi^{-2}(2^{-j}), \] where the constant \(C\) does not depend on the chain and \(\pi_{\min} = \min_{i \in V_n} \pi(i)\).