We examine discrete random recursive tree evolution algorithms that, at each time step, either add or delete a node from the tree with complementary probability. Insertion is accomplished using uniform attachment. We are interested in characterizing classes of deletion rules and their effects on common tree functionals (e.g., tree size, leaf count, root degree, etc.).
Chapter 1 opens with a brief description of random recursive trees followed by a discussion of the difficulties node deletion imposes on their study. Chapter 2 outlines the key analytical tools we use to analyze the evolution of random recursive trees subject to deletion rules. These include generating function theory, both formal and analytic, and random walks with matrix-valued transition probabilities. Chapter 3 introduces the key simplifying property of conditional equiprobability and identifies the class of deletion rules possessing it.
In Section 3.1, we focus on conditional equiprobable algorithms with fixed deletion probabilities. We show the behavior of the algorithm falls into three regimes determined by the insertion probability: p < 1/2, p = 1/2 and p > 1/2. Interestingly, the results are independent of the specific deletion rule used.
Continuing our examination of conditional equiprobable algorithms, in Section 3.2, we look at algorithms where the deletion probability is tuned by the operator as a function of the current tree size. We detail two iterative techniques based on continued fractions and systems of orthogonal polynomials for computing exact aspects of the random tree. We also present some theoretical considerations and computational results for developing asymptotic estimates.
In Chapter 4, we consider an algorithm lacking conditional equiprobability. Specifically, we examine a random recursive tree evolution process that intermixes steady expansion with periodic, radical reconstructions termed "revolutions". At each time step, the algorithm either adds a node to the tree with fixed probability p or, with complementary probability, removes a node and then restructures the remaining vertices into a tree of minimum height. In this analysis, we uncover a phase change in the algorithm at p = 1/2 and, unexpectedly, another one at p = 4/5 affecting higher order asymptotic terms.
In Chapter 5, we compute the asymptotic expectation of tree size, leaf count and root degree resulting from the use of different classes of deletion rules. We conclude our research in Chapter 6 with a discussion of results and methods that can be further developed.
The research in Section 3.1 and Chapter 4 has been presented at a conference and submitted for publication. A paper based on the material in Section 3.2 is in development.
|Advisor:||Mahmoud, Hosam M.|
|Commitee:||Modarres, Reza, Lai, Yinglei|
|School:||The George Washington University|
|School Location:||United States -- District of Columbia|
|Source:||DAI 81/11(E), Dissertation Abstracts International|
|Keywords:||Combinatorial probability, Generating functions, Random deletions, Random walks, Recursive trees, Singularity analysis|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be