隨機樹的邊界子樹數量

Abstract

在最近的手稿中，我們證明了：給定一整數k，在隨機遞迴樹(Random Recursive Trees)和隨機二元搜尋樹(Random Binary Search Trees)中大小為k 的邊 界子樹數量之極限分佈，隨著k 的改變，產生從常態分佈(Normal Distribution) 到卜松分佈(Poisson)，最後變成退化分佈(Degenerate)的相變。 在 Feng, Mahmoud 和 Panholzer 最近的論文中，也藉由完全不同的方法獨立 地得到相同的結果。在本計劃中，我們打算比較這兩種方法。特別地，我們將說 明我們的方法依舊適用於 Feng 等人的方法難以處理，甚至無法處理的其他種類 似的隨機樹相變結果。

In a recent manuscript, we proved that the limit laws of the number of subtrees of size k on the fringe of random recursive trees and random binary search trees undergo a phase change from normal to Poisson and finally become degenerate when k varies. The same results were independently obtained in a recent study of Feng, Mahmoud, and Panholzer by a completely different approach. In this project, we intend to compare these two approaches. In particular, we will demonstrate that our approach can also be applied to prove similar phase change results for other classes of random trees, whereas the approach of Feng et al. either does not work in an obvious way or is getting very cumbersome.