\input zb-basic
\input zb-ioport
\iteman{io-port 06053730}
\itemau{Munsonius, G\"otz Olaf}
\itemti{On tail bounds for random recursive trees.}
\itemso{J. Appl. Probab. 49, No. 2, 566-581 (2012).}
\itemab
A stochastic recursion of the following form is studied: $$X_n\overset{D}\to{=}\sum_{1}^b A_i(I_n)X_{I_{n,i}}^{(i)} + d(I_n,Z),\quad n\ge 2. $$ Here $X_n, X_n^{(1)},\ldots, X_n^{(b)}$ are i.i.d. random variables,\ $ d: {\cal R}^b\times {\cal R}^b\rightarrow {\cal R}^k,$ $A_i$ are deterministic functions,\ $Z\in {\cal R}^b_{\ge 0}$ are random vectors and $Z, I_n,X_n, X_n^{(1)},\ldots, X_n^{(b)}$ are mutually independent. Finally, $\overset{D}\to{=}$ denotes the equality in distribution. Such recursion arises in probabilistic analysis of algorithms and random trees. The focus of the paper is on bounding the probabilities of the tails $\Bbb P(X_{n_j}>t).$
\itemrv{Boris Granovsky (Haifa)}
\itemcc{}
\itemut{random tree; probabilistic analysis of algorithms; tail bound; path length; Wiener index}
\itemli{doi:10.1239/jap/1339878805 euclid:jap/1339878805}
\end