Maximums on trees

DOI10.1016/J.SPA.2014.09.004zbMATH Open1316.60131arXiv1405.6265OpenAlexW2060897377MaRDI QIDQ468736FDOQ468736

Authors: Predrag R. Jelenković, Mariana Olvera-Cravioto 

Publication date: 7 November 2014

Published in: Stochastic Processes and their Applications (Search for Journal in Brave)

Abstract: We study the minimal/endogenous solution $R$ to the maximum recursion on weighted branching trees given by ${\displaystyle }$Rstackrel{mathcal{D}}{=}left(�igvee_{i=1}^NC_iR_i ight)vee Q,${\displaystyle }$ where $(Q,N,C_1,C_2,dots)$ is a random vector with $NinmathbbNcupinfty$, $P(|Q|>0)>0$ and nonnegative weights $C_i$, and ${R_i}_{iinmathbbN}$ is a sequence of i.i.d. copies of $R$ independent of $(Q,N,C_1,C_2,dots)$; $stackrelmathcalD=$ denotes equality in distribution. Furthermore, when $Q>0$ this recursion can be transformed into its additive equivalent, which corresponds to the maximum of a branching random walk and is also known as a high-order Lindley equation. We show that, under natural conditions, the asymptotic behavior of $R$ is power-law, i.e., $P(|R|>x)simH{x}^{-alpha}$, for some $alpha>0$ and $H>0$. This has direct implications for the tail behavior of other well known branching recursions.

Full work available at URL: https://arxiv.org/abs/1405.6265

Recommendations

• Tail asymptotics of maximums on trees in the critical case
• Implicit renewal theory and power tails on trees
• Tail behavior of solutions of linear recursions on trees
• On weighted heights of random trees
• Power laws on weighted branching trees

zbMATH Keywords

large deviationsbranching random walkrandom difference equationsweighted branching processeshigh-order Lindley equationmaximum recursionpower law distributionsstochastic fixed-point equationsCramér-Lundberg approximation

Mathematics Subject Classification ID

Large deviations (60F10) Sums of independent random variables; random walks (60G50) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Random operators and equations (aspects of stochastic analysis) (60H25) Renewal theory (60K05)

Cites Work

• Implicit renewal theory and tails of solutions of random equations
• A general limit theorem for recursive algorithms and combinatorial structures
• The contraction method for recursive algorithms
• A survey of max-type recursive distributional equations
• Heavy tailed solutions of multivariate smoothing transforms
• Implicit renewal theory and power tails on trees
• Information ranking and power laws on trees
• On fixed points of a generalized multidimensional affine recursion
• Implicit renewal theorem for trees with general weights
• Fixed points of inhomogeneous smoothing transforms
• Fixed points of the smoothing transform: two-sided solutions
• Approximating the limiting quicksort distribution
• Asymptotic analysis for personalized web search
• Higher-order Lindley equations
• Lindley-type equations in the branching random walk
• Precise tail index of fixed points of the two-sided smoothing transform
• Title not available (Why is that?)
• A stochastic fixed point equation for weighted minima and maxima

Cited In (13)

• Large deviation estimates for branching random walks
• The height of increasing trees
• Tail asymptotics of maximums on trees in the critical case
• Tail behavior of solutions of linear recursions on trees
• Exponential tail bounds for max-recursive sequences
• Max-linear models in random environment
• Extremal properties of evolving networks: local dependence and heavy tails
• Importance sampling for maxima on trees
• Maxima and sums of non-stationary random length sequences
• Implicit renewal theory and power tails on trees
• Convergence of the population dynamics algorithm in the Wasserstein metric
• Stationary waiting time in parallel queues with synchronization
• Tightness for a family of recursion equations

This page was built for publication: Maximums on trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q468736)