Efficient Simulation for Branching Linear Recursions

Authors Ningyuan Chen, Mariana Olvera-Cravioto

Publication date 31 March 2015

Convergence of probability measures (60B10) Bootstrap, jackknife and other resampling methods (62F40)

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}, d o t s)

is a real-valued random vector with

N i n m a t h b b N = 0, 1, 2, d o t s

,

{R_{i}^{(k)}}_{i i n m a t h b b N}

is a sequence of i.i.d. copies of

R^{(k)}

, independent of

(Q, N, C_{1}, C_{2}, d o t s)

, and

s t a c k r e l m a t h c a l D =

denotes equality in distribution. For suitable vectors

(Q, N, C_{1}, C_{2}, d o t s)

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.

This page was built for publication: Efficient Simulation for Branching Linear Recursions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6260466)