Heat-bath random walks with Markov bases

2016/05/26 by Stanley, Caprice, Windisch, Tobias · 1 citation
#11P21 #Combinatorics (math.CO) #FOS: Mathematics #Primary: 05C81 #Secondary: 37A25 #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.1605.08386

Abstract

Graphs on lattice points are studied whose edges come from a finite set of allowed moves of arbitrary length. We show that the diameter of these graphs on fibers of a fixed integer matrix can be bounded from above by a constant. We then study the mixing behaviour of heat-bath random walks on these graphs. We also state explicit conditions on the set of moves so that the heat-bath random walk, a generalization of the Glauber dynamics, is an expander in fixed dimension.

Cited by

• SAT-sampling for statistical significance testing in sparse contingency tables

Related

• Walking on the Edge and Cosystolic Expansion
• Functions of random walks on hyperplane arrangements
• Random Walks on Dynamic Graphs: Mixing Times, HittingTimes, and Return\n Probabilities
• Random walks on the random graph
• Expanderizing Higher Order Random Walks