本文主要研究与几种随机树相关的一些随机变量的极限性质，例如：随机二叉搜索（?）三类顶点的数目，均匀递归树中顶点间的距离，区间树的大小．随机二叉搜索树只有三类顶点，即分别含有0，1和2个子点的顶点，我们分别用Xn，Xn（1）和Xn（2）记大小为n的随机二叉搜索树Tn中这三类顶点的数目．我们首先建立了关于Xn的递归方程，并由此入手，得到了其期望和方差，在此基础上，选取适当的概率距离，运用压缩法证明了Xn的大数律和渐近正态性．接着，又用归纳法证明了Xn和Xn（2）之间具有简单的线性关系，并由此直接得到了Xn（1）和Xn（2）的极限性质．对于大小为n的均匀递归树，我们研究了均匀递归树中任意顶点in和顶点n之间的距离D（in），n．在此前的各种文献中，关于D（in），n的讨论，都需要对in加上各种限制条件．我们完全解除了这些限制条件，利用经典的正态逼近方法，证明了：当树的大小n→∞时，对任何的0<in<n，经标准化后的D（in），n都具有渐近正态性．并顺便得到了D（in），n的大数律．这一结果昭示了经典极限理论在随机结构理论中的作用．区间（0，x）按照指定规则进行随机分割之后，可以将其对应为二叉树，称之为区间树．我们考虑区间树的大小（即顶点数目），首先，我们建立了区间树的概率空间结构．然后，在Sx的母函数不易求得的情况下，我们先建立了关于Sx递归方程，并从Sx递归方程出发，将求Sx的期望和方差的问题转化为求解特定类型微分方程的问题，最终求得了它们的准确解．在此基础上，我们不仅给出了Sx的强弱大数律，并在选取适当的概率距离之后，运用连续参数情形时的压缩法，证明了Sx的中心极限定理．
本文来源: https://www.lw50.cn/article/17f5876fc8fb48c1db0a0436.html