论文标题
对树木上最大的重要性采样
Importance sampling for maxima on trees
论文作者
论文摘要
我们考虑分布固定点方程：$$ r \ stackrel {\ Mathcal {d}} {=} q \ vee \ left（\ bigVee_ {\ bigVee_ {i = 1}^n c_i r_i \ right） \ {c_i \}）$，其中$ n \ in \ mathbb {n} $，$ q，\ {c_i \} \ geq 0 $和$ p（q> 0）> 0 $。通过设置$ w = \ log r $，$ x_i = \ log c_i $，$ y = \ log q $，它等于高阶的lindley方程$$ w \ stackrel {\ Mathcal {d}}}}} {=} {=} \ max \ max \ max \ max \ weft \ weft \ weft \ y， \ right \}。$$，众所周知，在kesten假设下，$$ p（w> t）\ sim h e^{ - αt}，\ qquad t \ t \ to \ to \ infty，$α> 0 $ solycramér-lundberg earvescramér-lundbergquarmér-lundberg方程$ \ sum_ {i = 1}^n e^{αx_i} \ right] = 1 $。本文的主要目的是为$ p（w> t）$提供明确的表示形式，该表示可以直接连接到构建$ W $的基础加权分支过程中，并且可用于为所有$ t $构建无偏见且高效的估计器。此外，我们展示了如何使用Alsmeyer的Markov Renewal定理直接分析这种新表示形式，从而为常数$ h $提供了替代表示。我们提供的数值示例说明了这种新算法的使用。
We consider the distributional fixed-point equation: $$R \stackrel{\mathcal{D}}{=} Q \vee \left( \bigvee_{i=1}^N 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\} \geq 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, \, \max_{1 \leq i \leq N} (X_i + W_i) \right\}.$$ It is known that under Kesten assumptions, $$P(W > t) \sim H e^{-αt}, \qquad t \to \infty,$$ where $α>0$ solves the Cramér-Lundberg equation $E \left[ \sum_{j=1}^N C_i ^α\right] = E\left[ \sum_{i=1}^N e^{α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.
