（概率论与数理统计专业论文）随机树中一些变量的极限定理.pdf

摘要 本文主要研究与几种随机树相关的一些随机变量的极限性质，例如：随机二叉搜索 树中三类顶点的数日，均匀递归树中顶点问的距离，区间树的大小 随机二叉搜索树只有三类顶点，即分别含有o ，1 和2 个子点的顶点，我们分别用 k ，州产) 和x 乎) 记大小为佗的随机二叉搜索树磊中这三类顶点的数目我们首先建 立了关于墨。的递归方程，并由此入手，得到了其期望和方差，在此基础上，选取适当 的概率距离，运用压缩法证明了的大数律和渐近正态性接着，又用归纳法证明了 墨；和砖? ) 之间具有简单的线性关系，并由此直接得到了弼j 和巅? ) 的极限性质 对于大小为礼的均匀递归树，我们研究了均匀递归树中任意顶点和顶点他之 间的距离现。弦在此前的各种文献中，关于现舭的讨论，都需要对该加上各种限制 条件我们完全解除了这些限制条件，利用经典的正态逼近方法，证明了：当树的大小 n _ 。时，对任何的o o ， 工p ( x ，y ) ：( e i x y l p ) ； 1 ：l ix y 峙 ( 2 2 ) 条件1 。与条件2 。显然满足，条件3 。可由m i n k o v s k i 不等式得到l p 距离的定义 域勿不能取为整个影，而应取为9 = x ，e i x i p o o 】 值得注意的是，定义2 1 所定义的距离并不能满足概率论研究中的所有需要，它只 能用来考察口s 收敛性，因为其中的条件1 。过强为了研究随机变量序列的其它收敛 性，应当削弱条件1 。，将其中的当且仅当改为当。这种削弱意义下的距离已经不具有 完全等同性，故将之称为概率距离 定义2 2 设勿为可允许的，称映射d ：勿2 = 9 9 _ 冗+ = 【o ，。o ) 是9 上的概 率距离，如果它满足定义2 。1 中的条件2 。和条件3 。，且具有 1 。a ( 不完全等同性) ：当p ( y = x ) = 1 时，有d ( x ，y ) = o 显然，定义2 1 意义下的随机变量间的距离都是定义2 2 意义下的概率距离而且 不难验证，经典极限定理中一些常用的距离，都是定义2 2 意义下的概率距离，但未必 是定义2 1 意义下的随机变量问的距离如： 例2 3 ( 一致距离) j d ( x ，y ) ：= s u p l p ( x z ) 一p ( y z ) l = s l l p f j x ( z ) 一睁( z ) 1 ( 2 3 ) z 7 已lz 7 己i l 在这里，p ( x ，y ) = o 当且仅当p ( x 0 ，对实数z ，记 z 0 )：= i z l 8 1 z = l z l 8 s i g nz ， 1 3 中国科学技术大学博士学位论文 设x 与y 都是实值随机变量，令 ( x ，y ) ：= e l x 8 _ y s i 的值取决于联合分布c ( x ，y ) ，它是一个复杂距离 例2 6 设s o ，而x 与y 都是实值随机变量，令 ( x ，y ) ：= l z l 8 l d ( p ( x 2 ，用归纳法即可 口 定理2 2 如果d 是理想距离，则对任意两个越机变量x 与y ，以及任何实常数彤 都有 d ( x + n ，y + 口) = d ( x ，y ) ( 2 ，i o ) 证明：由于常数g 与随枧变量x 和y 都独立，所_ 以由正则性知碰x 戤y + 8 ) d 僻，y ) 反之，常数一口与随机变量x + 口和y + o 都独立，所以又有 口 d ( x ，y )= d ( x + o 十( 一口) ，y + 口+ ( 一n ) ) d ( x + o ，y + o ) 定理2 3 如果d 是3 阶理想距离，更f j 对任意两个随机变量x 与y ，以及任何一个 实常数c 0 ，都有 d ( c x ，c y ) = i c l 8 d ( x ，y j ， 换言之，关系式( 2 。8 ) 中的不等号可以写为等式， 证明：在( 2 8 ) 式中取x 7 = 以，y = c y ，c ，= ，就有 d ( x ，l ，)= d ( c ，x 7 ，c ，y ) 1 5 ( 2 1 1 ) 中国科学技术大学博士学位论文 | c | 5 d ( x 7 ，y 7 ) 1 2 寿d ( 彬) ， 亦即d ( c x ，c y ) j e f 3 矗( x ，y ) ；结合( 2 8 ) 式，即得( 2 1 1 ) 式 口 容易看出，一致距离p 和全变差距离盯是。阶的理想距离；而工程距离研是1 阶 的理想距离除此之外，还有一些常用的理想距离，例如。 例2 8 ( p r o h o r o v 距离) 以玖表示随机变量的分布，亦即对b 纺1 ，有p x ( b ) = p ( x b ) ，那么尸r o 九o u 距离就是 丌【义，y ) = 7 r 【r y ，于y ) ：= i n e ：暇( b ) p y ( b 8 ) + e ，r ( b ) 既( b 5 ) + ，b 留) ， ( 2 1 2 ) 其中伊是召的邻域，即伊= z ：l z y i ( 2 1 3 ) 可以验证，p r o h o r o v 距离和a 一距离都是s = o 阶的理想距离 2 3z o l o t a r e v 距离 z o i o t a l e v 距离是由俄罗斯数学家z o l o t a l c v 于2 0 世纪7 0 年代引入的，它被广泛地 应用在现代极限理论之中，尤其是关于渐近正态性研究中的不可或缺的工具，近来更有 人发现它在研究渐近于其它分布时的重要作用和方便之处 为给出z o l o t a r e v 距离的定义，需要先定义一个函数集苫。： 定义2 5 设s o ，m = 嘲，即小于s 的最大整数写3 = m + q ，其中o o 时， z o l o t a r e v 距离岛的定义是： g ( x ，y ) ：= 裟l e ( ，( x ) 一，( y ) ) i ， ( 2 1 5 ) ，蕊i 其中，集合双如定义2 5 所示而当s = o 时，则定义为 件 白：= 。甄6 s u 需要特别说明的是，如果o = s u p i p ( x j e 7 ) 一p ( y b ) i ：b 纺) = ( x ，y ) 另一方面，如果记乱。= ，：l ，( z ) 一，( y ) i 1 ，z ，y 冗) ，则显然有s oc & 。任何 ，孑( 以) 对任何实数款箩，都满足不等式j ，( z ) 一歹( 们l 1 ，这意味着对每个，孑( 南) ，都 存在某个实数c = c ，使得 ，则无论如何，都不能有i ，( z 1 ) 一，( z 2 ) l l ，此为不可 中国科学技术大学博士学位论文 能因此 白( x ，y ) = s u pi ，( z ) d ( 厥( z ) 一n ( z ) ) l ，曲o 亿 是? l 厶，扛) 烈f x ( z ) 一h ( z ) ) l ，s d l ，冗 = ，1 l pl ( ，( z ) 一c ，) d ( 版( z ) 一j v ( z ) ) l ，醣，l 歹冗 冬定墨 ：装叭z ) 一c ，l 厶取( z ) 一r ( z ) ) i )，吉d ，l z 7 己，冗 j 丢厶l d ( 取( z ) 一砖( 硼i 综合上述两方面，即得命题中的断言 口 为了介绍s 为正整数时的表达式，先给出一个显然的引理 引理2 1 设g ( z ) 为冗上的有界变差函数， s o ，令 趵：= 湍枞 ( 2 1 6 ) 其中r ( ) 为g 8 m m 8 函数则当s l 时，有 p 1 如) = 丢s 9 ( 矾 定理2 5 当s 为正整数时。c 。可以表示为： 泓，y ) = 仁p ( 眦卜砷) ) i 如 = 仁j 鱼最乒d ( 取c u ，一r c u ，) l 如 c 2 肼， 特别地，当s = 1 时，即为 ，y ) - 仁陋) - 眦) l 如 = 门眨1 ( 小巧1 ( 札) 卜 ( 2 r 1 8 ) 证明：首先指出，当s 为正整数时，对于，我们有 ，( s 一1 ) ( z ) 一，( s 一1 ) ( 可) l l z 可i ， vz ，可7 宅， 1 8 第二章概率距离 这表明，( s ) 几乎处处存在，并且恒有i ，( s ) ( z ) ! 1 先证( 2 1 8 ) 对于，孑1 ，由分部积分，得 ( x ) 叫y ) ) f = 仁弛) d ( 取( 圹晰) ) f = i 仁八z ) ( 脚) 一眦州 = 1 仁八妒。( 眦) _ 脚) ) 如l s 仁惝小脚) i 如 s 仁) 一眦) i d z 这表明 “础) 仁胁) 一脚) 陋 另方面，如果令 ，n ( z ) ：= 仁s i g i l ( k ( 缸) 一日( u ) ) 川牡i n ) ) 札讥m 则对任何固定的扎n ，都有，n 笤1 ，从而 泓，y ) 州仁饰) d ( 殿( 矿眦) ) ni ，一o 。 、7 i = s u p l 仁肺) ( 眦如l = s u p 啡) _ 眦) 卜 = 仁陋) 一脚) k 琢售上殓网刀回，剐僭瞄l 苎j 瓦- 对于s = 2 ，虢，连续作两次分部积分，运用( 2 ，1 6 ) 式，并注意i ，( z ) l 1 ，可得 ( x h ( y ) ) j = 仁m ) d ( 圾一眦) ) ； = l 仁八z ) ( 脚) 一眦测 = l 仁九彬。( 眦) - 眦) ) 如f 中国科学技术大学博士学位论文 = l 仁，( 圳坪她h l = l 仁尸1 ( 脚，一脚酬 仁k 咿( 眦) - 脚) ) 卜 仁l 1 ( 眦h i 如 = 仁l c ，d ( 脚卜脚卅； 一般地，对于正整数5 3 ，我们对，孑。连续作s 次分部积分，可得 上式表明 f e ( ，( m ，( y ) ) i = f 仁产k 驴。1 ( 脚) 一脚) ) 如f 仁i 产k ) ll 广，( 如嘶( z ) ) l 如 i 产( z ) li 8 1 ( 如( z ) 一如( z ) ) i 如 ，一o 。 4 仁i 旷1 ( 酬一脚) ) 卜 = 仁l 笋d ( 脚，一脚，) l 出； 泓y ，仁i 仁与乒d ( 脚卜脚卅 反之，设函数南满足如下条件； 则有，o 孔，从而 ( z ) = s i g n 纠( 圾( z ) 一如( z ) ) ， 6 ( x ，y ) l e ( 南( x ) 一而( y ) ) = 仁l 旷1 ( 脚，一眦她 = 仁l 仁与笋d ( 脚卜眦卅 综合上述两方面，即得所证 口 第二章概率距离 2 4z o l o t a r e v 距离的基本性质 在研究随机树中一些变量的极限分布的时候，如果使用压缩法，根据变量的不同的 特点，就要选取不同的理想距离，而在考查渐近正态性的时候，z o l o t a r e v 距离就较为 适用，因此，我们需要在这里详细介绍一些z 0 1 0 t 粕c v 距离的基本性质 除上一节所述z o l o t a r e v 距离的一些性质外，它还具有如下的一些基本性质 定理2 6 历2 d 口他口距离g ( s o ) 是一个s 阶的理想距离 证明：由定义易知，对任何s 芝o ，g 都是简单距离 对于，孔，我们引入两种变换： ( a 掣，) ( z ) ：= 厂( z + y ) ， ( b 。，) ( z ) ：= c - 5 ，( 凹) ， 其中，箩冗，c o 容易看出；这两个变换都是鼠到自己的一一对应 令z 是与x 和y 都独立的随机变量，则有 l e ( ，( x + z ) 一，( y + z ) ) l l e ( a 可，( x ) 一a 可，( y ) ) l d f z 妇) 因此， 岛( x + 互y 十z ) s u p f e ( ，( 誓) 一，( y ) ) f ：，a 掣鼠) 趔乙( y ) ， 既然对任何y 冗，都有a 孔= 鼠，故上式右端就是g ( x ，y ) ，即g 具有正则性 而对任何e o ，我们有 i e ( ，( 以) 一，( c y ) ) l = 矿l e ( b c ，( x ) 一b c ，( y ) ) ， 因此就有 己( d ，c y ) 、二矿s u p l e ( ，( x ) 一，( y ) ) l ：，b 。鼠 ： 由于对任何c o ，都有b c 钆= 藐，所以 s u p i e ( ，( x ) 一，( y ) ) i ：，b 。孔) = g ( x ，y ) ， 故得g 的s 次齐次性 口 2 1 中国科学技术大学博士学位论文 定理2 7 设8 o ，m = h 是小于s 的最大整数，写s = m + q 则当6 ( x ，y ) o ，对任何m + 1 元有序实数组o o ，d 1 ，n m ，都有 因此对任何七= 1 ，m ，都有 6 ( x ，y ) ；i l pl e 七x 一e n 盘y 麻 = s l l pa 惫l e x 七一e y 钆 o k 0 亦即 瞰七制忆黜， 再由厶( x ，y ) o ，m = 【s j 则厶( x ，y ) o 。的充分必 要条件是t k 焉霸嚣两 o ，当e i x r + e i y | s o 。使得 证明：记m = h ，即小于s 的最大整数， 式易证 s = m + q 由于o o ，使得对任何随机变量，都有 7 r 1 + 5 ( x ，y ) c ，g ( x ，y ) 定理2 1 0 对任何随机变量x 与y ，对s = m + a o ，其中m = 【s j ，o 1 ，则其父点是顶点- n j ( 2 ) ：如果2 i 几，则顶点i 无左子点；否则，其左子点就是顶点2 i ( 3 ) ：如果2 + 1 n ，则顶点l 无右子点；否则，其右子点就是顶点2 t + 1 ， 如果二叉树不是满二叉树也不是完全二叉树，在存储的时候，通常将该二叉树先牢 全为完全二叉树，并设定那些后补的顶点的标号皆为o ，存储后补的顶点时，空一个存 储单元在那里即可所以，如果二叉树中空节点很多的时候，这样就会造成存储空问的 2 7 中国科学技术大学博士学位论文 巨大浪费，而且，一般我们将数据按照二叉树的形式存储在计算机中之后，还要设法对 其中所含数据进行遍历，检索等操作在处理这些情况的时候，原先的那种自上而下， 自左而右的标号方法就显得并不是很合理，于是，对于需要存储的数据块( ：1 2 2 ，2 n ) ， 不妨用( 1 ，2 ，n ) 对其进行取代( 这是因为，即使数据块中有相同的数据，它在存储时 也要占据不同的存储单元，所以，可以视其不同，这样，我们就可以将( 2 1 ，2 2 ，k ) 看 作为一组严格有序的数，自然就可以用( 1 ，2 ，礼) 代替之) ，我们采用如下的二叉搜索 树的形式对数据进行存储，则在遍历，检索的时候就会方便许多 二叉搜索树是二叉树的一种它的构造方法如下；设有一个严格有序集( 1 1 ：2 ，l t l ) ， 不妨设它就是( 1 ，2 ，n ) ，对 l ，2 ，几) 任意一个置换( 丌1 ，丌2 ，) ，首先将该置换中 的第一个元素丌l 对应为二叉搜索树的根点；对于元素丌2 ，如果丌2 小于根点霄l 就将它对 应为左子树的根点，否则，将它对应为右子树的根点；然后，再依次考虑元素乃o 2 ) ， 仍然将它们先和根点进行比较，若 2 ( 3 2 ) 证明：补充定义三o 当n = 1 和n = 2 时，显然有x 1 = 尥= 1 ，所以 e 【墨】= e 【拖】_ 1 当礼22 时，由于和n 一1 一巩同服从 o ，1 ，礼一1 上的均匀 分布，所以，如果我们在递归式( 3 1 ) 两边取期望，并对= 歹取条件，则有 e p h l= e 【x 【，n 】+ e 【j 一1 一l r 竹】 = e 薹冯pe = j ， + e 薹砖一t 一，p c 巩= 歹， =e l 冯p ( = j ；) | + el 砖一l j p ( 巩= 歹) l ij = ollj = o1 第三章随机二叉搜索树中几类理地耋堕 = 去e 萎玛 + 熹e 匿焉一t j = 要萎酬 唰孤一+ 昙争玛， = 要+ 孚( 刍薹叫 n仃 仃一l _ ：， ：罢e 陬一。1 + 寻e 一1 1 几 亿 = 等e 陬_ 1 j ：= 一j l a n 一1 i n 。 利用该递推关系式依次递推，即得 e 陬】- 半者e 隔一2 】 = 墓等酬 礼+ 1 2 下 证毕口 再来计算k 的方差 定理3 6 对于大小为n 的随机二又搜索树中的叶点数目，有 v 缸阢j = v 缸阮j = o ， 【】= 等，n 3 ( 3 3 ) 证明：由于x l = 拖= 1 ，显然有v _ a r 阢】= v 缸阢】= o 为了得到礼3 时v 撕【矗】 的表达式，需要先计算v 圳拖1 对递归式( 3 1 ) 两边平方后取期望，并关于= j 取条件，同时注意到玛呈碍， 即得 e 【x ：1 = e 【( x “+ 磁一l 一) 2 1 3 5 中国科学技术大学博士学位论文 由上式和= 0 ，x 1 = 义2 = l ，得： e 【霹】= ；( e 穑】+ e x 翻十e 【砖】) =2 因此，由( 3 2 ) 式，我们有 【尥】 ：一1 一】 1 1 一j ) 2 p ( = j i ) j 1 】e 【x 1 】+ e d ，2 】e 【】) + 0 ) e 【焉】一e 2 拖】 2 一( ) 2 = 吾 容易看出，v 撕阢】的结果也满足( 3 3 ) 式 再来建立隅】的递归关系式由于呈冗一l 一为nl ，n 1 ) 上的均 匀分布，所以，如果 结果，我们就有 v 【】 对( 3 1 ) 式两边取方差，并关于既= 歹取条件，同时结合( 3 2 ) 式的 e 【e 【】2 e 卜+ 粕一孚 2 e 匿( 玛懈h 一孚) 2 嗽刊 疆羡r 一扣 一小一糖叫协 ”o巧+ 即批铂叫。弘曲卅 一鼢一怪啦扣 x l e + + 2髟 + 耻d h e + 2 3 + 2 3 = 第三章随机二叉搜索树中几类顶点的数目 由定理3 4 ，我们知道玛至碍，且对任意正整数歹，奄o ，码和雄相互独立因此， v 打【k 】= 要薹ek j 铡2 + 罢薹( ek 一等 e 卜小j 一字j ) nn l 暑址】 再利用所得的关系式，推出关于方差的递推关系式 v a r 陬】_ 砉隅一1 】+ 丢吲 nnf l l = 扣睾( 刍薹v a 恻) = 昙协阢- 1 1 + 孚- 1 】 = 半一】 于是，对任意正整数n 3 ，我们有 刚= 半鲁一2 】 = 夏岩娜3 ， 3 7 等 似! l i 中国科学技术大学博士学位论文 礼+ 1 2 1 r 证毕口 由五；的期望和方差的表达式，我们可以立即得到下面两个推论 推论3 1 若为大小为n 的随机二叉搜索树中的叶点数目，则当n 2 时，有 e 嗽】- 坠等业 ( 3 4 ) 证明：结合( 3 2 ) 式和( 3 3 ) 式，即有 e 【霹】= v a r 隅】十【e 】2 = 等+ ( 字) 2 一o 。一十i 。_ 一l 1 8 3 = 坠等业，n 2 = 一f t ： z证毕口 推论3 2 若为大小为n 的随机二叉搜索树中的叶点数目，则当竹一时，有 p1 i 万一j 。 证明：由c l l c b y d c v 不等式，对任意 o ， p ( 1 舞一牡) = p ( 1 学l ) = p ( f 等掣l e ) 崭替 ： 1 1 8 ( 佗+ 1 ) 2 令佗_ o c ，则有 熙p ( | 斋一言l ) 蛐 由于上式中左边的概率为非负，所以，它的极限必为o 此即表明( n + 1 ) 依概率收 敛到l 3 证毕口 第三章随机二叉搜索树中几类顶点的数目 3 4 压缩法和极限分布 在本节中，我们将采用压缩法证明本章的主要结论，即关于x n 的渐近正态性 压缩法最初是由r 凰i e r ( 1 9 9 1 ) 分析“q l l i 妇o r t 算法时引入的后来， r a c h e v r t i s c h c n d o r f ( 1 9 9 5 ) 对这种方法作了一些推广，并正式提出“压缩法”的概念最近， r 庙l e r ( 2 0 0 1 ) ，n e i n i n g e r ( 2 0 0 1 ) ，n e i n i n g e r & 砸l s c h e n ( i o r “2 0 0 4 ) 对压缩法作了更广泛的推 广，并引入了多维的情形n e i n i n g e r ( 2 ( ) 0 2 ) 最先将压缩法应用到均匀递归树和随机二 叉搜索树上后来它就被广泛地用来证明随机树中一些随机变量的极限分布 压缩法在处理具有如下特定形式的递归关系的随机变量的极限分布时，十分有效 记n 为自然数集，设存在某个正整数咖，当n 几。时，随机变量序列 钒) n 1 ，有 如下递归分布式： 骗呈，t q 毁。+ 巩， ( 3 5 ) t n 其中，随机变量厶， 只取值于集合o ，1 ，2 ，n l ，q 箩只取值于自然数集n ；且对任意 n n 和o 歹n l ，随机变量( 玩，k ，) ，q 相互独立， 厶= ( 厶，1 ，厶，1 ) ， 玩= ( ，1 ，1 ) ； 对任意歹和f ，硝是岛的独立复制；并令初始条件为q o 三o 压缩法在求解满足上述条件的q 凡的极限分布的时候，一般分为如下四个步骤 第一步：求骗期望记的期望为：= e ，如：= e 鼠，则由( 3 5 ) 式， 一般地，该式可以整理为 = e k ；+ 如。 t n t i 一1 = 厶( 歹) e 【，d 彩十厶， j = 0 其中，厶0 ) 为常数通常我们由此关于铷的递归式，可以解得铷或者采用一些技巧 至少求得它的渐近式 3 9 中国科学技术大学博士学位论文 第二步：正则化将q n 进行适当的正则化使得正则化之后得到的k 收敛到极限 碥：里2 二塑， 孙 其中，正则化参数鼽 0 鼽一般取为与、冈面砺同阶，如不清楚、冈磊砺的阶，则要 进行猜测和反复尝试将进行正则化之后，我们有 若记： k 呈蕃l 警噬：+ 著佗n 9 “ n r 等， 磁= 垒兰篓坚垒警+ 风一e 瓯 t n “ 则，有正则化后关于砭的递归关系式 一e 巩， k 呈簖j 碟) + 磷 ( 3 6 ) i 】n 其中，巧是巧的独立复制 第三步：猜虼的极限分布即由k 的递归式，猜测碥的极限分布或者所 满足的关系式若厶， 趋于无穷，同时还有( 磷 ，懿) 依分布收敛到( ，b ) ，则可以得到 关于彤的一个递归关系式 、厂 2 n一 上 呈 群，。：+ 磁， l n llj ， k 磁+ b ， i n ( 3 7 ) 其中，对任意i n ，( k ，口) ，且眦相互独立，m 是的独立复制 第四步：压缩映射简而言之，就是选取一个理想的概率距离，运用压缩映射证明： 在该概率距离下k 收敛到w 我们在这_ 步中要做的是，选取一个合适的概率距离， 证明( 3 6 ) 式的右边和( 3 7 ) 式的右边在该理想概率距离下收敛到。即可 4 0 第三章随机二叉搜索树中几类顶点的数目 如前，我们已经得到了的递归式，也得到了它的期望方差，所以，对于矗的 正则化也不是问题，于是，为证) 厶的渐近正态性，我们就要要选用一种理想的概率距 离 由定理2 6 知，参数为s 的z o l o t a r c v 距离岛( 参见定义2 6 ) 就是个理想距离，它 不仅具有理想距离的正则性和齐次性，而且，它还拥有第二章所介绍的诸多优良性质， 这将大大有助于压缩法最后一步的实施，并最终得到我们想要的结论 我们就选用3 阶( 即；m = 2 ，q = 1 ，s = 3 ) z o l o t a r e v 距离白( 参见定义2 6 ) 首先， 用墨。的期望和方差将( 3 1 ) 式正则化，就有 一e 【1k 一( n + 1 ) 3 、v 打【】、( 佗十1 ) 1 8 口叉仉一( 巩+ 1 ) 3 + 1 2 弋而再而vi 万 。k + 一( n 一) 3 匝 十了丙司丽虿一vi 万 若记 震一黼，、( n + l j 1 8 霹：= 鬻，、k ，_ r1 ，o 那么，上式可以改写成 矗呈鼠 料+ 霹斗等 ( 3 8 ) 为了证明的渐近正态性，我们还需要下面的两个引理 引理3 1 设z 是一个标准正态随机变量，z 1 和忍是z 的两个相互独立的独立 复制，则 z 呈磊 籍+ 玩、等， ( 3 9 ) 其中，服从 o ，1 ，佗一1 ) 上的均匀分布，而且与z ，磊，历相互独立 证明：事实上，我们只需验证( 3 9 ) 式两边具有相同的特征函数即可，由随机变量 z ，z 1 ，z 2 ，的相互独立性，我们有 e h t0 僻+ 忍罔) 中国科学技术大学博士学位论文 = e = 著阱( t 闻z t 卅x 州嚣m = 去 _ 揣小p _ 高t 2 = 去静 一) 这恰恰是标准正态随机变量的特征函数由此，本命题成立证毕 口 引理3 2 设实数序列 a n ，n n ) 满足不等式 瞬n 昙篆( 等) 2 o 羞( 并) 七= 0 、 7 则当靠_ o o 时，的极限为0 证明：由归纳法可证数列 n n ，n n ) 有界，所以 o n 的上极限有限记 0 n ：= l i m s u l ) n n o ，存在一个充分大的正整数几o ，使得；当礼 n o 时，o n 几。时，我们有 一昙蒸( 措) 2 = 罢薹( 等) 吾时昙惫蔓。( 等) 2 鲰 要薹( 等) 2 罢七蔓。( 等) 3 ”e ， 掣溉 + ( ，要薹( 等) 墨 第三章随机二叉搜索树中几类顶点的数目 显然，对任意固定的正整数n o o ， 舰( 掣。戮) ) 一o n - + 、几0 k 彻。， 所以，如果令竹一。o ，就有 口剑，嘉薹( 等 = 2 ( ) 以 = 昙( 口刊 由e 的任意性知a = o ，即： 旦n n = o 证毕 口 现在，我们来证明本节的最重要的结论 定理3 7 若为大小为n 的随机二又搜索树中的叶点数目则当n o 。时，有 定= 黼三忡) 证明： 由定理2 1 l ，我们只需要证明：当n _ 。o 时，随机变量矗= 专杀茜等和 z 之间的z o l o t a r e v 距离白趋于。即可记 白( r 栩：= 白( c ( 瓠脚1 ) ) 为得到所要结论，我们首先来证明白( 晶，) 是有限的由定理2 7 知，对任意二阶矩 有限的随机变量h 和，有 白( m ，k ) 丢厶| t 1 3 d l p ( t ) 一p ( 屹 2 时，有 e ) 2 证明：由定理3 9 可知，当n 2 时， e 陋) 2 2 n 2 7 n + 9 孵】+ ( e 【砰】) 2 警+ ( 字) 2 2 礼2 7 几+ 9 证毕口 推论3 4 若砖为大小为几的随机二叉搜索树中含有2 个子点的顶点数目，则 当n o o 时，有 则有 x 乎)p1 i 巧一百 证明；证明方法与推论3 2 雷同，故略之 口 定理3 1 0 若嘏为大小为几的随机二叉搜索树中只含有1 个子点的顶点数目， x 1 ) = o ；趟1 ) = 1 ； 掣，几2 ； 丁，几2 z ； 吾( 川) ，扎独 ( 0 ，1 ) ， 口s 礼_ 。o ， 证明由随机二叉搜索树的定义，当亿= 1 ，2 时，命题显然成立在大小为礼的随 机二叉搜索树中，最多只有三类顶点，即：含有。个，1 个和2 个子点的顶点所以，自