一種新的動差法與其應用

A new variant of the method of moments with applications

陳哲皓(Che-Hao Chen)

指導教授 ： 符麥克

國立交通大學/理學院/應用數學系暨研究所/碩士(2009年)

https://doi.org/10.6842/NCTU.2009.00238

摘要

演算分析在計算科學裡是一個重要的工作，這可以幫我們了解這
些演算法適當的用途。在這篇論文中，我們將會用機率的理論來了解
一個演算法所須要運行的時間。為了使這樣機率的方法可以運作，首
先我們考慮演算法的輸入為一個適當的隨機模型，然後讓運行的時間
成為隨機變數，這樣我們就可以嘗試算出它的期望值和變異數，進而
去了解取極限後的行為。在最近幾年，method of moments 已經變成
了解決這些問題的標準工具。

在論文中，我們對一個叫優先樹的資料結構和它們的分析感到興
趣，也會使用method of moments來簡化最近一些優先樹結果的證明。
然而，在使用這個方法的過程中，我們會遇到一些困難，此時，我們
將會介紹一個新的method of moments 來解決這些問題。

以下是我們的論文概述，在第一章，我們將會介紹method of
moments，並且也會介紹優先樹和關於這資料結構近幾年的結果。第
二章，我們會用一個新的method of moments 重新證明第一章所提到
的一個結果。第三章，我們再一次使用這方法來解決一個比較複雜的
問題。最後在第四章會給一個結論。
中

關鍵字

動差法

並列摘要

Analyzing algorithms in order to understand their usefulness
and appropriateness is a key task in computer science. In
this thesis, we will use probability theory to analyze the
running time of algorithms. In order to perform such a
probabilistic analysis, we will first fix a suitable random
model for the input. Then, the running time becomes a
random variable and properties such as the mean value and
the variance are sought. Once the latter properties are
understood, one also wants to clarify the limit behavior. In
recent years, the method of moments has become a standard
tool for this purpose.

In this thesis, we are interested in a data structure, called
priority trees, and their analysis. One of the goals of the
thesis is to simplify the proofs of some recent results on
priority trees by using the method of moments combined with
asymptotic transfers.
However, in doing so, some new problems will arise which we
will overcome by introducing a new variant of the method of
moments.

We give a short outline of the thesis. In Chapter 1, we are
going to introduce the method of moments. Moreover, we will
introduce priority trees and explain some recent results
concerning this data structure. Then, in Chapter 2, we will
introduce our new method and re-prove some of the results
mentioned in Chapter 1. In Chapter 3, we will apply our new
approach to a more complex example. We will end the thesis
with a short summary in Chapter 4.

並列關鍵字

method of moments

參考文獻

for ¯nding the maximum in a broadcast communication model, J. Algorithms, 46,

[1] P. Billingsley, Probability and Measure, Third Edition, John Wiley & Sons, New

York, 1995.

[2] W. M. Chen, H. K. Hwang, Analysis in distribution of two randomized algorithms

140-177 (2003).