Tail behavior of solutions of linear recursions on trees

DOI10.1016/J.SPA.2012.01.003zbMATH Open1253.60077arXiv1108.3809OpenAlexW2089324648MaRDI QIDQ424501FDOQ424501

Mariana Olvera-Cravioto

Publication date: 1 June 2012

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Random difference equations and renewal theory for products of random matrices
• Title not available (Why is that?)
• 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
• The stochastic equation Y_n+1=A_nY_n + B_n with stationary coefficients
• A survey of max-type recursive distributional equations
• Martingale convergence in the branching random walk
• Regularly varying functions
• On generalized multiplicative cascades
• Regular variation in the tail behaviour of solutions of random difference equations
• Large deviations and ruin probabilities for solutions to stochastic recurrence equations with heavy-tailed innovations
• Distances in random graphs with finite variance degrees
• Implicit renewal theory and power tails on trees
• Information ranking and power laws on trees
• Elementary fixed points of the BRW smoothing transforms with infinite number of summands
• Perpetuities with thin tails
• Asymptotics for Weighted Random Sums
• Fixed points of the smoothing transform: two-sided solutions
• Approximating the limiting quicksort distribution
• Asymptotic analysis for personalized Web search
• Determining Factors Behind the PageRank Log-Log Plot
• The functional equation of the smoothing transform

Cited In (9)

• Pagerank asymptotics on directed preferential attachment networks
• Recurrence equations over trees in a non-Archimedean context
• PageRank in Scale-Free Random Graphs
• Stochastic recursions on directed random graphs
• Convergence of the population dynamics algorithm in the Wasserstein metric
• Weighted branching and a pathwise renewal equation
• Tails for (max, plus) recursions under subexponentiality
• PageRank's behavior under degree correlations
• 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)