Papers Published
Abstract:
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.