Tail behavior of solutions of linear recursions on trees

DOI10.1016/J.SPA.2012.01.003MaRDI QIDQ424501zbMATH OpenOpenAlexFDO

Authors Mariana Olvera-Cravioto

Publication date 1 June 2012

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

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

zbMATH Keywords

large deviationsregular variationrandom difference equationsmultiplicative cascadesstochastic fixed point equationsstochastic recursionweighted branching processes

Mathematics Subject Classification ID

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

Abstract: Consider the linear nonhomogeneous fixed point equation R =_d sum_{i=1}^N C_i R_i + Q, where (Q,N,C_1,...,C_N) is a random vector with N in{0,1,2,3,...}U{infty}, {C_i}_{i=1}^N >= 0, P(|Q|>0) > 0, and {R_i}_{i=1}^N is a sequence of i.i.d. random variables independent of (Q,N,C_1,...,C_N) having the same distribution as R. It is known that R will have a heavy-tailed distribution under several different sets of assumptions on the vector (Q,N,C_1,...,C_N). This paper investigates the settings where either Z_N = sum_{i=1}^N C_i or Q are regularly varying with index -alpha < -1 and E[sum_{i=1}^N C_i^alpha] < 1. This work complements previous results showing that P(R>t) Ht^{-alpha} provided there exists a solution alpha > 0 to the equation E[sum_{i=1}^N|C_i|^alpha] = 1, and both Q and Z_N have lighter tails.

Recommendations

• Maximums on trees
• Power laws on weighted branching trees
• Precise tail asymptotics of fixed points of the smoothing transform with general weights
• Tail asymptotics of maximums on trees in the critical case
• Implicit renewal theory and power tails on trees

Cites work

• scientific article; zbMATH DE number 4000257 (Why is no real title available?)
• scientific article; zbMATH DE number 765034 (Why is no real title available?)
• A general limit theorem for recursive algorithms and combinatorial structures
• A survey of max-type recursive distributional equations
• Approximating the limiting quicksort distribution
• Asymptotic analysis for personalized web search
• Asymptotics for Weighted Random Sums
• Determining Factors Behind the PageRank Log-Log Plot
• Distances in random graphs with finite variance degrees
• Elementary fixed points of the BRW smoothing transforms with infinite number of summands
• Fixed points of the smoothing transform: two-sided solutions
• 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
• Large deviations and ruin probabilities for solutions to stochastic recurrence equations with heavy-tailed innovations
• Martingale convergence in the branching random walk
• On generalized multiplicative cascades
• Perpetuities with thin tails
• Random difference equations and renewal theory for products of random matrices
• Regular variation in the tail behaviour of solutions of random difference equations
• Regularly varying functions
• The contraction method for recursive algorithms
• The functional equation of the smoothing transform
• The stochastic equation Y_n+1=A_nY_n + B_n with stationary coefficients

Cited in

(14)

• Maximums on trees
• Tail asymptotics of maximums on trees in the critical case
• Stochastic recursions on directed random graphs
• Pagerank asymptotics on directed preferential attachment networks
• Recurrence equations over trees in a non-Archimedean context
• Weighted branching and a pathwise renewal equation
• Convergence of the population dynamics algorithm in the Wasserstein metric
• PageRank in Scale-Free Random Graphs
• Convergence rates in the implicit renewal theorem on trees
• Tails for (max, plus) recursions under subexponentiality
• PageRank's behavior under degree correlations
• A necessary and sufficient condition for the tail-triviality of a recursive tree process
• Power laws on weighted branching trees
• Tightness for a family of recursion equations

This page was built for publication: Tail behavior of solutions of linear recursions on trees

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