engleski

Importance sampling for maxima on trees

We study the all-time supremum of the perturbed branching random walk, known to be the endogenous solution to the high-order Lindley equation: \begin{; ; ; equation*}; ; ; W \stackrel{; ; ; \mathcal{; ; ; D}; ; ; }; ; ; {; ; ; =}; ; ; \max\left\{; ; ; Y, \, \max_{; ; ; 1 \leq i \leq N}; ; ; (W_i + X_i) \right\}; ; ; , \end{; ; ; equation*}; ; ; where the $\{; ; ; W_i\}; ; ; $ are independent copies of $W$, independent of the random vector $(Y, N, \{; ; ; X_i\}; ; ; )$ taking values in $\mathbb{; ; ; R}; ; ; \times \mathbb{; ; ; N}; ; ; \times \mathbb{; ; ; R}; ; ; ^\infty$. Under Kesten assumptions, this solution satisfies \[P(W > t) \sim H e^{; ; ; -\alpha t}; ; ; , \qquad t \to \infty, \] where $\alpha>0$ solves the Cram\'er-Lundberg equation $ E\left[ \sum_{; ; ; i=1}; ; ; ^N e^{; ; ; \alpha X_i}; ; ; \right] = 1$. This paper establishes the tail asymptotics of $W$ by using the forward iterations of the map defining the fixed-point equation combined with a change of measure along a randomly chosen path. This new approach provides an explicit representation of the constant $H$ and gives rise to unbiased and strongly efficient estimators for the rare event probabilities $P(W > t)$.

High-order Lindley equation, branching random walk, importance sampling, weighted branching processes, distributional fixed-point equations, change of measure

nije evidentirano