The thesis is devoted to the analysis of asymptotic properties of random trees when the number of verticles goes to infinity. The work considers three classes of random trees and presents results on the asymptotic behaviour of profiles, mode, width, height, length of particular paths etc. The first class is simply generated random trees, which is a classic model in the literature. It can be described in the following way: on each step we pick a vertex uniformly at random from a subset of all verticies and add new verticies to the chosen one according to some prescribed rule. This class contains, in particular, random recursive trees and binary search trees. The second model is general branching process trees. Thirdly, we consider VP-trees, which appeared for the first time in computer science as a data structure for fast execution of nearest neighbor search queries.
In the present work we continue the analysis of random trees using methods and techniques developed in recent works of A. Iksanov, Z. Kabluchko, A. Marynych, H. Sulzbach et al. Not only we obtain new results but also improve general theory which is used in the proofs. Moreover, we analyse a new type of trees, which has not been studied before from a probabilistic viewpoint.
We obtain complete asymptotic expansions almost surely for profiles of simply generated random trees and provide limit theorems for mode and width, as well as propose new characterizations of random variables, which appear as the coefficients, via stochastic fixed-point equations. We also analyse the height of a general branching process tree of an iterated perturbed random walk. As a byproduct we derive new asymptotics for Lebesgue--Stieltjes convolutions of functions of linear growth which appear in the analysis of intermediate levels of trees of iterated perturbed random walk and apply these results to renewal functions. Besides we prove a weak law of large numbers for the length of the leftmost path in a VP-tree and a limit theorem for this length along subsequences. Finally, we study partitions of a space generated by a random VP-tree. We prove the finiteness of the moment of the first return to certain states of these partitions, the existence of a stationary distribution of the corresponding Markov chain on the set of partitions and convergence this stationary distribution, which is also calculated explicitly.
Most of theoretical results are accompanied by mathematical modelling and computer simulations using a programming language Python3, which confirms the obtained assertions and gives a better understanding of studied quantities.
The thesis is both of theoretical and applied nature. Random trees have numerous applications in data structures and algorithms analysis, and in modelling of evolution and distribution processes in many applied sciences, in particular, in biology, medicine, sociology, economics etc. Obtained results can be used in the aforementioned areas, and developed mathematical methods can be used for future research of other classes of trees.
