论文部分内容阅读
本文主要研究与几种随机树相关的一些随机变量的极限性质,例如:随机二叉搜索树中三类顶点的数目,均匀递归树中顶点间的距离,区间树的大小.
随机二叉搜索树只有三类顶点,即分别含有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>的中心极限定理.