Maximums on trees

DOI10.1016/J.SPA.2014.09.004MaRDI QIDQ468736zbMATH OpenOpenAlexFDO

Authors Predrag R. Jelenković, Mariana Olvera-Cravioto

Publication date 7 November 2014

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

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

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)

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.

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

Cites work

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

Cited in

(13)

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

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)