隨機樹上的分支數：兩種逼近的比較

Abstract

Robert E. Horton 和Arthur N. Strahler 利⽤「Horton-Strahler number 」來做河流的分類。然⽽，之後它被利⽤在資訊科學的領域，並且稱 為「暫存器函數」，還有再其它領域也有應⽤。 r-分⽀是⼀個重要且和暫存器函數有關的參數。在幾⼗年前John W. Moon 有⼀篇⽂章是分析r-分⽀的⼀些隨機性質，⽽這些是建⽴在 滿⼆元樹和均勻分布之上，他⽤的⽅法為把樹拆成⼦樹做遞迴運算。 最近Benjamin Hackl 、Clemens Heuberger 和Helmut Prodinger 也有 ⼀篇⽂章，是利⽤了另⼀種⽅法來分析同樣的參數，⽽這個⽅法是⽤ 隨機鏈取代節點。較新的這篇⽂章，並沒比較兩種⽅法有何不同。 這篇論⽂的主要⽬標為介紹這兩種⽅法並比較它們。第⼀種⽅法， 因為Moon 寫該篇論⽂時，奇異點分析並還沒發展完全，所以我們會 ⽤現代的奇異點分析重新詮釋。⽽第⼆種⽅法，我們主要呈現Hackl 、 Heuberger 和Prodinger ⽂章的內容。另外，我們會利⽤最近Stephan Wagner 所得到的結果，並且利⽤第⼀種⽅法得到極限分布的結果。 除了做以上的分析，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.