Profile of Random Exponential Binary Trees

Yarong Feng () and Hosam Mahmoud
Additional contact information
Yarong Feng: The George Washington University
Hosam Mahmoud: The George Washington University

Methodology and Computing in Applied Probability, 2018, vol. 20, issue 2, 575-587

Abstract: Abstract We introduce the random exponential binary tree (EBT) and study its profile. As customary, the tree is extended by padding each leaf node (considered internal), with the appropriate number of external nodes, so that the outdegree of every internal node is made equal to 2. In a random EBT, at every step, each external node is promoted to an internal node with probability p, stays unchanged with probability 1 - p, and the resulting tree is extended. We study the internal and external profiles of a random EBT and get exact expectations for the numbers of internal and external nodes at each level. Asymptotic analysis shows that the average external profile is richest at level 2 p p + 1 n $\frac {2p}{p+1}n$ , and it experiences phase transitions at levels a n, where the a’s are the solutions to an algebraic equation. The rates of convergence themselves go through an infinite number of phase changes in the sublinear range, and then again at the nearly linear levels.

Keywords: Binary tree; Random graph; Internal (external) profile; Asymptotic analysis; Phase transition; Two-dimensional recurrence; Generating function; Primary: 90B15; Secondary: 60C05, 05C80, 65Q30 (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s11009-017-9578-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:metcap:v:20:y:2018:i:2:d:10.1007_s11009-017-9578-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/11009

DOI: 10.1007/s11009-017-9578-z

Access Statistics for this article

Methodology and Computing in Applied Probability is currently edited by Joseph Glaz

More articles in Methodology and Computing in Applied Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().