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