隨機數位樹的機率分析

Abstract

數位樹是計算機科學裡面一種基本的資料結構，在過去30 年內也已經在 很多文章內被討論。本計劃主要討論隨機數位樹的機率分析，主要分成兩個部 份。在第一部份，我們將回顧過去的研究成果並提出一個可以簡化變異數分析和 更簡單的常數表示式的新方法；在第二個部份，我們將提出一個一般化理論可以 得出數位樹的形狀參數的極限法則、收斂率和局部極限定理等。

Digital trees are fundamental data structures in computer science and have been analyzed in numerous papers over the last three decades. The current project is concerned with probabilistic analysis of digital trees and will consist of two parts: in the first part, we will revisit most of the previous studies and apply a new approach which is expected to greatly simplify the analysis of the variance as well as give easier expressions for the constants involved. In the second part of the project, we will give a general framework for deriving deeper statistical properties such as limit laws, rates of convergency, local limit theorems, etc. of shape parameter of digital trees.