On the contraction method with degenerate limit equation. (Q1889801): Difference between revisions

Several problems in discrete probability and analysis of algorithms lead to recursive random variables with logarithmic mean and variance, and a degenerate limit equation of the form \(X=X\) (in distribution) when properly normalized. The limit law is in most cases normal. This paper aims to solve such a situation under suitable assumptions on the distribution. The crucial idea is to decompose the standard normal distribution in a proper way so as to give a better approximation to the normalized random variables in question. Examples of application of the authors' main result include depth in random binary search trees and several cost measures of two randomized algorithms in some broadcast communication model studied previously by \textit{W.-M. Chen} and the reviewer [J. Algorithms 46, No. 2, 140--177 (2003; Zbl 1030.68109)].