The Curveball algorithm is a variation on well-known switch-based Markov chain approaches for uniformly sampling binary matrices with fixed row and column sums. Instead of a switch, the Curveball algorithm performs a so-called binomial trade in every iteration of the algorithm. Intuitively, this could lead to a better convergence rate for reaching the stationary (uniform) distribution in certain cases. Some experimental evidence for this has been given in the literature. In this note we give a spectral gap comparison between two switch-based chains and the Curveball chain. In particular, this comparison allows us to conclude that the Curveball Markov chain is rapidly mixing whenever one of the two switch chains is rapidly mixing. Our analysis directly extends to the case of sampling binary matrices with forbidden entries (under the assumption of irreducibility). This in particular captures the case of sampling simple directed graphs with given degrees. As a by-product of our analysis, we show that the switch Markov chain of the Kannan-Tet ali-Vempala conjecture only has non-negative eigenvalues if the sampled binary matrices have at least three columns. This shows that the Markov chain does not have to be made lazy, which is of independent interest. We also obtain an improved bound on the smallest eigenvalue for the switch Markov chain studied by Greenhill for uniformly sampling simple directed regular graphs.
All the results regarding rapid mixing mentioned above rely on the multi-commodity flow method developed by Sinclair @cite_0 . In this work we omit multi-commodity flow techniques in order to compare the switch and Curveball Markov chains, but rather take a more elementary approach based on comparing eigenvalues of transition matrices. One seeming advantage of the eigenvalue comparison is that it allows us to compare the switch and Curveball chains for arbitrary fixed row and column sums. Our spectral gap comparisons are special cases of the classical comparison framework developed largely by Diaconis and Saloff-Coste and is based on so-called Dirichlet form comparisons of Markov chains, see, e.g., @cite_20 @cite_11 , and also Quastel @cite_1 . See also the expository paper by Dyer, Goldberg, Jerrum and Martin @cite_16 . As the stationary distributions are the same for all our Markov chains, we use a more direct, but equivalent, framework based on positive semidefiniteness. We briefly elaborate on this in Appendix for the interested reader.
@cite_1 @cite_0 @cite_16 @cite_20 @cite_11
2033281046 2167877620 2136258494 1988307095
The paper is concerned with tools for the quantitative analysis of finite Markov chains whose states are combinatorial structures. Chains of this kind have algorithmic applications in many areas, including random sampling, approximate counting, statistical physics and combinatorial optimisation. The efficiency of the resulting algorithms depends crucially on the mixing rate of the chain, i.e. , the time taken for it to reach its stationary or equilibrium distribution. The paper presents a new upper bound on the mixing rate, based on the solution to a multicommodity flow problem in the Markov chain viewed as a graph. The bound gives sharper estimates for the mixing rate of several important complex Markov chains. As a result, improved bounds are obtained for the runtimes of randomised approximation algorithms for various problems, including computing the permanent of a 0–1 matrix, counting matchings in graphs, and computing the partition function of a ferromagnetic Ising system. Moreover, solutions to the multicommodity flow problem are shown to capture the mixing rate quite closely: thus, under fairly general conditions, a Markov chain is rapidly mixing if and only if it supports a flow of low cost. In this paper we consider a simple Markov chain for bipartite graphs with given degree sequence on @math vertices. We show that the mixing time of this Markov chain is bounded above by a polynomial in @math in case of half-regular degree sequence. The novelty of our approach lies in the construction of the multicommodity flow in Sinclair's method. The switch chain is a well-known Markov chain for sampling directed graphs with a given degree sequence. While not ergodic in general, we show that it is ergodic for regular degree sequences. We then prove that the switch chain is rapidly mixing for regular directed graphs of degree @math , where @math is any positive integer-valued function of the number of vertices. We bound the mixing time by bounding the eigenvalues of the chain. A new result is presented and applied to bound the smallest (most negative) eigenvalue. This result is a modification of a lemma by Diaconis and Stroock [ Annals of Applied Probability 1991], and by using it we avoid working with a lazy chain. A multicommodity flow argument is used to bound the second-largest eigenvalue of the chain. This argument is based on the analysis of a related Markov chain for undirected regular graphs by Cooper, Dyer and Greenhill [ Combinatorics, Probability and Computing 2007], but with significant extension required. We consider two problems: randomly generating labeled bipartite graphs with a given degree sequence and randomly generating labeled tournaments with a given score sequence. We analyze simple Markov chains for both problems. For the first problem, we cannot prove that our chain is rapidly mixing in general, but in the near-regular case, i.e., when all the degrees are almost equal, we give a proof of rapid mixing. Our methods also apply to the corresponding problem for general (nonbipartite) regular graphs, which was studied earlier by several researchers. One significant difference in our approach is that our chain has one state for every graph (or bipartite graph) with the given degree sequence; in particular, there are no auxiliary states as in the chain used by Jerrum and Sinclair. For the problem of generating tournaments, we are able to prove that our Markov chain on tournaments is rapidly mixing, if the score sequence is near-regular. The proof techniques we use for the two problems are similar. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14: 293–308, 1999