Width and mode of the profile for some random trees of logarithmic height (Q997955)

From the authors' introduction: Most random trees in the discrete probability literature have height either of order \(\sqrt{n}\) or of order \(\log{n}\) (\(n\) being the tree size). For simplicity, we call these trees square-root trees and log trees, respectively. Profiles (number of nodes at each level of the tree) of random square-root trees have a rich connection to diverse structures in combinatorics and probability, and have been extensively studied. In contrast, profiles of random log trees, arising mostly from data structures and computer algorithms, were less addressed and only quite recently were their limit distributions, drastically different from those of square-root trees, better understood. We study in this paper the asymptotics of width, which is defined to be the size of the most abundant level, and its close connection to the profile. There are many results on first-order asymptotics of profiles for standard log trees, such as binary search trees, random recursive trees, \(m\)-ary search trees and quad trees. In some cases, quite accurate asymptotic expresssions are known for the expected profile. The present paper extends the results to a universal class of log trees called width-regular. It adds a host of new results on the width of these trees, such as its exact location up to \(O(1)\) as well as tight estimates on the central moments of the width and some strong laws of large numbers. Equally important is the fact that these results are obtained from simple moment estimates. For example, the correlation between the profiles at different levels is not needed at all in the study of the width. In their analysis the authors combine two crucial asymptotic estimates for the expected profile and for its higher central moments with some basic probabilistic theorems, such as Markov and Chebyshev inequalities and the Borel-Cantelli lemma. The asymptotic estimates for the expected profile and for the higher central moments are, however, previously obtained using diverse analytic tools, such as differential equations, singularity analysis and the saddle-point method.