论文部分内容阅读
本文主要研究随机递归树和随机二叉搜索树上与分支和子树相关的极限定理。 根树上的分支是指以第一代顶点为根点的子树,对于随机递归树的分支结构,我们首先通过组合的方法给出了在大小为n的随机递归树上大小为m的分支的数目的精确分布,由此可直接得到它的极限分布是参数为1/m的Poisson分布;证明了各种不同大小的分支数目是渐近独立的,此外还给出了各种分支数目的联合分布及联合极限分布。 利用上面分支结构的结果,我们给出了在随机递归树上的简单向下随机游动的长度的渐近分布。 我们进一步讨论了大小为n的随机递归树上分支大小的极值,运用生成函数和指数公式,分别给出了最小与最大分支大小的极限分布,并且通过一些数值计算,还给出了最大分支大小的分布函数和密度函数的图像。 我们对随机递归树和随机二叉搜索树都考察了不同种类的子树个数问题,首先考察了随机递归树上固定大小和固定形状的子树的数目,经过适当的正则化后,我们用压缩法证明了它们是依分布收敛到正态的,利用Polya罐模型,可以表明强大数律也应该是成立的。 更一般地,对于子树的大小k=k(n)随n变化的情形,可以将k(n)分为三类不同情形:次临界情形,即k(n)/n1/2→0;临界情形,即k(n)=θ(n1/2);和超临界情形,即k(n)/n1/2→∞。通过分析生成函数所满足的函数方程,我们证明了在次临界情形下,大小为k(n)的子树的数目(正则化后)是渐近正态的;在超临界情形下,是依概率收敛到0的;而在临界情形下,若k(n)/n1/2收敛到某个有限的常数,则相关子树的数目是依分布收敛到Poisson分布的,这展示了在大小为n的随机递归树和随机二叉搜索树上,大小为k(n)的子树的数目从次临界情形到超临界情形其极限分布逐步演化的全部过程。