Premium
On the Joint Path Length Distribution in Random Binary Trees
Author(s) -
Knessl Charles,
Szpankowski Wojciech
Publication year - 2006
Publication title -
studies in applied mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 46
eISSN - 1467-9590
pISSN - 0022-2526
DOI - 10.1111/j.1467-9590.2006.00349.x
Subject(s) - mathematics , path (computing) , random binary tree , binary tree , path length , wkb approximation , mathematical analysis , distribution (mathematics) , nonlinear system , binary number , joint probability distribution , moment generating function , generating function , combinatorics , probability distribution , statistics , physics , arithmetic , quantum mechanics , computer science , programming language
During the 10th Seminar on Analysis of Algorithms , MSRI, Berkeley, June 2004, Knuth posed the problem of analyzing the left and the right path length in a random binary tree. In particular, Knuth asked about properties of the generating function of the joint distribution of the left and the right path lengths. In this paper, we mostly focus on the asymptotic properties of the distribution of the difference between the left and the right path lengths. Among other things, we show that the Laplace transform of the appropriately normalized moment generating function of the path difference satisfies the first Painlevé transcendent . This is a nonlinear differential equation that has appeared in many modern applications, from nonlinear waves to random matrices. Surprisingly, we find out that the difference between path lengths is of the order n 5/4 where n is the number of nodes in the binary tree. This was also recently observed by Marckert and Janson. We present precise asymptotics of the distribution's tails and moments. We will also discuss the joint distribution of the left and right path lengths. Throughout, we use methods of analytic algorithmics such as generating functions and complex asymptotics, as well as methods of applied mathematics such as the Wentzel, Kramers, Brillouin (WKB) method.