---
res:
bibo_abstract:
- "A central problem in computational statistics is to convert a procedure for sampling
combinatorial objects into a procedure for counting those objects, and vice versa.
We will consider sampling problems which come from Gibbs distributions, which
are families of probability distributions over a discrete space Ω with probability
mass function of the form μ^Ω_β(ω) ∝ e^{β H(ω)} for β in an interval [β_min, β_max]
and H(ω) ∈ {0} ∪ [1, n].\r\nThe partition function is the normalization factor
Z(β) = ∑_{ω ∈ Ω} e^{β H(ω)}, and the log partition ratio is defined as q = (log
Z(β_max))/Z(β_min)\r\nWe develop a number of algorithms to estimate the counts
c_x using roughly Õ(q/ε²) samples for general Gibbs distributions and Õ(n²/ε²)
samples for integer-valued distributions (ignoring some second-order terms and
parameters), We show this is optimal up to logarithmic factors. We illustrate
with improved algorithms for counting connected subgraphs and perfect matchings
in a graph.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: David G.
foaf_name: Harris, David G.
foaf_surname: Harris
- foaf_Person:
foaf_givenName: Vladimir
foaf_name: Kolmogorov, Vladimir
foaf_surname: Kolmogorov
foaf_workInfoHomepage: http://www.librecat.org/personId=3D50B0BA-F248-11E8-B48F-1D18A9856A87
bibo_doi: 10.4230/LIPIcs.ICALP.2023.72
bibo_volume: 261
dct_date: 2023^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/1868-8969
- http://id.crossref.org/issn/9783959772785
dct_language: eng
dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
dct_title: Parameter estimation for Gibbs distributions@
...