Fast and Slim Lifted Markov Chains

Metropolis-Hasting method allows for designing a reversible Markov chain P on a given graph G for a target stationary distribution π. Such a Markov chain may suffer from its slow mixing time due to reversibility. Diaconis, Holmes and Neal (1997) for the ring-like chain P, and later Chen, Lovasz and Pak (2002) for an arbitrary chain P provided an explicit construction of a non-reversible Markov chain via lifting P so that its mixing time is essentially 1/Φ(P), whereΦ(P) is the conductance of P. Hence it leads to the reduction of the mixing time up to its square root. However, the construction of Chen et. al. results in expansion of size of the underlying graph during lifting; it affects the performance of algorithms (such as samplings or distributed linear dynamics) based on Markov chains. Therefore, motivated to reduce the size of the lifted chain, we provide a new lifting for an arbitrary chain based on expander graphs, which results in reduction of size up to Ω(n) (n is the number of states of P) with essentially the same mixing time. The lifting, though allows for reduction in the mixing time, cannot be reduced beyond 1/Φ(P), given a starting Markov chain P. Therefore, if P is ill-designed to begin with, 1/Φ(P) can be large. To overcome this limitation, we introduce a new notion of lifting, which we call pseudo-lifting. For an arbitrary chain P and a diameter D of its underlying graph, we provide a simple pseudo-lifting with mixing time O(D) and size O(nD) – this is the fastest possible mixing time for any Markov chain up to constant for any given underlying graph. Next, we provide a hierarchical pseudo-lifting which allows for optimizing the size of the lifted chain using geometry of its underlying graph. We exhibit the strength of this construction for graphs with constant doubling dimension ρ to design a fast mixing pseudo-lifted Markov chain with size O ³ Dn1− 1 ρ+1 ´ , which might be much larger without its geometry.