Limit laws for depths and heights of random trees

Teoria prawdopodobieństwa i modelowanie stochastyczne
Osoba referująca: 
Piotr Dyszewski (Uniwersytet Wrocławski)
czwartek, 25. Listopad 2021 - 12:15
We will revisit the random split-trees introduced by Devroye "Universal limit laws for depths in random trees." SIAM Journal on Computing 28, no. 2 (1998): 409-432, and show how one can use an embedding into a continuous setting to present a new treatment of the model. We will illustrate our approach by giving a new proof of the central limit theorem for the depth of a split-tree. Moreover we will give a new result in the form of a limit theorem for the height of a split-tree. The talk is based on a joint work in progress with C. Mailer (University of Bath).