{
  "id": "1108.3201",
  "version": "v2",
  "published": "2011-08-16T10:30:31.000Z",
  "updated": "2013-11-16T23:30:54.000Z",
  "title": "Explicit error bounds for Markov chain Monte Carlo",
  "authors": [
    "Daniel Rudolf"
  ],
  "journal": "Dissertationes Math. 485 (2012), 93 pp",
  "categories": [
    "math.PR",
    "math.NA"
  ],
  "abstract": "We prove explicit, i.e. non-asymptotic, error bounds for Markov chain Monte Carlo methods. The problem is to compute the expectation of a function f with respect to a measure {\\pi}. Different convergence properties of Markov chains imply different error bounds. For uniformly ergodic and reversible Markov chains we prove a lower and an upper error bound with respect to the L2 -norm of f . If there exists an L2 -spectral gap, which is a weaker convergence property than uniform ergodicity, then we show an upper error bound with respect to the Lp -norm of f for p > 2. Usually a burn-in period is an efficient way to tune the algorithm. We provide and justify a recipe how to choose the burn-in period. The error bounds are applied to the problem of the integration with respect to a possibly unnormalized density. More precise, we consider the integration with respect to log-concave densities and the integration over convex bodies. By the use of the Metropolis algorithm based on a ball walk and the hit-and-run algorithm it is shown that both problems are polynomial tractable.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2013-11-16T23:30:54.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "65C05",
      "60J10",
      "60J05",
      "60J22",
      "65C20",
      "37A25",
      "62F25",
      "65Y20"
    ],
    "keywords": [
      "explicit error bounds",
      "upper error bound",
      "markov chain monte carlo methods",
      "convergence property",
      "burn-in period"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "journal": "Ph.D. Thesis",
      "year": 2011
    },
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011PhDT.......182R"
    }
  }
}