Counting Branches in Random Trees: A Comparison of Two Approaches
|關鍵字:||暫存器函數;r-分支;隨機樹;Register function;r-branch;Random trees|
|摘要:||Robert E. Horton 和Arthur N. Strahler 利⽤「Horton-Strahler number
W. Moon 有⼀篇⽂章是分析r-分⽀的⼀些隨機性質，⽽這些是建⽴在
最近Benjamin Hackl 、Clemens Heuberger 和Helmut Prodinger 也有
Heuberger 和Prodinger ⽂章的內容。另外，我們會利⽤最近Stephan
除了做以上的分析，Hackl 、Prodinger 和Sara Kropf 也有利⽤第⼆
The Horton-Strahler number, proposed by Robert E. Horton and Arthur N. Strahler, was originally introduced for the classification of river systems. However, it was later also used in Computer Science (where it is called the register function) and found many other applications in diverse areas. One important parameter related to the Horton-Strahler number is the number of $r$-branches. For a complete binary trees that is chosen uniformly at random, stochastic properties of this number were analyzed in an old paper of John M. Moon with a recursive approach based on the root decomposition of a tree. Recently, the same parameter was also analyzed in a paper of Benjamin Hackl, Clemens Heuberger and Helmut Prodinger with a different approach, namely by letting the tree grow via replacing nodes by chains. The latter paper did not include a detailed comparison of the two approaches. The main goal of this thesis is to describe the above to approaches for the sake of comparing them. For the first approach, this will be done by rephrasing it with the modern theory of singularity analysis which was not fully developed when Moon wrote his paper. For the second approach, we will mainly follow the presentation in the paper of Hackl, Heuberger and Prodinger. Moreover, using recent result of Stephan Wagner, we will prove a central limit theorem as well (using the first approach). Apart from analyzing the above number, Hack and Prodinger (jointly with Sara Kropf) also used the second approach for discussing related problems. We will show that these results could be also alternatively derived with the first approach above.