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

Math @ Duke



Publications [#41201] of Mark Huber

Papers Published

  1. M. Huber, G. Reinert, The Stationary Distribution in the Antivoter Model: Exact Sampling and Approximations, in Stein's Method: Expository Lectures and Applications (2004), pp. 79--94
    (last updated on 2005/09/11)

    The antivoter model is a Markov cahin on regular graphs which has a unique stationary distribution, but is not reversible. This makes the stationary distribution difficult to describe. Despite the fact that in general nothing is known about the stationary distribution other than it exists and is unique, we present a method for sampling exactly from this distirubiton. The method has running time O(n^3r/c), where n is the number of nodes in the graph, c is the size of the minimum cut in the graph, and r is the degree of each node in the graph. We also show that the original chain has O(n^3r/c) mixing time. For the antivoter model on the complete graph we derive a closed form solution for the stationary distribution. Moreover, we bound the total variation distance between the stationary distribution for the antivoter model on multipartite graph and the stationary distirubiton on the complete graph.
ph: 919.660.2800
fax: 919.660.2821

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