学位论文 > 优秀研究生学位论文题录展示

关于两类随机树的极限定理

作　者: 冯群强
导　师: 苏淳
学　校: 中国科学技术大学
专　业: 概率论与数理统计
关键词: 随机树分支子树简单向下随机游动指数公式压缩法 P(?)lya罐生成函数
分类号: O211.4
类　型: 博士论文
年　份: 2006年
下　载: 120次
引　用: 0次
阅　读: 论文下载

内容摘要

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

全文目录

摘要  5-6
Abstract  6-9
第一章简介  9-17
  1.1 图论中的基本概念  9-10
  1.2 随机递归树  10-12
  1.3 随机二叉搜索树  12-14
  1.4 本文主要研究成果  14-17
第二章分支结构  17-31
  2.1 分支总数目  17-20
  2.2 顶点n的深度  20-22
  2.3 给定大小分支的数目  22-24
  2.4 渐近独立性  24-31
第三章简单向下随机游动  31-41
  3.1 长度为2的情形  31-35
  3.2 一般情形  35-41
第四章最小与最大分支  41-57
  4.1 指数族与最小分支的大小  42-44
  4.2 最大分支的大小  44-54
    4.2.1 生成函数  44-45
    4.2.2 鞍点逼近  45-48
    4.2.3 收敛性  48-54
  4.3 数值计算  54-57
第五章不同种类的子树  57-75
  5.1 递归分布等式与矩  57-61
  5.2 压缩法与中心极限定理  61-64
  5.3 Pólya罐与强大数律  64-71
    5.3.1 广义Pólya罐模型简介  64-66
    5.3.2 在子树问题上的应用  66-71
  5.4 式样问题  71-75
第六章不同大小子树的一般情形  75-103
  6.1 递归树情形  76-91
    6.1.1 任意阶矩  77-79
    6.1.2 临界情形  79-81
    6.1.3 超临界情形  81
    6.1.4 次临界情形  81-91
  6.2 二叉搜索树情形  91-103
    6.2.1 临界和超临界情形  92-97
    6.2.2 次临界情形  97-103
攻读博士学位期间论文发表(或待发表)情况  103-105
参考文献  105-109

相似论文

控制权度量模型及计算,O211.3
几类序列的多重卷积公式,O157.1
一个与记录时间相关的生成函数研究,O211.3
托普利兹矩阵的一种分解带状逆预处理矩阵,O151.21
托普利兹方程组的基于嵌入法的预处理矩阵,O241.5
Bailey变换与一些新的q-级数恒等式,O173
基于校园网E2E时延测量研究,TP393.06
变系数广义Hamilton系统的生成函数方法,O241.81
广义Bernoulli-Euler多项式及其研究,O174.14
无线通信中协同分集的性能分析与编码技术研究,TN919.3
P分拆的计算,O156.7
基于N-S方程的烟雾模拟实时性改进,TP391.41
鞍点逼近方法及在CDO定价中的应用,O212.7
我国企业价值评估方法及实证研究,F224
求解BTTB最小二乘问题的BTTB预处理矩阵,O151.21
基于战斗力生成的军费研究,E0-054
聚合反应机理模型的建立及在聚丙烯生产流程模拟中的应用,TQ325.14
第三类超Cartan域的完备Einstein-K（？）hler度量及其全纯截曲率,O153.4
端到端网络时延的性能测量,TN915.06
改进的FHN系统的斑图形成及其螺旋波控制,O415