Papers Published
Abstract:
In the hard core gas model from statistical
physics, the
goal is to sample from a weighted
distribution of
independent sets of a graph. The probability
of choosing
a particular independent set is proportional
to a
parameter k raised to the size of the
independent set.
Currently, a Markov chain of Dyer and
Greenhill is known
to be mixing over the widest ranges of k. In
this paper,
it is shown how to use bounding chains and
coupling from
the past to generate exactly random samples
from the hard
core gas model using the Dyer/Greenhill chain.