{
  "id": "1503.09150",
  "version": "v1",
  "published": "2015-03-31T18:20:01.000Z",
  "updated": "2015-03-31T18:20:01.000Z",
  "title": "Efficient Simulation for Branching Linear Recursions",
  "authors": [
    "Ningyuan Chen",
    "Mariana Olvera-Cravioto"
  ],
  "comment": "submitted to WSC 2015",
  "categories": [
    "math.PR"
  ],
  "abstract": "We consider a linear recursion of the form $$R^{(k+1)}\\stackrel{\\mathcal D}{=}\\sum_{i=1}^{N}C_iR^{(k)}_i+Q,$$ where $(Q,N,C_1,C_2,\\dots)$ is a real-valued random vector with $N\\in\\mathbb{N}=\\{0, 1, 2, \\dots\\}$, $\\{R^{(k)}_i\\}_{i\\in\\mathbb{N}}$ is a sequence of i.i.d. copies of $R^{(k)}$, independent of $(Q,N,C_1,C_2,\\dots)$, and $\\stackrel{\\mathcal{D}}{=}$ denotes equality in distribution. For suitable vectors $(Q,N,C_1,C_2,\\dots)$ and provided the initial distribution of $R^{(0)}$ is well-behaved, the process $R^{(k)}$ is known to converge to the endogenous solution of the corresponding stochastic fixed-point equation, which appears in the analysis of information ranking algorithms, e.g., PageRank, and in the complexity analysis of divide and conquer algorithms, e.g. Quicksort. Naive Monte Carlo simulation of $R^{(k)}$ based on the branching recursion has exponential complexity in $k$, and therefore the need for efficient methods. We propose in this paper an iterative bootstrap algorithm that has linear complexity and can be used to approximately sample $R^{(k)}$. We show the consistency of estimators based on our proposed algorithm.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-03-31T18:20:01.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68U20",
      "62F40",
      "60B10"
    ],
    "keywords": [
      "branching linear recursions",
      "efficient simulation",
      "naive monte carlo simulation",
      "corresponding stochastic fixed-point equation",
      "linear complexity"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}