Tomorrow I’ll be giving a talk at the Fall Western AMS meeting, at UCLA, in Boelter Hall 2444. The talk is titled “Near-linear time perfect simulation of corrugated surfaces”.
Given a bipartite graph with n nodes, a corrugated surface can be viewed as a vector in [0,1]n such that all nodes in one partition are local maxima, and all the nodes in the other partition are local minima. In order to draw samples from this random landscape, Caracciolo, Rinaldi, and Sportiello (2008) constructed a Markov chain whose stationary distributionwas uniform over the set of corrugated surfaces. They conjectured from experiments that the mixing time of the chain was O(n ln n) for the special case of a square lattice. Here a new Markov chain is presented that provably mixes in O(n ln n) time for all bipartite graphs. Like the Caraccilo, et al. chain, this new chain can also be used with coupling from thepast to obtain samples drawn exactly from the desired distribution. Furthermore, this approach can then be combinedwith randomized cooling schedule methods in order to obtain a 1 + ε approximation (with probability at least 1 – δ) of the corrugated surface volume in time O(n2(ln n)ε-2 ln (1/δ)).