Dissertation/Thesis Abstract

Random Recursive Tree Evolution Algorithms: Identification and Characterization of Classes of Deletion Rules
by Saunders, Arnold T., Jr., Ph.D., The George Washington University, 2020, 114; 27830773
Abstract (Summary)

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.

Indexing (document details)
Advisor: Mahmoud, Hosam M.
Commitee: Modarres, Reza, Lai, Yinglei
School: The George Washington University
Department: Statistics
School Location: United States -- District of Columbia
Source: DAI 81/11(E), Dissertation Abstracts International
Subjects: Statistics
Keywords: Combinatorial probability, Generating functions, Random deletions, Random walks, Recursive trees, Singularity analysis
Publication Number: 27830773
ISBN: 9798645447540
Copyright © 2021 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy