2015/03/31 by Ningyuan Chen, Chen, Ningyuan, Mariana Olvera‐Cravioto +1
Computer Science · Mathematics · #60B10 #62F40 #68U20 #Algorithms and Data Compression #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1503.09150
openalex publication_date 2015/03/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider a linear recursion of the form R(k+1)\stackrel\mathcal D=∑i=1NCiR(k)i+Q, where (Q,N,C1,C2,…) is a real-valued random vector with N∈ℕ=\0, 1, 2, …\, \R(k)i\i∈ℕ is a sequence of i.i.d. copies of R(k), independent of (Q,N,C1,C2,…), and \stackrelD= denotes equality in distribution. For suitable vectors (Q,N,C1,C2,…) 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.