Abstract | ||
---|---|---|
We prove a new lower bound on the critical density $\rho_c$ 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 $\rho_c \ge 1/8$ to $\rho_c \ge 0.154$. |
Year | Venue | Field |
---|---|---|
2014 | CoRR | Discrete mathematics,Combinatorics,Coupling,Upper and lower bounds,Markov chain,Torus,Mathematics |
DocType | Volume | Citations |
Journal | abs/1407.1930 | 1 |
PageRank | References | Authors |
0.62 | 5 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Thomas P. Hayes | 1 | 659 | 54.21 |
Cristopher Moore | 2 | 1765 | 160.55 |