Information Ranking and Power Laws on Trees

2009/05/11 by Predrag R. Jelenković, Jelenkovic, Predrag R., Mariana Olvera‐Cravioto +1 · 1 citation
Computer Science · Mathematics · #60H25 #60J80 #Advanced Database Systems and Queries #Algorithms and Data Compression #FOS: Computer and information sciences #FOS: Mathematics #Performance (cs.PF) #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.0905.1738

openalex publication_date 2009/05/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the situations when the solution to a weighted stochastic recursion has a power law tail. To this end, we develop two complementary approaches, the first one extends Goldie's (1991) implicit renewal theorem to cover recursions on trees; and the second one is based on a direct sample path large deviations analysis of weighted recursive random sums. We believe that these methods may be of independent interest in the analysis of more general weighted branching processes as well as in the analysis of algorithms.

Cited by

• PCA recovery thresholds in low-rank matrix inference with sparse noise

Related

• Implicit Renewal Theory and Power Tails on Trees
• On tail bounds for random recursive trees
• Maximums on Trees
• Tail asymptotics of maximums on trees in the critical case
• Implicit Renewal Theorem for Trees with General Weights