隨機(jī)樹中一些變量的極限定理.pdf

1、本文主要研究與幾種隨機(jī)樹相關(guān)的一些隨機(jī)變量的極限性質(zhì)，例如：隨機(jī)二叉搜索樹中三類頂點的數(shù)目，均勻遞歸樹中頂點間的距離，區(qū)間樹的大?。?隨機(jī)二叉搜索樹只有三類頂點，即分別含有0，1和2個子點的頂點，我們分別用X<,n>，X<'(1)><,n>和X<'(2)><,n>)記大小為n的隨機(jī)二叉搜索樹T<,n>中這三類頂點的數(shù)目．我們首先建立了關(guān)于X<,n>的遞歸方程，并由此入手，得到了其期望和方差，在此基礎(chǔ)上，選取適當(dāng)?shù)母怕示嚯x，運用壓

2、縮法證明了X<,n>的大數(shù)律和漸近正態(tài)性．接著，又用歸納法證明了X<,n>和X<'(2)><,n>之間具有簡單的線性關(guān)系，并由此直接得到了X<'(1)><,n>和X<'(2)><,n>的極限性質(zhì)． 對于大小為n的均勻遞歸樹，我們研究了均勻遞歸樹中任意頂點i<,n>和頂點n之間的距離D<,i<,n>>,n>在此前的各種文獻(xiàn)中，關(guān)于D<,i<,n>,n>的討論，都需要對i<,n>加上各種限制條件．我們完全解除了這些限制條件，利用經(jīng)典

3、的正態(tài)逼近方法，證明了：當(dāng)樹的大小n→∞時，對任何的0,n>都具有漸近正態(tài)性．并順便得到了D<,i<,n>,n>的大數(shù)律．這一結(jié)果昭示了經(jīng)典極限理論在隨機(jī)結(jié)構(gòu)理論中的作用． 區(qū)間(0，x)按照指定規(guī)則進(jìn)行隨機(jī)分割之后，可以將其對應(yīng)為二叉樹，稱之為區(qū)間樹．我們考慮區(qū)間樹的大小(即頂點數(shù)目)，首先，我們建立了區(qū)間樹的概率空間結(jié)構(gòu)．然后，在S<,x>的母函數(shù)不易求得的情況下，我們先建立了關(guān)