Efficient Simulation for Branching Linear Recursions

Ningyuan Chen, Mariana Olvera-Cravioto

Published 2015-03-31Version 1

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.