论文部分内容阅读
给定顶点集合[n]:={1,2,…,n).对于每个顶点i,独立地且随机地从[n]中取出一个顶点j,然后在这两个顶点之间连接一条以i为始点,以j为终点的有向边。这样构成的图一般称为随机映射图.论文中研究当n趋向无穷大时随机映射图的局部极限性质及其应用。
首先,我们讨论固定的m个顶点在随机映射图中的连接概率.因此得到连接概率的精确解和其二阶展开.比如,m个顶点互相连接的概率关于n单调下降趋于(2m-2!!)/(2m-1)!!,或者,互不连接的概率关于n单调增加趋1/(2m-1)!!。
文中接着描述随机映射图的[k]-局部图和[k]-好图. [k]-局部图是一幅保留着顶点集合[k]在原来的映射图中的拓扑结构的最小的图.有些映射图的[k]-局部图具有简单拓扑结构:它仍然是映射图且含有2k个顶点,其中[k]的顶点是它的叶子,其余的k个顶点是入度为二的内点.我们把这些具有简单结构的[k]-局部图的映射图称为[k]-好图。容易发现当n趋向无穷大时,随机映射图是[k]一好图的概率趋向于一.进一步研究得到,随机映射图的局部图极限在莫种意义下等价于一个马尔科夫链,准确地说是等价于图的随机生长过程;图的随机生长过程中产生的图的连通分支的顶点个数的时间序列是一个(0,1/2)-中国餐厅过程,和产生的图的树的顶点个数的时间序列是(1/2,1/2)-中国餐厅过程;局部图极限性质能够反映随机映射图的整体性质——局部图可以用来估计随机映射图的具有莫类性质的顶点的个数和莫些顶点的高度。应用局部图极限性质能够反映随机映射图的整体性质,我们容易得到三种定义在随机映射图的遍历过程, Harris游动,深度优先的遍历和在叶子上的遍历,在经过标准化后弱收敛于同一个反射布朗桥。
最后,我们介绍(αθ)-中国餐厅过程。假设餐厅来了n个客人,他们坐在前面的k个餐桌,且第i个餐桌有,n<,i>个客人.当下一个客人到达餐厅时,他将以(n<,i>-α)/(n+θ)的概率坐在第i个餐桌,以(θ+kα)/(n+θ)的概率坐在第一张非空的餐桌,即第k+1个餐桌上.这样的一个随机过程称为参数为(α,θ)的中国餐厅过程.我们得到在不同参数下当餐厅总人数足够多时,中国餐厅过程的餐桌的最大客人人数的各阶渐进矩.应用前面结论,图的随机生长过程中所产生的图的连通分支的顶点个数的时间序列就是一个(0,1/2)一中国餐厅过程和局部图极限性质能够反映随机映射图的整体性质,直接得到当n趋向无穷大时随机映射图的最大连通分支的顶点个数的各阶渐进矩.进而从各阶渐进矩,知道最大连通分支的顶点个数的渐进分布密度函数类似地,得到最大树的顶点个数的各阶渐进矩以及渐进分布密度函数.