隨機樹的邊界子樹數量

The Number of Subtrees on the Fringe of Random Trees

檔案

本條目沒有附加檔案。

日期

2007

類型

補助單位

行政院國家科學委員會

計畫編號

NSC96-2628-M009-012

語言

中文

摘要

在最近的手稿中,我們證明了:給定一整數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.

所屬典藏

研究計畫
顯示完整詮釋資料 統計資料

引用此條目

符麥克, & FUCHS MICHAEL (2007). 隨機樹的邊界子樹數量. https://ir.lib.nycu.edu.tw/handle/11536/102914

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/102914