Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#14018] of Mark Huber

Papers Published

  1. Mark L. Huber, A bounding chain for Swendsen-Wang, Random Structures and Algorithms, vol. 22 no. 1 (2002), pp. 53--59
    (last updated on 2007/09/10)

    The greatest drawback to Monte Carlo Markov chain methods is lack of knowledge of the mixing time of the chain. The use of bounding chains solves this difficulty for some chains by giving theoretical and experimental upper bounds on the mixing time. Moreover, when used with methodologies such as coupling from the past, bounding chains allow the user to take samples drawn exactly from the stationary distribution without knowledge of the mixing time. Here we present a bounding chain for the Swendsen-Wang process. The Swendsen-Wang bounding chain allows us to efficiently obtain exact samples from the ferromagnetic Q-state Potts model for certain classes of graphs. Also, by analyzing this bounding chain we show that Swendsen-Wnag is rapidly mixing over a larger range of parameters than was known previously.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320