随机树中一些变量的极限定理

来源 :中国科学技术大学 | 被引量 : 0次 | 上传用户:fxl207111
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文主要研究与几种随机树相关的一些随机变量的极限性质,例如:随机二叉搜索树中三类顶点的数目,均匀递归树中顶点间的距离,区间树的大小. 随机二叉搜索树只有三类顶点,即分别含有0,1和2个子点的顶点,我们分别用X<,n>,X<(1)><,n>和X<(2)><,n>)记大小为n的随机二叉搜索树T<,n>中这三类顶点的数目.我们首先建立了关于X<,n>的递归方程,并由此入手,得到了其期望和方差,在此基础上,选取适当的概率距离,运用压缩法证明了X<,n>的大数律和渐近正态性.接着,又用归纳法证明了X<,n>和X<(2)><,n>之间具有简单的线性关系,并由此直接得到了X<(1)><,n>和X<(2)><,n>的极限性质. 对于大小为n的均匀递归树,我们研究了均匀递归树中任意顶点i<,n>和顶点n之间的距离D<,i<,n>>,n>在此前的各种文献中,关于D<,i<,n>,n>的讨论,都需要对i<,n>加上各种限制条件.我们完全解除了这些限制条件,利用经典的正态逼近方法,证明了:当树的大小n→∞时,对任何的0,n>都具有渐近正态性.并顺便得到了D<,i<,n>,n>的大数律.这一结果昭示了经典极限理论在随机结构理论中的作用. 区间(0,x)按照指定规则进行随机分割之后,可以将其对应为二叉树,称之为区间树.我们考虑区间树的大小(即顶点数目),首先,我们建立了区间树的概率空间结构.然后,在S<,x>的母函数不易求得的情况下,我们先建立了关于S<,x>递归方程,并从S<,x>递归方程出发,将求S<,x>的期望和方差的问题转化为求解特定类型微分方程的问题,最终求得了它们的准确解.在此基础上,我们不仅给出了S<,x>的强弱大数律,并在选取适当的概率距离之后,运用连续参数情形时的压缩法,证明了S<,x>的中心极限定理.
其他文献
本学位论文将着力于研究解决群论中的几个公开问题,内容主要包括两个方面:一是研究与群类理论相关的群的子群结构和群类的代数结构方面的几个问题;二是利用子群置换性质刻画有限
图像插值在更少图像信息的情况下构造出忠实于小尺寸原图大尺寸图像,而如果能够让插值重构出来的图像边缘和轮廓清晰,这就可以直接应用于减小网络传输图像的负担,同时保持图