（概率论与数理统计专业论文）关于两种随机图模型的研究.pdf

摘要 本文涉及与两种随机图模型有关的若干问题一种是关于分裂算法产生的随机树 上的随机路径问题，另一种是关于均匀递归树与纪录值的关系问题 对于第个问题，本文用单边分裂的方法得到随机路径，并利用泊松变换与反泊松 变换得到这一路径期望的确切表达最后用指数逼近的方法以及梅林变换的办法得到 这一结果的极限值接着很自然的把这种方法推广到m 叉对称分裂算法上，得到相应 的结果 在另一部分中，我们为了研究均匀递归树的分支结构，引进了记录值的概念通过 对记录值性质的介绍便得到了均匀递归树分支结构与记录值问题的内在联系，从而得 到均匀递归树分支数的若干性质除此之外，还给出了递归树与记录值之间的一个一一 映射。这种映射很好的保持了分支与记录时间隔的对应关系最后根据上面的关系得到 了记录时间间隔的一系列性质 关键词，二叉分裂算法；泊松变换；指数逼近；随机路径；递归树，记录值 a b s t r a c t t w ok i n d so fr a n d o mg r a p hm o d e l l ；a r ei n t r o d u c e di nt h i st h e s i s o n ei st h e b e r n o u l l is p l i t t i n ga l g o r i t h ma n dt h eo t h e ro n ei st h er a n d o mr e c u r s i v et r e e o nt h eo n eh a n d ，f o rt h eb e r n o u l l is p l i t t i n ga l g o r i t h m ，t h er a n d o mp a t hl e n g t h o ft h i sr a n d o mt r e e si sc o n s i d e r e d t h er a n d o mp a t hl e n g t hi so b t a i n e db yt h ep a r t i a l s p l i t t i n gm e t h o d w i t ht h em e t h o do fp o i s s o n i z a t i o na n dd e p o i s s o n i z a t i o n ，t h ee x a c t e x p r e s s i o no ft h ee x p e c t i o no ft h ep a t hl e n g t hi so b t a i n e d i nt h ee n d ，t h el i m i t i n gr e s u l t i ss h o w e db yt h ee x p o n e n t i a la s y m p t o t i ca n dm e l l i nt r a n s f o r m a t i o nm e t h o d f u r t h e r m o r e t h i sm e t h o dbu s e do nt h em r a ys p l i t t i n ga l g o r i t h ma n ds o m er e s u l t sa r eo b t a i n e d i nt h i ss i t u a t i o n o nt h eo t h e rh a n d ，t h er e c o r di si n t r o d u c e dt og a i ns o m er e s u l t sa b o u tt h eb r a n c h - i n gs t r u c t u r ep r o p e r t i e so nt h er a n d o mt r e e w i t hs o m ep r o p e r t i e so ft h er e c o e d ，t h c r e l a t i o n s h i pb e t w e e nt h er e c o r da n dt h eb r a n c h i n gs t r u c t u r ei ss h o w e d w i t ht h i s * l a t i o n s h i p ，s o m ep r o p e r t i e so ft h eb r a n c h i n gs t r u c t u r ea r eo b t a i n e d l a t e r ，am a p p i n g b e t w e e nt h er a d o mt r e ea n dt h er e c o r di si n t r o d u c e d i nt h ee n d ，s o m ep r o p e r t i e so f t h ew a i t i n gt i m eb e t w e e nt w or e c o e da r eo b t a i n e d k e y w o r d s ：b e r n o u l l is p l i t t i n ga l g o r i t h m ；p o i s s o n i z a t i o n ；e x p o n e n t i a l a s y m p t o t i c ；r a n d o mp a t h ；r a n d o mt r e e s ；r e c o r d i i i 中国科学技术大学学位学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究 工作所取得的成果。除已特别加以标注和致谢的地方外，论文中 不包含任何他人已经发表或撰写过的研究成果。与我一同工作的 同志对本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权， 即：学校有权按有关规定向国家有关部门或机构送交论文的复 印件和电子版，允许论文被查阅或借阅，可以将学位论文编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：! ! 茎查 2 0 7 年；月8 日 致谢 在完成这篇论文的过程中，我得到了许多老师和同学的大力支持和帮助在此，我 想对他们致以深深的谢意! 首先，要感谢我的导师苏淳教授，三年来，苏老师从专业知识，研究方法，治学态 度等多个方面，给予我悉心的指导，使我从一个本科生，慢慢成长为一个合格的研究 生生他对学生的循循善诱，让我受益匪浅；他对每一项工作的认真细心。令我深受感 动这些都是我人生中最有益的影响之一，也是我今后学习工作中最好的榜样在此， 我想向苏老师表示我最衷心的感谢! 其次，我想向赵林城教授，方兆本教授。缪柏其教授，韦来生教授。吴耀华教授， 胡太忠教授和杨亚宁教授表达我由衷的感激之情他们悉心的传授各门专业课知识，将 我一步步引进概率论与数理统计这个学科的殿堂，让我在吸收这方面知识的同时，也教 给了我运用它们的工具和方法此外，在我的研究生阶段，还得到了系里许多老师，包 括郑坚坚老师，臧红老师和夏红卫老师的不少帮助，在此一并向他们表示我最诚挚的谢 意 同时，我还要感谢我的学长陈昱博士，胡治水博士，冯群强博士。严继高博士，刘 杰博士，陈静硕士他们在我的学习和研究中给予了很多帮助和指点我还要感谢我的 同学宁兵博士，蒋俊博士，以及其他同学和老师在他们的鼓励和支持下。我才克服了 种种困难，并最终完成了我的硕士学业 最后，我将特别的感激之情献给我的家人他们无私的爱，永远是我前进的最大动 力l 谨以此文献给所有关心和帮助过我的人l 第一章绪论 1 。1 图论中的基本概念 图是指有序三元组g = ( k e ，讪) ，其中y 非空为顶点集，e 为边集，1 f ，是e 到 y 中元素有序对或无序对簇v v 的函数y 中元素称为顶点，e 中元素称为边 v v 中的元素若全是有序对。那么g 称为有向图；若全是无序对。那么g 称为无 向图若无向图中边e e 的两个端点为z 和y ( 或有向图中边e 以z 为起点，y 为终 点) ，我们也可将e 记作z v 一般地，图g 也可以简写为g = ( i , e ) 若两顶点之间有边连接或两边有公共的端点，我们称它们为相邻的两端点相同 的边称为环如果两个顶点之间有多条边，则称这些边为平行边无环并且没有平行 边的图称为简单圈我们下面讨论的图均指简单图 如果两个图的顶点集之间存在一个保持相邻关系的一一映射。则称两个图是同构 的即对图g = ( v e ) 和图g ，= ( v f ) ，若存在一个一一映射妒：v y 7 使得边 x y e 当且仅当边妒( 茹) 咖( y ) f ，则图g 和g 是同构的 设g = ( k e ) 为无向图，臼v 为g 上的个顶点与顶点 相邻的顶点数称为 l ，的度数，记为d g ( ) 对图g 上的顶点如和仇，若存在另外k 一1 个互不相同的顶点 l ，也，讥一1 使得仇和仉+ 1 相邻， = 0 ，1 ，k 一1 ，那么就称顶点如，讥以及 边如”l t ，饥一1 讥组成了个长度为k 的路两个端点相同的路称为闭路或圈设 z ，y v ，若g 中存在连接z 和可的路，则称z 和y 是连通的若图g 中任意两个 顶点都是连通的，则称g 为连通图 不含圈的图称为森林不含圈的连通图称为树易知树上任意两顶点t ，1 ，之间有 且仅有一条路相连接。并且我们把连接”，的路所包含的边数称为u ，口两顶点之间的 距离树丁上所有顶点的数目就称为r 的大小不难知道，大小为n 的树恰有n 一1 条边 设图丁为树，若指定某点r 为根点。则称丁为以r 为根点的根树顶点 和根点 1 中国科技大学硕士论文 r 之间的距离称为口的深度或高度若根树? 上的两顶点z 和y 相邻。且z 离根点 较近，那么我们称y 是z 的子点或者$ 是y 的父点没有子点的顶点称为叶我们 也可以类似定义顶点的后代和祖宗此外，树r 中所有深度为k 的顶点组成的集合称 为第k 代顶占、特别地，根点是第0 代顶点 一般地，根树可被看作无向图，也可被看作有向图看作有向图时。每条边的方向 规定为远离根点的方向，因此，根树也可被称为外向树更多关于图论的基本知识，可 参阅b o l l o b f i , s ( 1 9 9 8 ) 或徐俊明( 1 9 9 8 ) 1 2 二叉分裂算法的介绍 分裂算法是将大小为n 的集合递归地分成若干子集，直到所有的子集中的元素个 数都严格小于某个常数d 为止的一种算法这种算法有着非常广泛的应用在数据 结构中，这类算法被用来对数据进行排序和搜索它们有时被称为。d i v i d ea n dc o i l - q u e r ”算法c o r m e n & r i v e s t ( 1 9 9 0 ) 与k n u t h ( 1 9 9 8 ) 中对这类算法有完整的描述，m a - h a m o u d ( 1 9 9 2 ) 和s e d g e w i c k & f l a j o l e t ( 1 9 9 5 ) 中用分析方法对这类算法予以了讨论在 通信网络中，这类算法被用来描述单位时间只能传输一个信号的网络通信渠道，参看 c a p e t a a a k i s ( 1 9 7 9 ) 与e p h r e m i d e s & h a j e k ( 1 9 9 8 ) 此外，在统计检验中，如果已知某个 群体中至少有一个有某种特性( 如某种疾病) ，也可以应用这类算法用尽可能少的检验次 数在尽可能短的时间内识别出该个体，参看w o l f ( 1 9 8 5 ) 本文中我们仅考虑二叉分裂的 情形，并运用随机图论的理论和方法对其进行研究 对于由礼个元索所构成的集合所进行的二叉分裂( 记作k ( n ) ) 可以描述如下， 如果n = 0 或n = 1 ，就不进行分割；如果凡2 ，则将原来的集合分为两个子集， 其中每个元素都被等概率地分入两个子集，不妨设两个子集大小为n l 和礼一n l ；然后 再对每个子集继续进行刚才的过程k ( n - ) ，k m m ) ，直到所有集合中的元素个数都小 于2 为止 显然，这种算法可以对应为一个二又树；将原来的集合对应为树的根点，如果n 2 ， 则把它的两个子集对应为根点的两个子点，并如此一直下去显然，树的叶点所对应的 2 第一章绪论 集合( 称为叶点集) 中或者只有一个元索或者是空集在搜索算法中最后得到空集，表 明没有搜索到给定的元素，即搜索不成功反之则是成功搜索每个内点所对应的集合 ( 称为内点集) 中的的元索个数都不小于2 我们关心的是叶点到根点的距离，计为k 这一问题在很多文献中都被研究过。但都是先用组合的方法，再结合分析的手段在第 二章中我们希望通过概率的方法得到厶l 的期望，并对它的极限性状加以描述 1 3 随机递归树 随机递归树，又称均匀递归树，是一种基于很多随机现象和计算机算法的结构模 型大小为礼的随机递归树是顶点集为 l ，2 ，n ，且根点为1 的根树，它的构造 过程可以看成一个顶点插入过程：对新插入的顶点n ，在已有的n 一1 个顶点中随机取 一个作为它的父点，这里随机的意义即指在大小为n 一1 的树上任一顶点成为n 的父 点是等可能的由它的构造可知任一条由根点到叶的路上的顶点标号均是递增的 随机递归树最早是由n a r a p o p o r t ( 1 9 7 0 ) 引入用来作为研究某些系统的增长的 一种概率模型后来它陆续被用来分析有机物污染的扩散( m e i r m o o n ，1 9 7 4 ) ，金字 塔式配置( g a s t w i r t h ，1 9 7 7 ) ，语言学中的谱系结构( n a j o c k & h e y d e ，1 9 8 2 ) ，因特网的 界面地图( j a n i c 等。2 0 0 2 ) ，计算机网络的随机增长( c h a r t 等。2 0 0 3 ) 它还跟一些因特 网模型( 参阅v a nm i e g h e m 等，2 0 0 1 ；v a nd e rh o f s t a d 等，2 0 0 1 ；d e v r o y e 等，2 0 0 2 ) 和物理模型( 参阅t e t z l a f f , 2 0 0 2 ) 有关联此外它还出现在有关h o p f 代数的文献中( 参 阅g r o s s m a n l a r s o n ，1 9 8 9 ) 下面给出一个为随机递归树的传染病模型 假设某个群体中一共有n 个人先后感染了某种传染病( 例如严重急性呼吸综合症) ， 其中只有一个人去过疫区。从两他是这个群体的感染源头第二个人一定是被他传染 的；由于不清楚传染机制，所以我们假定第三个人分别以概率；1 被前两个人所传染；一 般地，我们假定第k 个人以概率由被前k 一1 个人所传染，k = 2 ，3 ，n 如果我 们以顶点k 表示第k 个人。对于k 2 ，将顶点k 与传染给他疾病的人所对应的顶点之 间连一条边，那么我们就得到了一个递归树由此看来，研究随机递归树有利于从一定 程度上弄清严重急性呼吸综合症之类的传染病的传染规律 3 中国科技大学硕士论文 大小为礼的递归树一共有一1 ) ! 种，这是因为对每个顶点t 的父点有i 一1 种选 择，i = 2 ，n 所有大小为n 的递归树出现的概率都是一样的，即为i ；i 例如大 小为4 的递归树有六种，出现的概率各为六分之一( 如图1 1 ) ，关于随机递归树更多的 概率性质，可参阅综述性文献s m y t h e & m a h m o u d ( 1 9 9 4 ) 433 4 图1 1 所有大小为4 的递归树 4 。 很多作者都考察过随机递归树例如顶点间距离问题，s z y m a f i s k i ( 1 9 9 0 ) 给出了 顶点n 的深度的分布，d e v r o y e ( 1 9 8 8 ) 和m a h m o u d ( 1 9 9 1 ) 分别证明了n 的深度的中 心极限定理； m o o n ( 1 9 7 4 ) 考察了任意给定两点间的距离，d o b r o w ( 1 9 9 6 ) ，d o b r o w s m y t h e ( 1 9 9 6 ) 进一步得出了它的分布和建立了中心极限定理。苏淳，刘杰和冯群强 ( 2 0 0 6 ) 取消了前人关于顶点标号的各种限制条件，得到关于任意两个顶点之间距离的中 心极限定理成立的广泛条件；m a h m o u d ( 1 9 9 1 ) ，d o b r o w f i l l ( 1 9 9 9 ) 研究了路径总长 ( 即所有顶点到根点的距离之和) ，前者证得了正则化后收敛到某个非退化的随机变量。 而后者得出了此极限是“q u i e k s o r t ”型的，从而不满足中心极限定理；n e n i n g e r ( 2 0 0 2 ) 还考察了w i e n e r 指数( 即所有顶点间的距离之和) 和路径总长的联合极限分布，他还 提到了随机选定的两个顶点之间的距离关于各代顶点的数目，m e i r m o o n ( 1 9 7 8 b ) 给出了精确分布( 第一代顶点的个数即根点的度数) ，p u c h s 等( 2 0 0 6 ) 进一步考察了其 极限性质；d e v r o y e & l u ( 1 9 9 5 ) ，o o h & s c h m u t z ( 2 0 0 2 ) 均考察了最大的顶点度数， 分别得到了强大数律和极限分布；关于给定度数的顶点数日。n a j o c k & h e y d e ( 1 9 8 2 ) ， m e i r m o o n ( 1 9 8 8 ) 分别考察了叶( 即度数为l 的顶点) 和出度( 即子点个数) 为1 的 4 第一章绪论 顶点的个数；利用p o l y a 罐模型， m a h m o u d s m y t h e ( 1 9 9 2 ) 讨论了出度为0 ，1 ，2 的顶点的数目，得出了它们的联合极限分布是多元正态；j a n s o n ( 2 0 0 5 ) 把他们的结论 推广到了所有不同出度的顶点数目关于子树冈题，m a h m o u d s m y t h e 1 9 9 1 ) 考察 了以任意顶点k 为根点的子树大小和其上叶点的数目的极限分布冯群强，苏淳和胡 治水( 2 0 0 5 ) 讨论了均匀递归树的分支结构，不仅得到了第一代子点数目的大数律，中 心极限定理，重对数律，而且很容易将他们的结果转化为关于顶点n 的深度的相应结 果j 他们还讨论了各种不同大小分支数目的分布，联合分布以及它们的极限性状他们 还讨论了与均匀递归树上的等概向下随机游动有关的一些问题 另外，不少作者对随机递归树作了变形或推广，参阅s z y m a f i s k i ( 1 9 8 7 ) ，m a h m o u d ： s m y t h e s z y r n a f i s k i ( 1 9 9 3 ) ，d o b r o w & s m y t h e ( 1 9 9 6 ) ，m a h m o u d ( 2 0 0 4 ) ，p a a h o l z e r p r o d i n g e r ( 2 0 0 4 ) 等 5 第二章二叉分裂过程的分裂次数 2 1 随机路径 我们的目标足求叶点到根点的平均距离，为达到这一目的。我们来引进一种所谓的 单边分裂算法顾名思义，这种算法是始终只分裂一边。不妨设分裂左边( 实际上没有 左右之分) ，直到左子集的元素个数小于2 为止显然。从最后得到的左叶点到根点形 成个随机路径可以看出，这条路径可能是实际完全分裂过程中的任意一条这条路 径长度的期望就是我们所要求的平均路径长度设单边分裂过程得到的二叉树顶点个 数为风，显然有凰= r l = 1 下面引理给出了个简单的递推关系 引理2 1 对任意n 2 ，随机变量风满足 忍呈2 + 硅一靠 ( 2 1 1 ) 其中& = b l + + 艮，b i ，i l 是参数为i e 的独立b e r n m t l l i 随机变量对 0 n ，随机变量磁与r k 同分布 上面引理中的b e r n o u l l i 随机变量可以理解为t 对i 1 ，若晟= 0 ，则第 个元素 被分在左子集中 利用边界条件r o = r i = 1 ，可以对一切非负整数n ，将如的递归关系统一表示为 心呈2 + 磁一晶一2 7 。s l ， ( 2 1 2 ) 容易看出，在单边分裂算法之下，有关系式 r = 2 厶。+ 1 成立所以，为考察l 。的极限性状，只需考查r 。的极限性状 定理2 1 对霉 0 ，序列e ( 心) 的泊松变换为， 如) = 薹她) 鲁e - # = l + 2 篆p ( t 2 s 争 ( 2 怕) 其中t 2 是两个参数为j 的指数分布的独立随机变量的和 中国科授大学硕士论文 i 正q l ：设= f o ，四，t o 是强度为l 的泊松过程e ( 忍) 的泊松变换可以 表示为 r ( z ) = e ( r n ( i o 。1 ) ) 由递推式( 3 2 2 ) ，我们可以得到等式 r n ( i o 。芦2 + r b ( i - - 2 i i n ( 1 0 姻 此因泊松随机变量l v ( o 。霉】) 分裂成两个随机变量，s n c i o ，司) 和_ j vc o ，聋1 ) 一s n ( t o 卅) ；而 根据泊松过程的性质，这两个随机变量都是参数为= 2 的泊松随机变量由定义，t 2 是泊松过程中的第二个质点的到达时刻，于是( ( 【0 ，善1 ) l = f 2 z ) ，而且 e ( r n ( 0 。1 ) ) = e ( r n ( i o ，。2 i ) ) + 2 2 p ( t 2 茁) = e ( r n ( o = 2 1 ) ) + 2 p ( t 2 口) 上式可以递归地写为， r ( z ) = r ( 嘉) + 2 p ( t z 磊) 。 k = 0 。 注意到对任何o 冗，都有 恕r ( 蠡) = r ( o ) - - - e ( r o ) = l ， 在上式两边取极限得定理结论口 下面定理是本文的主要结果 定理2 2 对n22 ，我们有 e c r u ) = 1 + 2 ( 1 0 - 西1r 一螽( 1 一刍) ”1 ) ( 2 1 4 ) ) 0 、 一一 第二章二叉分裂过程的分裂次数 证明：仍以= ( ( 【0 ，x 1 ) ，z2o 表示强度为1 的泊松点过程，由( 3 2 3 ) 对区 间【0 ，叫内的质点的个数取条件，我们有 r ( 。) = 1 + 2 p ( t ：磊) 知 0 = 1 + 2 p ( t 2 熹，( 【0 ，z 】) = n ) ( 2 1 5 ) k on 2 。 以。表示第n 个质点的到达时刻，由泊松过程的性质，若给定事件 ( 【o ，。】) = ，1 ) ，则 随机向量( t l ，t 2 ，t 。) 与扛地1 ) ，x u ( 2 ) ，玑_ 。) ) 同分布，其中( 矾 ) 1si n ) 表示 区间【0 , 1 】上的均匀分布随机变量的次序统计量特别地，若给定事件 ( 【o ，z 】) = n ) ， 则随机变量t 2 与z 阢2 】同分布，因此我们得到t p ( t 。蠡，j v ( i o ，z 】) = n ) = p ( z 。毒，j ，( 【0 ，叫) = ，；) = p ( 如，。s 刍( i o ，司) = 0 = p ( 去) p ( ( 【o ，z j ) = n ) ， 将此式代入( 3 2 ，5 ) 式，得到 啦) = ，+ 。善萎p ( 。s 万1 ) p ( ( 1 0 堋= ，0 知 0n 2 、 一， = l + 2 p ( 仉。去) 等e 一 i - 0n9ko 2 在上式中交换求和顺序，得 、巾，= 暮等e 一。+ 。薹( 篆p c 一刍，) 蔷e q 一e 。+ 薹( t + z k o 慨剐争n 2 。 坤。 最后个等式显然是一个泊松变换，通过比较两边的系数我们得到下面的等式，对n 2 h = l + 2 p ( 如。去) ( 2 1 6 ) 又因p ( 巩。z ) = 1 一( 1 一o r n x ( 1 一z p ，代入上式即得( 3 2 4 ) 式 口 中国科技大学硕士论文 推论2 1 由关系2 厶= 忍一1 知 驯2 磊( ，邓一扣一象c t 一扩) 仁 ， 2 2 渐近分析 对k 渐近性质的研究有很重要的意义。它在计算机算法中表示查找一个给定键值 所需要的平均分裂次数这一理论在很多文章中都做出了研究我们首先对e ( l 。) 作 指数逼近，然后利用第二节中复分析的结果得到我们想要的结果 下面证明( 3 27 ) 式可以在求和号内用指数逼近由( 3 2 7 ) 式得 驯= 羡( 川一扩c 一刍+ 昙，) = 薹( 叫一妒c - + 等，) 汜。m 若令n 一1 = m ，。k ，。= f r n ，上式变成， e ( l 。) = ( 1 - ( 1 一警) “( 1 怕。) ) ：= k = 0 再令为 = ( 1 一e q 一( 1 + 。t 。) ) 由单调性知c ，k 7 1 m ，我们要研究两者之差t 一= k = 0 ( ( 1 一等) ”一e 嘞”) ( 1 + m ) ( 2 2 2 ) 对0 厶9 。l 、口 ， 。 j 量2 0 m z 一 = 萋，( e 一卢罟0 ( 1 ) ) k o 2 m l 一 由f 2 】知。i o e 一“7 2 署是关于m 的有界函数，所以= d ( 1 ) 面对手匕右 k 2 。：。2 a , o 2 e 0 ，序列g ( 冗。) 的泊松变换为， 巾) = 妻n = o e ( 如，等e 1 = + z 篆尸( t 。嘉) c s 2 。， 其中t 2 是两个参数为j 的指数分布的独立随机变量的和 证明：设= f i o ，日，t o ) 是强度为1 的泊松过程e ( 晚) 的泊松变换可以 表示为， 7 ( z ) ：e ( r ( 【0 硝) ) 由递推式( 3 2 2 ) ，我们可以得到等式 r n ( o 。1 ) 呈2 + r k ( i 。卅) 一s ( o 。1 ) 一2 ，( i 。叫) 1 1 6 第三章m 叉对称分裂过程 此因泊松随机变量7 v ( 【o ，。1 ) 分裂成两个随机变量，s ( i o ，。1 ) 和( 【0 ，。】) 一s ( 1 0 。科) ；而 根据泊松过程的性质，这两个随机变量分别是参数为虹三半和景的泊松随机变量由 定义，暑2 是泊松过程中的第二个质点的到达时刻，于是f n ( | o ，z 】) l = 1 2 卫 ，而 且 上式可以递归地写为t e ( r n ( l o 司) ) = e ( r j v ( i o ，景1 ) ) + 2 2 p ( t 2 霉) = e ( r q ( o 云1 ) ) + 2 p ( t 2 善) 心) = r ( 杀) + 。善, z - i p ( t ：嘉) 注意到对任何z 冗，都有 恕r ( 嘉) r ( o ) = e ( n o ) _ 1 在上式两边取极限得定理结论 下面定理是本交的主要结果， 口 ( 3 2 4 证明：仍以r = t v ( 【0 ，j ) 茁o 表示强度为1 的泊松点过程，由( 3 2 3 ) 对区 问【0 ，z 】内的质点的个数取条件，我们有一 j ，( o ，叫) = n ) ( 3 2 5 ) 以t 。表示第疗个质点的到达时刻，由泊松过程的性质，若给定事件 j v ( 【o ，z 1 ) = n ，则 随机向量( t l ，t 2 ，“) 与巩，x u 2 ，七，。) 同分布，其中( 玑n ，1 t n ) 表 1 7 、 r ，上舻 一 、= r旦彬 一 r ， 一i 舻 一 o 一 有、二 枷嘎一 毛 + i “ 对 嘲 力 e 3 理 定 ，三舻 三舻 匹 0 n 2 l o ：。圹* + ( 1 + 。p ( s 熹) ) 等e 最后一个等式显然是一个泊松变换，通过比较两边的系数我 f 1 得到下面的等式i 对体2 2 = i + 2 p 他。s 嘉) ( 3 | 2 6 ) 又因p ( u 2 。妨：l 一( 1 一。y 一船( 1 一p ，代入上式即得0 2 ，4 ) 式 口 捕娩3 1 由美系2 k = 如一1 知 e ( k ) ：( 一( 一熹) “一亲( t 一嘉) ”1 ) ( s 2 ，) 七 0 、 注3 1 可以看出，上述结果与二叉分裂情形非常相似事实上，借助分析方法， 也可以证明 e ( l 。) 一| o g m + 0 ( 1 ) 1 8 第四章记录值问题与均匀递归树 4 1 记录值及其基本性质 在一个独立同分布且有给定密度函数的随机变量序列x ，磁，五中，如果墨 是前t 个元素中最大的时。则称托是个记录值，设k 为这一事件的示性函数记录值 有很多很有用的性质，在g f i c k ( 1 9 7 8 ) 中有着详细的介绍首先，注意到( y i ，k ) 的分布与墨的共同分布是无关的不失一般性，我们一般认为x l ，尥五。是由 1 ，2 ，1 2 上的均匀置换产生的记录值的基本性质可以总结如下， 1 如果r 1 r 2 ，是x 1 ，k 的部分秩( 若r = j 当且仅当恐是x i ，恐 中第j 大的元素) ，则r ，r 2 ，r | 。是独立的这表明k ，砼，k 是独立的且 对每个 r 服从l ，2 ，礼上的均匀分布 2 p ( k = 1 ) = 1 i ，其中i 1 3 x l ，x 2 ，k 中最后一个记录值服从1 ，2 ，他上的均匀分布 4 若 k 表示x l , 尥，j o 上的记录值个数，h 。表示调和和苎i i ，日乎表示 t = 1 妻1 伊，则有e ( 心) ：玩，且v a r ( 航) ：玩一砰 ；l 5 且i o g n 三1 6 苎云努依分布收敛到正态随机变量 注4 1 我们简单看看性质4 ，5 ，6 的证明性质4 可以由性质2 直接得到应用 调和和的估计，我们有f ( 魁。一l o g n 一7 = 0 ，5 7 7 2 1 5 6 6 4 9 9 h 为欧拉常敷) ，且 v a r ( n ) 一l o g n 一7 一譬大数律5 可以由性质4 及切比雪夫不等式得到中心极限 定理则可通过验证l i n d e b e r g - f e l l e r 中心极限定理中的条件得到设乃是随机变量巧 1 9 中国科技大学硕士论文 n 的分布函数， s ：= 矿o r ( k ) ，根据l i n d e b e r g - f e l l e r 中心极限定理，若 t = l 喜堆 m 即x 2 d r j ( 加娴， 娑兰i 删。 s n 在我们的问题中，5 ：= 耋( 1 一) = 巩一麟) 由于弓的概率质量都集中在【一l ，1 】 上，且s 。一0 0 ，知l i n d e b e r g f e l l e r 中心极限定理的条件成立。所以有t 老却( o ，) 、j h h h 攀 4 2 随机树的分支结构 在根树中。以某顶点为根点的子树是指由该点和它所有后代组成的结构，而分支 是指以第1 代顶点为根点的子树容易知道，递归树的子树也是递归树，只要我们把它 上的顶点按照原来的大小顺序重新按l ，2 ，标号即可 不难想象，随机树的分支结构问题是随机树性质研究的一个重要方面。f l a j o l e t & s e d g e w i c k ( 2 0 0 6 + ) 利用生成函数和分析方法考察了随机标号根树和平面树的分支总数 和给定大小的分支数目。本章中将主要考察随机递归树上的相关问题，并绘出分支结 构与记录值问题的关系从本节开始我们的随机树都是由标号为0 ，1 ，2 _ ，扎的顶点生 成，其中0 是根点根点的子点按照标号从小到大排列依次称为第一分支，第二分支， ，可以看出至少有一个以l 为根点的第一分支，而最多有n 个分支我们以眦表示 第i 分支的大小有以下引理成立。 引理4 1 第一分支的大小肌服从i ，2 n 上的均匀分布 2 0 第四章记录值问题与均匀递归树 证明：首先，t l + 1 个顶点生成的随机树的个数是n ! 而第分支大小为七的随机 树个数为c ：二i ( k 1 ) ! m 一) ! 所以有t p ( m 叫= 型兰竽型= ； 结论成立 引理4 2 p ( = f l 眦= 膏) = 杀百，其中1 k 孚时，x 。，。是b e r n o u l l i 随机变量，即 p ( x n m = 1 ) = 1 一p ( 矗，。= 0 ) = 二 推论4 2 在大小为礼一1 的随机置换上，对任何正整数m ，随机变量x 。的极 限分布是参数为1 m 的p o i s s o n 分布。即 l i r a p ( x , , ，m = ) = 鬲e 一击，= o ，1 ， 推论4 3 在太小为n - 1 的随机置换上，各种不同大小记录时问隔的数目 ( 1 i 竹一1 ) 的联合分布是 以h 1 - 轧矗二一2 ， 一产札1 ) 2 里志， 其中缸，j ：。l 是满足条件n - i t = n 一1 的任何一组非负整数 推论4 4 对任意1sk n 一- ，l 时时：1 7 , 1 j l 一面， 罩十户 一叼 第四章记录值问题与均匀递归树 图4 3 第三步 推论4 5 在随机置换上，不同大小记录时间隔的敷目渐近独立即对任意正整数 m 和有序非负整敷组 霉l ，$ 。 ，均有 ；叫锄， 一m ，- 知刊= 驴南 中国科技大学硕士论文 图4 4 第四步 第五章结束语 弘1 本文的创新之处 本文的创新之处主要有两点第一用单边分裂的方法得到二叉分裂算法的随机路 径，并且可以自然的应用泊松变换的方法第二，建立起随机置换与随机树的关系。构 造出保持这一关系的一一映射，使二者的很多性质等价起来 5 2 附录 首先介绍泊松变换 定义5 1 设r n 是一实数列，定义 称r ( $ ) 是的泊松变换 巾) 2 p 和z 氓 ( 5 2 1 ) 在引入m e u i n 变换之前。先介绍带的概念将复平面上的开带 s = 矿+ i t ：a 盯 o ( 5 2 3 ) 我们称g 。( z ) 是一个双值和( “d y a d i cs u m s j ) 在实际应用中，z 经常是一个很大 的数特别的，如果伽= 0 ，则称g o ( z ) 为标准双值和 关于标准双值和，我们有以下重要结果 引理5 1 设g ( z ) 为一函数，满足g ( o o ) 0 ，且 g ( 。) 一d k x 一，$ 一0 0 ( 5 2 4 ) 又设 g 三磊咖膨h b 】= z 1 掣如+ ”掣如 则当o _ o 。时，有 g 叫酬l 0 9 2 x + 掣+ 邕州b s 。卅壹k = l 亲与， ( 5 z 5 ) 其中，7 【9 】称为g 的欧拉常敷， 尸( “) 是一个确定的周期函数 引理的证明可参看f l u j o l e t & g o u r d o n & d u m a s ( 1 9 9 5 ) 攻读硕士学位期间论文发表情况 1 叶长青，苏淳，刘杰( 2 0 0 7 ) ，二叉分裂算法的随机路径长度中国科技大学学报，已 接受 参考文献 f 1 】c o r m e nl e i s e r s o n ，t h ，l e i s e r s o n ，c e a n dr i v e s t ，r l ( 1 9 9 0 ) a 加一如mm i t p r e s s 【2 1k n u t h ，d e ( 1 9 9 8 ) t h ea r to fc o m p u t e rp r o g r a m m i n g a d d i s o n - w e s l e y , r e a d i n g ，m a 1 3 】m a h a m o u d ，h ( 1 9 9 2 ) e v o l u t i o no fr a n d o ms e a r c ht r e e s w i l e y , n e wy o r k 4 1m a h m o u d ，h ，s m y t h e ，r a n ds z y m a 血k i ，j ( 1 9 9 3 ) o nt h es t r u c t u r eo fp l a n e - o r l e n t e d r e c u r s i v et r e e sa n dt h e i rb r a n c h e s r a n d o ms t r u c t u r e sa n da l g o r i t h m s4 ，1 5 1 - 1 7 8 【5 】s e d g c w i c k ，r a n df l a j o l e t ，p ( 1 9 9 5 ) i n t r o d u c t i o nt ot h ea n a l y s i so fa l g o r i t h m s a d d i s o n w e s l e y , r e a d i n g ，m a 【6 lr o b e r t ，p ( 2 0 0 5 ) o nt h ea s y m p t o t i cb e h a v i o ro fs o m ea l g o r i t h m s r a n d o ms t r u c t u r e s h l g o r i t h m j 2 7 2 3 5 - - 2 5 0 【7 lc a p e t a n a k i s ，j t 。( 1 9 7 9 ) t r e ea l g o r i t h m sf o rp a c k e tb r o a d c a s tc h a n n e l s i e e en w h i n f o r m t h e o r y 2 5 ，5 0 5 - 5 1 5 【8 】w o l f , l k ( 1 9 8 5 ) b o r na g a i ng r o u pt e s t i n g ：m u l t i a c c e s sc o m m u n i c a t i o n s i e e et a n s i n f o r m t h e o r y 3 1 ，1 8 5 - 1 9 1 【9 3e p h r e m i d e s ，a a n dh a j e k , b ( 1 9 9 8 ) i n f o r m a t i o nt h e o r ya n dc o m m u n i c a t i o nn e t w o r k s ： a nu n c o n s u m m a t e du n i o n i e e et r a n i n l o r m ，t h e o r y “。l 一2 0 f 1 0 】l o r d e n ，g ( 1 9 7 0 ) o ne x c e o v e rt h eb o u n d e r y a n n m a t h s t a t i s t 4 1 。5 2 0 - 5 2 7 i 1 1 】f e n g ，q ，h u ，z ，s u ，c ( 2 0 0 5 ) t h es t r u c t u r eo ft h er a n d o mr e c u r s i v et r e e s s c i e n c ei n c h i n as e t am a t h e m a t i