Maximums on Trees

Abstract

We study the minimal/endogenous solution $R$ to the maximum recursion on weighted branching trees given by $$R\stackrel{\mathcal{D}}{=}\left(\underset{i=1}{\overset{N}{\bigvee }}{C}_i{R}_i\right)\vee Q,$$ where $(Q,N,C_1,C_2,\dots )$ is a random vector with $N\in \mathbb{N}\cup \{\infty \}$, $P(|Q|>0)>0$ and nonnegative weights $\{C_i\}$, and $\{R_i{\}}_{i\in \mathbb{N}}$ is a sequence of i.i.d. copies of $R$ independent of $(Q,N,C_1,C_2,\dots )$; $\stackrel{\mathcal{D}}{=}$ 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)\sim H{x}^{-\alpha }$, for some $\alpha >0$ and $H>0$. This has direct implications for the tail behavior of other well known branching recursions.

arXiv admin note: text overlap with arXiv:1006.3295