{
  "id": "2206.03125",
  "version": "v1",
  "published": "2022-06-07T09:03:45.000Z",
  "updated": "2022-06-07T09:03:45.000Z",
  "title": "Monte Carlo integration with adaptive variance reduction: an asymptotic analysis",
  "authors": [
    "Leszek Plaskota",
    "Paweł Przybyłowicz",
    "Łukasz Stępień"
  ],
  "categories": [
    "math.NA",
    "cs.NA"
  ],
  "abstract": "The crude Monte Carlo approximates the integral $$S(f)=\\int_a^b f(x)\\,\\mathrm dx$$ with expected error (deviation) $\\sigma(f)N^{-1/2},$ where $\\sigma(f)^2$ is the variance of $f$ and $N$ is the number of random samples. If $f\\in C^r$ then special variance reduction techniques can lower this error to the level $N^{-(r+1/2)}.$ In this paper, we consider methods of the form $$\\overline M_{N,r}(f)=S(L_{m,r}f)+M_n(f-L_{m,r}f),$$ where $L_{m,r}$ is the piecewise polynomial interpolation of $f$ of degree $r-1$ using a partition of the interval $[a,b]$ into $m$ subintervals, $M_n$ is a Monte Carlo approximation using $n$ samples of $f,$ and $N$ is the total number of function evaluations used. We derive asymptotic error formulas for the methods $\\overline M_{N,r}$ that use nonadaptive as well as adaptive partitions. Although the convergence rate $N^{-(r+1/2)}$ cannot be beaten, the asymptotic constants make a huge difference. For example, for $\\int_0^1(x+d)^{-1}\\mathrm dx$ and $r=4$ the best adaptive methods overcome the nonadaptive ones roughly $10^{12}$ times if $d=10^{-4},$ and $10^{29}$ times if $d=10^{-8}.$ In addition, the proposed adaptive methods are easily implementable and can be well used for automatic integration. We believe that the obtained results can be generalized to multivariate integration.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-06-07T09:03:45.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "65C05",
      "65D30"
    ],
    "keywords": [
      "monte carlo integration",
      "adaptive variance reduction",
      "asymptotic analysis",
      "crude monte carlo approximates",
      "special variance reduction techniques"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}