{
  "id": "1708.07466",
  "version": "v1",
  "published": "2017-08-24T15:47:50.000Z",
  "updated": "2017-08-24T15:47:50.000Z",
  "title": "Randomized Dimension Reduction for Markov Chains Simulation",
  "authors": [
    "Nabil Kahale"
  ],
  "comment": "22 pages, 1 figure. A preliminary version has appeared at the 9th NIPS Workshop on Optimization for Machine Learning, Dec. 2016, Barcelona",
  "categories": [
    "stat.CO"
  ],
  "abstract": "We present an efficient method to estimate a function of the state of a Markov chain at time-step d. Our method is based on a new unbiased algorithm that estimates the expected value of f(U) via Monte Carlo simulation, where U is a vector of d independent random variables, and f is a function that depends little on its last arguments. The algorithm samples an initial segment of components of U according to a certain distribution. For several Markov chains, our method improves upon standard Monte Carlo by a factor asymptotically proportional to d. We establish a relationship between the performance of our algorithm and the truncation dimension of f. The algorithm uses a new geometric method, of independent interest, that computes the optimal distribution in O(d) steps. Numerical experiments support our findings.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-08-24T15:47:50.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "markov chains simulation",
      "randomized dimension reduction",
      "monte carlo simulation",
      "independent random variables",
      "standard monte carlo"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 22,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}