2026-08-17T17:48:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18124 2024-03-06T11:01:05Z ddc:004 open_access

Parameter Estimation for Gibbs Distributions Harris, David G. Kolmogorov, Vladimir Gibbs distribution sampling 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]. The partition function is the normalization factor Z(β) = ∑_{ω ∈ Ω} e^{β H(ω)}, and the log partition ratio is defined as q = (log Z(β_max))/Z(β_min) We 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik David G. Harris and Vladimir Kolmogorov 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.72 urn:nbn:de:0030-drops-181246 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.72 eng https://creativecommons.org/licenses/by/4.0/legalcode