Paper Info
Title
Sharp Mixing Time Bounds for Sampling Random Surfaces
Abstract
We analyze the mixing time of a natural local Markov Chain (Gibbs sampler) for two commonly studied models of random surfaces: (i) discrete monotone surfaces with "almost planar" boundary conditions and(ii) the one-dimensional discrete Solid-on-Solid (SOS)model. In both cases we prove the first almost optimal bounds. Our proof is inspired by the so-called "meancurvature" heuristic: on a large scale, the dynamics should approximate a deterministic motion in which each point of the surface moves according to a drift proportional to the local inverse mean curvature radius. Key technical ingredients are monotonicity, coupling and an argument due to D. Wilson [17] in the framework of lozenge tiling Markov Chains. The novelty of our approach with respect to previous results consists in proving that, with high probability, the dynamics is dominated by a deterministic evolution which follows the mean curvature prescription. Our method works equally well for both models despite the fact that their equilibrium maximal deviations from the average height profile occur on very different scales.
Year
DOI
Venue
2011
10.1109/FOCS.2011.47
FOCS
Keywords
Field
DocType
lozenge tiling markov chains,deterministic evolution,sharp mixing time bounds,local inverse mean curvature,average height profile,discrete monotone surface,sampling random surfaces,gibbs sampler,one-dimensional discrete solid-on-solid,natural local markov chain,mean curvature prescription,deterministic motion,lattices,mixing time,couplings,markov chain,markov process,solid modeling,markov processes,physics,monte carlo markov chain,mean curvature,boundary condition,boundary conditions,sampling methods
Boundary value problem,Discrete mathematics,Monotonic function,Combinatorics,Markov process,Markov chain,Mean curvature,Spectral gap,Monotone polygon,Mathematics,Gibbs sampling
Conference
ISSN
Citations 
PageRank 
0272-5428
0
0.34
References 
Authors
0
3
Name
Order
Citations
PageRank
Pietro Caputo132.15
Fabio Martinelli241.64
Fabio Lucio Toninelli300.68