On tail bounds for random recursive trees
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).\)
- A limit theorem for “quicksort”
- Approximating the limiting quicksort distribution
- Exponential bounds and tails for additive random recursive sequences
- scientific article; zbMATH DE number 2127728 (Why is no real title available?)
- scientific article; zbMATH DE number 5763324 (Why is no real title available?)
- scientific article; zbMATH DE number 1375579 (Why is no real title available?)
- scientific article; zbMATH DE number 837692 (Why is no real title available?)
- Large Deviations for Quicksort
- Large deviations for the weighted height of an extended class of trees
- Limit theorems for functionals of recursive trees.
- Note on the heights of random recursive trees and random m‐ary search trees
- Precise logarithmic asymptotics for the right tails of some limit random variables for random trees
- The center of mass of the ISE and the Wiener index of trees
- The height of increasing trees
- The total Steiner k-distance for b-ary recursive trees and linear recursive trees
- Applications of the theory of records in the study of random trees
- Probabilistic recurrence relations revisited
- On a tail bound for analyzing random trees
- Exponential tail bounds for max-recursive sequences
- Tails for (max, plus) recursions under subexponentiality
- Profile of random exponential recursive trees
- Recursive random variables with subgaussian distributions
- scientific article; zbMATH DE number 6522631 (Why is no real title available?)
- Limit theorems for functionals of recursive trees.
- Tail behaviour and martingale convergence of random recursive structures and algorithms
- The Hitting Time for the Height of a Random Recursive Tree
- Random infinite trees and supercritical behavior of collision resolution algorithms
- Probability bounds given by hypercherry trees
- (Probabilistic) recurrence relations revisited
- Random tree recursions: Which fixed points correspond to tangible sets of trees?
- The Wiener index of random digital trees
- Note on a stochastic recursion
- Exponential bounds and tails for additive random recursive sequences
- Precise logarithmic asymptotics for the right tails of some limit random variables for random trees
This page was built for publication: On tail bounds for random recursive trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2897163)
