On tail bounds for random recursive trees (Q2897163)

A stochastic recursion of the following form is studied: NEWLINE\[NEWLINEX_n\overset{D}{=}\sum_{1}^b A_i(I_n)X_{I_{n,i}}^{(i)} + d(I_n,Z),\quad n\geq 2. NEWLINE\]NEWLINE Here \(X_n, X_n^{(1)},\ldots, X_n^{(b)}\) are i.i.d. random variables,\ \( d: {\mathcal R}^b\times {\mathcal R}^b\rightarrow {\mathcal R}^k,\) \(A_i\) are deterministic functions,\ \(Z\in {\mathcal R}^b_{\geq 0}\) are random vectors and \(Z, I_n,X_n, X_n^{(1)},\ldots, X_n^{(b)}\) are mutually independent. Finally, \(\overset{D}{=}\) 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 \(\mathbb P(X_{n_j}>t).\)