隨機數位樹之形狀參數之近似分析及阿貝爾可加性

Abstract

分析各種不同類型的數位樹(digital trees)之形狀參數(shape parameters)一直都是演算分析(Analysis of Algorithms)中主要的課題之一。其分析方法可追朔自Knuth一系列具開創性的書籍《電腦程式的藝術》。在該叢書的第三冊中，他推導出許多平均值的近似展開項(asymptotic expansions)，其中涵蓋數個主要的形狀參數。爾後，他的成果被Flajolet, Jacquet, Kirschenhofer, Prodinger, Régnier, Sedgewick等人更進一步地使用。在80年代末和90年代初期，許多研究開始分析變異數。其中使用的方法主要有兩種：(1) Rice method和(2) 涉及梅林轉換(Mellin transform)和解析的去波松化(de-Poissonization)的two-stage approach。後者在Fuchs, Hwang 以及 Zacharovas (FHZ)近期的工作中，給出一般性的架構，用以方便推導出不同類型的形狀參數之期望值和變異數。

本篇論文的目標有兩個：第一，概括論述以上的研究方法以及其發展。 特別是，我們將進一步解釋FHZ的結果。Yu在其碩士論文中使用此方法，並且發現了一個全新的現象：近似展開項包含了發散級數，然而該級數在阿貝爾可加性(Abel Summability)的觀點下有值。第二，我們將展示上述的現象不是特例的情形，而是發生在許多形狀參數的分析中。

一個簡短的大鋼如下：第1章，我們給出定義以及一個簡短的分析歷史；第2章，我們將介紹所使用的工具，特別是上述所提及的two-stage approach以及FHZ近期的貢獻；這些工具將在第3章被用來討論一些已知的結果(其中一個取自Yu的碩士論文)；然後，在第4章，我們將討論一些新的例子以及展示上述的現象；最後，在第5章，我們做一結論，並結束本篇論文。

The analysis of shape parameters of the various classes of digital trees has always been one of the main topics in the Analysis of Algorithms. The foundations can be traced back to Knuth's seminal work ``The Art of Computer Programming". In Volume 3, Knuth derived asymptotic expansions of the average value of many of the main shape parameters of digital trees. His work was then further refined by Flajolet, Jacquet, Kirschenhofer, Prodinger, R\'{e}gnier, Sedgewick and others. In particular, in the late 80s and early 90s, many papers appeared on deriving asymptotic expansions of the variance with two main approaches: the Rice method and a two-stage approach based on Mellin transform and analytic de-Poissonization. The latter approach was further refined in a recent work of Fuchs, Hwang and Zacharovas (FHZ) who gave general frameworks for deriving asymptotic expansions of mean and variance of a vast class of shape parameters.

The purpose of this thesis is two-fold: first we want to survey the above tools and developments. In particular, we will explain in details the recent approach of FHZ. This approach was used in the recent master thesis of Yu, who discovered a new phenomenon for a shape parameter in digital trees, namely, the asymptotic expansions of the moments contain divergent series which have values by using Abel summability. Another aim of this thesis is to show that the phenomenon discovered by Yu is not special but occurs in the analysis of many other shape parameters as well.

A short outline of the thesis is as follows: in Chapter 1, we give definitions and a brief history of the analysis of shape parameters in digital trees. In Chapter 2, we will introduce the tools, in particular, the above mentioned two-stage approach and the recent contributions of FHZ. These tools will be used in Chapter 3 to discuss some known results (one of them being the result of Yu from his master thesis). Then, in Chapter 4, will discuss some new cases which also exhibit the phenomenon observed by Yu. We will finish the thesis in Chapter 5 with a conclusion.