Electronic Thesis/Dissertation


On Fast Growth Models for Random Structures Open Access

Downloadable Content

Download PDF

We introduce and study three fast growth models for random structures: hierarchical lattice networks, dynamic Pólya-Eggenberger urns, and exponential binarytrees.We study the degree prole of random hierarchical lattice networks. At everystep, each edge is either serialized (with probability p) or parallelized (with probability 1 − p). We establish an asymptotic Gaussian law for the number of nodes ofoutdegree 1, and show how to extend the derivations to encompass asymptotic limitlaws for the number of nodes of higher outdegrees. The asymptotic joint distributionof the number of nodes of outdegree 1 and 2 is shown to be bivariate normal. Nophase transition with p is detected in these asymptotic laws.For the limit laws, we use ideas from the contraction method. The recursiveequations that we get involve coecients and toll terms depending on the recursionvariable and thus are not in the standard form of the contraction method. Yet, anadaptation of the contraction method goes through, showing that the method haspromise for a wider range of random structures and algorithms.We study new types of Pólya-Eggenberger urn schemes with a dynamic replacement matrix. We consider urn schemes of two colors (white and blue) in this novelclass. The nature of the governing limit stochastic relation exhibits a phase changewhen the addition function meets a regularity condition. We show that when thecondition is met, the proportion of white balls in such an urn converges to a Bernoullilimit distribution. This is to be contrasted with dynamic Pólya-Eggenberger urnswith slow addition function, where the limit distribution is believed to be continuouson the interval [0,1]. We demonstrate that the condition is satised when the addition function, along a subsequence of draws, grows exponentially (the exponentialviPólya-Eggenberger urn) or faster (the super exponential Pólya-Eggenberger urn).The exponential Pólya-Eggenberger urn may be suitable as a realistic model formany fast-growing random structures around us today. With the growth of random networks taking place faster than ever before, super exponential urns may beapplicable in the near future.We study the internal and external proles of the random exponential binary tree(EBT). As customary, the tree is extended by padding each leaf node (consideredinternal), with the appropriate number of external nodes, so that the outdegree ofevery internal node is made equal to 2. In a random EBT, at every step, eachexternal node is promoted to an internal node with probability p, stays unchangedwith probability 1 − p, and the resulting tree is extended.We get exact expectations for the numbers of internal and external nodes ateach level. Asymptotic analysis shows that the average external prole is richest atlevel 2pp+1n, and it experiences phase transitions at levels αn, where the α's are thesolutions to an algebraic equation. The rates of convergence themselves go throughan innite number of phase changes in the sublinear range, and then again at thenearly linear levels.The ndings on hierarchical lattice networks of this work are published in [40].At present, the ndings on dynamic Pólya urns are under review at Statistics &Probability; Letters, and the ndings on exponential binary trees are submitted toMethodology and Computing in Applied Probability

Author Language Keyword Date created Type of Work Rights statement GW Unit Degree Advisor Committee Member(s) Persistent URL