Богун Владислав АнатолійовичМаринич Олександр Віталійович2022-11-182024-05-102022-11-182022Богун В. А. Дослiдження асимптотичних властивостей випадкових дерев : дис ... д-ра філос. : 113 - прикладна математика / Богун Владислав Анатолiйович. - Київ, 2022. - 147 с.УДК 519.21https://ir.library.knu.ua/handle/123456789/2151The 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 coeffici- ents, 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 parti- tions 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 evoluti- on and distribution processes in many applied sciences, in particular, in biology, medicine, sociology, economics etc. Obtained results can be used in the aforementi- oned areas, and developed mathematical methods can be used for future research of other classes of trees.Дисертацiйна робота присвячена дослiдженню асимптотичних властивостей випадкових дерев, коли кiлькiсть вершин у деревi прямує до нескiнченностi. В роботi розглянуто три класи випадкових дерев, представлено результати про асимптотичну поведiнку профiлiв, моди, ширини, висоти, довжин певних шляхiв та iнших характеристик. Першим класом є випадковi дерева простої будови, що є класичною моделлю в лiтературi. Її можна описати наступним чином: на кожному кроцi в деревi навмання вибирається вершина з певної пiдмножини та до неї додаються новi вершини. До цього класу належать випадковi рекурсивнi дерева та бiнарнi дерева пошуку. Другою моделлю слугують дерева загальних гiллястих процесiв. Третiми виступають VP-дерева, що виникають в комп’ютерних науках як структура даних для швидкого виконання запиту пошуку найближчого сусiда. В данiй дисертацiйнiй роботi продовжено дослiдження випадкових дерев методами та технiками, використаними в нещодавнiх роботах О. Iксанова, З. Каблучка, О. Маринича, Г. Зульцбаха та iнших. При цьому отримано новi результати та збагачено загальну теорiю, що використовується для доведень. Окрiм цього в роботi дослiджується новий клас дерев, що ранiше не вивчався з ймовiрнiсної точки зору. Автором дисертацiї отримано повнi асимптотичнi розклади майже напевне для профiлiв випадкових дерев простої будови, доведено граничнi теореми для моди i ширини та запропоновано новi характеризацiї для випадкових ве- личин, що при цьому виникають, у виглядi стохастичних рiвнянь нерухомої точки. Проаналiзовано висоту дерев загального гiллястого процесу побудова- ного за збуреним випадковим блуканням. Додатково автором отримано асимптотики згорток Лебега-Стiлтьєса функцiй лiнiйного росту, що з’являються при дослiдженнi подiбних дерев на промiжних рiвнях, а вiдповiднi результати застосованi до функцiй вiдновлення. Також було доведено слабкий закон великих чисел для довжини найлiвiшого шляху у VP-деревi та граничну тео- рему щодо її збiжностi вздовж пiдпослiдовностей. Нарештi, були дослiдженнi розбиття простору, що породжує випадкове VP-дерево. Отримано результат про скiнченнiсть моменту першого повернення в певнi стани цих розбиттiв, доведено iснування стацiонарного розподiлу вiдповiдного ланцюга Маркова на множинi розбиттiв та збiжнiсть до нього, а сам стацiонарний розподiл пiдраховано у явному виглядi . Основнi теоретичнi результати супроводжуються математичним моделю- ванням та комп’ютерними симуляцiями виконаними за допомогою мови програмування Python3, що пiдтверджують вiдповiднi твердження та дають краще уявлення про дослiджуванi величини. Дисертацiйна робота має як теоретичне так i прикладне значення. Випад- ковi дерева мають численнi застосування в аналiзi структур даних та алгоритмiв, а також для моделювання процесiв еволюцiї та поширення в багатьох прикладних науках, зокрема бiологiї, медицинi, соцiологiї, економiцi та iнших. Отриманi в роботi результати можуть знайти застосовування в згаданих сферах, а запропонованi математичнi методи можна використовувати для подальших дослiджень iнших класiв дерев.uk-UAДисертація