Thomas Hayes, Cristopher Moore

Paper #: 14-07-023

We prove a new lower bound on the critical density pc of the hard disk model, i.e., the density below which it is possible to efficiently sample random configurations of n non-overlapping disks in a unit torus. We use a classic Markov chain which moves one disk at a time, but with an improved path coupling analysis. Our main tool is an optimized metric on neighboring pairs of configurations, i.e., configurations that differ in the position of a single disk: we define a metric that depends on the difference in these positions, and which approaches zero continuously as they coincide. This improves the previous lower bound pc ≥ 1/8 to pc ≥ 0.154.