Implicit renewal theorem for trees with general weights

STOCHASTIC PROCESSES AND THEIR APPLICATIONS

卷:122

Article

Jelenkovic, Predrag R.²  Olvera-Cravioto, Mariana¹ 

[1] Columbia Univ, Dept Ind Engn & Operat Res, New York, NY 10027 USA

[2] Columbia Univ, Dept Elect Engn, New York, NY 10027 USA

关键词: Implicit renewal theory;    Weighted branching processes;    Multiplicative cascades;    Smoothing transforms;    Stochastic recursions;    Power laws;    Large deviations;    Stochastic fixed point equations;   

DOI  :  10.1016/j.spa.2012.05.004

来源: Elsevier

【 摘 要 】

Consider distributional fixed point equations of the form R (D)(=) f (Q, C-i, R-i, I <= i <= N), where f(.) is a possibly random real-valued function, N is an element of {0, 1, 2, 3, ...} U {infinity}, {C-i}(i is an element of N) are real-valued random weights and {R-i}(i is an element of N) are lid copies of R, independent of (Q, N, C-1, C-2, ...); (D)(=) represents equality in distribution. Fixed point equations of this type are important for solving many applied probability problems, ranging from the average case analysis of algorithms to statistical physics. We develop an Implicit Renewal Theorem that enables the characterization of the power tail behavior of the solutions R to many equations of multiplicative nature that fall into this category. This result extends the prior work in Jelenkovie and Olvera-Cravioto (2012) [16], which assumed nonnegative weights (C-i), to general real-valued weights. We illustrate the developed theorem by deriving the power tail asymptotics of the solution R to the linear equation R (D)(=) Sigma(N)(i)(= =1) C-i R-i + Q. (c) 2012 Elsevier B.V. All rights reserved.

【 授权许可】

Free