Statistical Physics and Statistical Computing: A Critical Link

The main purpose of this chapter is to demonstrate the fruitfulness of cross-fertilization between statistical physics and statistical computation, by focusing on the celebrated Swendsen-Wang algorithm for the Ising model and its recent perfect sampling implementation by Huber. In particular, by introducing Hellinger derivative as a measure of instantaneous changes of distributions, we provide probabilistic insight into the algorithm's critical slowing down at the phase transition point. We show that at or near the phase transition, an infinitesimal change in the temperature parameter of the Ising model causes an astronomical shift in the underlying state distribution. This finding suggests an interesting conjecture linking the critical slowing down in coupling time with the grave instability of the system as characterized by the Hellinger derivative (or equivalently, by Fisher information). It also suggests that we can approximate the critical point of the Ising model, a physics quantity, by monitoring the coupling time of Huber's bounding chain algorithm, an algorithmic quantity. This finding might provide an alternative way of approximating criticality of thermodynamic systems, which is typically intractable analytically. We also speculate that whether we can turn perfect sampling from a pet pony into a workhorse for general scientific computation may depend critically on how successful we can engage, in its development, researchers from statistical physics and related scientific fields.