Importance sampling for maxima on trees

Abstract

We consider the distributional fixed-point equation: $$R\stackrel{\mathcal{D}}{=}Q\vee \left(\underset{i=1}{\overset{N}{\bigvee }}{C}_i{R}_i\right),$$ where the $\{R_i\}$ are i.i.d.~copies of $R$, independent of the vector $(Q,N,\{C_i\})$, where $N\in \mathbb{N}$, $Q,\{C_i\}\ge 0$ and $P(Q>0)>0$. By setting $W=\log R$, $X_i=\log C_i$, $Y=\log Q$ it is equivalent to the high-order Lindley equation $$W\stackrel{\mathcal{D}}{=}\max \left\{Y,\underset{1\le i\le N}{\max }(X_i+W_i)\right\}.$$ It is known that under Kesten assumptions, $$P(W>t)\sim H{e}^{-\alpha t},t\to \infty ,$$ where $\alpha >0$ solves the Cramér-Lundberg equation $E\left[{\sum }_{j=1}^N{C}_i^{\alpha }\right]=E\left[{\sum }_{i=1}^N{e}^{\alpha X_i}\right]=1$. The main goal of this paper is to provide an explicit representation for $P(W>t)$, which can be directly connected to the underlying weighted branching process where $W$ is constructed and that can be used to construct unbiased and strongly efficient estimators for all $t$. Furthermore, we show how this new representation can be directly analyzed using Alsmeyer's Markov renewal theorem, yielding an alternative representation for the constant $H$. We provide numerical examples illustrating the use of this new algorithm.