{
  "id": "1206.2689",
  "version": "v2",
  "published": "2012-06-12T23:49:36.000Z",
  "updated": "2015-03-18T07:41:45.000Z",
  "title": "Approximation algorithms for the normalizing constant of Gibbs distributions",
  "authors": [
    "Mark Huber"
  ],
  "comment": "Published in at http://dx.doi.org/10.1214/14-AAP1015 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)",
  "journal": "Annals of Applied Probability 2015, Vol. 25, 974-985",
  "doi": "10.1214/14-AAP1015",
  "categories": [
    "math.PR",
    "stat.CO"
  ],
  "abstract": "Consider a family of distributions $\\{\\pi_{\\beta}\\}$ where $X\\sim\\pi_{\\beta}$ means that $\\mathbb{P}(X=x)=\\exp(-\\beta H(x))/Z(\\beta)$. Here $Z(\\beta)$ is the proper normalizing constant, equal to $\\sum_x\\exp(-\\beta H(x))$. Then $\\{\\pi_{\\beta}\\}$ is known as a Gibbs distribution, and $Z(\\beta)$ is the partition function. This work presents a new method for approximating the partition function to a specified level of relative accuracy using only a number of samples, that is, $O(\\ln(Z(\\beta))\\ln(\\ln(Z(\\beta))))$ when $Z(0)\\geq1$. This is a sharp improvement over previous, similar approaches that used a much more complicated algorithm, requiring $O(\\ln(Z(\\beta))\\ln(\\ln(Z(\\beta)))^5)$ samples.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-06-12T23:49:36.000Z",
      "abstract": "Consider a family of distributions indexed by a parameter \\beta, where the probability that the configuration x is chosen is proportional to exp(-\\beta H(x)) / Z(\\beta). Here Z(\\beta) is the proper normalizing constant, equal to the sum over x' of exp(-\\beta H(x')). Then {\\pi_\\beta} is known as a Gibbs distribution, and Z(\\beta) is the partition function. This work presents a new method for approximating the partition function to a specified level of relative accuracy using only a number of samples that is O(ln(Z(\\beta)) ln(ln(Z(\\beta)))) when Z(0) >= 1. This is a sharp improvement over previous similar approaches, which used a much more complicated algorithm requiring O(ln(Z(\\beta)) ln(ln(Z(\\beta)))^5) samples.",
      "comment": null,
      "journal": null,
      "doi": null,
      "authors": [
        "Mark L. Huber"
      ]
    },
    {
      "version": "v2",
      "updated": "2015-03-18T07:41:45.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68Q87",
      "65C60",
      "65C05"
    ],
    "keywords": [
      "gibbs distribution",
      "approximation algorithms",
      "partition function",
      "proper normalizing constant",
      "sharp improvement"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1206.2689H"
    }
  }
}