[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content

Algorithms for Hard-Constraint Point Processes via Discretization

  • Conference paper
  • First Online:
Computing and Combinatorics (COCOON 2022)

Abstract

We study the algorithmic applications of a natural discretization for the hard-sphere model and the Widom–Rowlinson model in a region of \(d \)-dimensional Euclidean space \( \mathbb {V} \subset \mathbb {R} ^{d}\). These continuous models are frequently used in statistical physics to describe mixtures of one or multiple particle types subjected to hard-core interactions. For each type, particles are distributed according to a Poisson point process with a type-specific activity parameter, called fugacity. The Gibbs distribution over all possible system states is characterized by the mixture of these point processes conditioned that no two particles are closer than some type-dependent distance threshold. A key part in better understanding the Gibbs distribution is its normalizing constant, called partition function.

Our main algorithmic result is the first deterministic approximation algorithm for the partition function of the hard-sphere model and the Widom–Rowlinson model in box-shaped regions of Euclidean space. Our algorithms have quasi-polynomial running time in the volume of the region \(\nu \left( \mathbb {V} \right) \) if the fugacity is below a certain threshold. For the \(d \)-dimensional hard-sphere model with particles of unit volume, this threshold is \(\textrm{e}/2^d \). As the number of dimensions \(d \) increases, this bound asymptotically matches the best known results for randomized approximation of the hard-sphere partition function. We prove similar bounds for the Widom–Rowlinson model. To the best of our knowledge, this is the first rigorous algorithmic result for this model.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 55.99
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 69.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Anari, N., Jain, V., Koehler, F., Pham, H.T., Vuong, T.D.: Entropic independence II: optimal sampling and concentration via restricted modified log-Sobolev inequalities. CoRR abs/2111.03247 (2021). https://arxiv.org/abs/2111.03247

  2. Anari, N., Liu, K., Gharan, S.O.: Spectral independence in high-dimensional expanders and applications to the hardcore model. CoRR abs/2001.00303 (2020). http://arxiv.org/abs/2001.00303

  3. Boublik, T., Nezbeda, I., Hlavaty, K.: Statistical thermodynamics of simple liquids and their mixtures. Fundam. Stud. Eng. Elsevier (1980)

    Google Scholar 

  4. Chen, X., Feng, W., Yin, Y., Zhang, X.: Rapid mixing of Glauber dynamics via spectral independence for all degrees. CoRR abs/2105.15005 (2021). http://arxiv.org/abs/2105.15005

  5. Chen, Z., Liu, K., Vigoda, E.: Rapid mixing of Glauber dynamics up to uniqueness via contraction. CoRR abs/2004.09083 (2020). http://arxiv.org/abs/2004.09083

  6. Chen, Z., Liu, K., Vigoda, E.: Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion. In: STOC, pp. 1537–1550. ACM (2021). https://doi.org/10.1145/3406325.3451035

  7. Friedrich, T., Göbel, A., Katzmann, M., Krejca, M., Pappik, M.: Using random graphs to sample repulsive gibbs point processes with arbitrary-range potentials. CoRR abs/2204.01793 (2022). http://arxiv.org/abs/2204.01793

  8. Friedrich, T., Göbel, A., Krejca, M., Pappik, M.: A spectral independence view on hard spheres via block dynamics. In: Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP), vol. 198, pp. 66:1–66:15 (2021). https://doi.org/10.4230/LIPIcs.ICALP.2021.66

  9. Galanis, A., Ge, Q., Stefankovic, D., Vigoda, E., Yang, L.: Improved inapproximability results for counting independent sets in the hard-core model. Random Struct. Algorithms 45(1), 78–110 (2014). https://doi.org/10.1002/rsa.20479

    Article  MathSciNet  MATH  Google Scholar 

  10. Guo, H., Jerrum, M.: Perfect simulation of the hard disks model by partial rejection sampling. CoRR abs/1801.07342 (2018). https://arxiv.org/abs/1801.07342v2

  11. Hansen, J.P., McDonald, I.R.: Theory of Simple Liquids. Academic Press, 4th edn. (2013). https://doi.org/10.1016/B978-0-12-387032-2.00013-1

  12. Helmuth, T., Perkins, W., Regts, G.: Algorithmic Pirogov-Sinai theory. In: Proceedings of the 51st Annual ACM Symposium on the Theory of Computing (STOC), pp. 1009–1020 (2019). https://doi.org/10.1145/3313276.3316305

  13. Jenssen, M., Joos, F., Perkins, W.: On the hard sphere model and sphere packings in high dimensions. Forum Math. Sigma 7, e1 (2019). https://doi.org/10.1017/fms.2018.25

    Article  MathSciNet  MATH  Google Scholar 

  14. Jerrum, M., Valiant, L.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Sci. 43, 169–188 (1986). https://doi.org/10.1016/0304-3975(86)90174-X

    Article  MathSciNet  MATH  Google Scholar 

  15. Kendall, W.S.: Perfect simulation for the area-interaction point process. In: Accardi, L., Heyde, C.C. (eds.) Probability Towards 2000. Lecture Notes in Statistics, vol. 128, pp. 218–234. Springer, Cham (1998). https://doi.org/10.1007/978-1-4612-2224-8_13

  16. Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H., Teller, E.: Equation of state calculations by fast computing machines. J. Chem. Phys. 21(6), 1087–1092 (1953). https://doi.org/10.1063/1.1699114

    Article  MATH  Google Scholar 

  17. Michelen, M., Perkins, W.: Strong spatial mixing for repulsive point processes. CoRR abs/2202.08753 (2022). https://arxiv.org/abs/2202.08753

  18. Patel, V., Regts, G.: Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials. SIAM J. Comput. 46(6), 1893–1919 (2017). https://doi.org/10.1137/16M1101003

    Article  MathSciNet  MATH  Google Scholar 

  19. Penrose, M.D.: Self-avoiding walks and trees in spread-out lattices. J. Stat. Phys. 77(1–2), 3–15 (1994). https://doi.org/10.1007/BF02186829

    Article  MathSciNet  MATH  Google Scholar 

  20. Sinclair, A., Srivastava, P., Štefankovič, D., Yin, Y.: Spatial mixing and the connective constant: optimal bounds. Probab. Theory Relat. Fields 168, 153–197 (2017). https://doi.org/10.1007/s00440-016-0708-2

    Article  MathSciNet  MATH  Google Scholar 

  21. Sly, A.: Computational transition at the uniqueness threshold. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 287–296 (2010). https://doi.org/10.1109/FOCS.2010.34

  22. Štefankovič, D., Vempala, S., Vigoda, E.: Adaptive simulated annealing: a near-optimal connection between sampling and counting. J. ACM 56(3), 1–36 (2009). https://doi.org/10.1145/1516512.1516520

    Article  MathSciNet  MATH  Google Scholar 

  23. Stoyan, D., Kendall, W.S., Chiu, S.N., Mecke, J.: Stochastic Geometry and its Applications. Wiley, Hoboken (2013). https://doi.org/10.1002/9781118658222

    Book  MATH  Google Scholar 

  24. Weitz, D.: Counting independent sets up to the tree threshold. In: Proceedings of the 38th Annual ACM Symposium on the Theory of Computing (STOC), pp. 140–149 (2006). https://doi.org/10.1145/1132516.1132538

  25. Widom, B., Rowlinson, J.S.: New model for the study of liquid-vapor phase transitions. J. Chem. Phys. 52(4), 1670–1684 (1970). https://doi.org/10.1063/1.1673203

    Article  Google Scholar 

Download references

Acknowledgments

Andreas Göbel was funded by the project PAGES (project No. 467516565) of the German Research Foundation (DFG). This project has received funding from the European Union’s Horizon 2020 research and innovation program under the Marie Skłodowska-Curie grant agreement No. 945298-ParisRegionFP and was partially funded by the HPI Research School on Data Science and Engineering.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Martin S. Krejca .

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Friedrich, T., Göbel, A., Katzmann, M., Krejca, M.S., Pappik, M. (2022). Algorithms for Hard-Constraint Point Processes via Discretization. In: Zhang, Y., Miao, D., Möhring, R. (eds) Computing and Combinatorics. COCOON 2022. Lecture Notes in Computer Science, vol 13595. Springer, Cham. https://doi.org/10.1007/978-3-031-22105-7_22

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-22105-7_22

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-22104-0

  • Online ISBN: 978-3-031-22105-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics