【作者】 陈新兴；

【导师】 应坚刚；

【作者基本信息】 复旦大学 ， 概率论与数理统计， 2007， 博士

【摘要】 给定顶点集合[n]={1，2，…，n}。对于每个顶点i，独立地且随机地从[n]中取出一个顶点i，然后在这两个顶点之间连接一条以i为始点，以i为终点的有向边。这样构成的图一般称为随机映射图。论文中研究当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趋向无穷大时随机映射图的最大连通分支的顶点个数的各阶渐进矩。进而从各阶渐进矩，知道最大连通分支的顶点个数的渐进分布密度函数。类似地，得到最大树的顶点个数的各阶渐进矩以及渐进分布密度函数。更多还原

【Abstract】 Abstract: Given vertices set [n] := {1,2,…, n}. For every vertex i, we inde-pendently and randomly choose a vertex from [n], and join these two vertices with an oriental edge which has initial point i and end point j. Such graph composed of these vertices and these edges, is generally called random map-ping graph. In the paper, we investigate the limit property of the local image of a random mapping graph and its use as n goes to infinity.First we study the joined probability of m fixed vertices in a random graph. Hence we get its precise formula and its second order expansion. For example as n goes to infinity, the probability that m vertices are joined is increasing to (?)，while the the probability that m vertices are mutually disjoined is decreasing to (?).The paper next describes [k]-local image of a random mapping graph and [k]-good graph. The [k]-local image of a mapping graph is a minimal graph which keeps the topological structure of [k]. Some mapping graphs’s [k]-local images have simple topological structure: it is still a mapping graph but with 2k vertices and it has [k] as leaves and the rest k vertices as inner vertices whose indegree is two. We call these whose [k]-local images have simple structure [k]-good graphs. It is easily to find that as n goes infinity, the probability that a random mapping graph is [k]-good asymptotic to one. Furthermore, the limitation of local image of a random mapping graph is equiv-alent to a Markov chain, random birth process of graphs more precisely. The time sequence of the sizes of components(or tree) of the graphs constructed by random birth process is a (0, 1/2) -Chinese Restaurant Processor (1/2,1/2) -Chinese Restaurant Process). The limit property of its local image can reflect the whole property of a random mapping graph . This make us can estimate the number of vertices with a certain of property and the height of some ver-tices of a random mapping through its local image. By the fact that the limit property of its local image can reflect the whole property of a random mapping graph, we can easily draw out the conclusion that three kind of travels which are defined on a random mapping graph , Harris walk, Travels on the contour and Travels in depth-first order, weekly converge to the same process called Reflected Brown Bridge.At last we introduce (α,θ)-Chinese Restaurant Process. Suppose that there are n customers in a restaurant and they occupy the first k tables with n_i customers sitting around the i-th. table. Let the next customer be brought either to the i-th occupied table with probability (n_i-α)/(n +θ) or to the first empty table with probability (θ+ kα)/(n +θ). Such a random sequence is called (α,θ)-Chinese restaurant process. We get asymptotic moments of the size of the largest table as n large enough for each pair (α,θ). Applying the above result that The time sequence of the sizes of components of the graphs constructed by random birth process is a (0,1/2) -Chinese Restaurant Process and the result that the limit property of its local image can reflect the whole property of a random mapping graph, We directly get the asymptotic moments of the size of the largest component of a random mapping graph as n goes to infinity. Furthermore, we get its asymptotic distribution directly from the as-ymptotic moments. Similarly, we find the asymptotic moments of the size of the largest tree and its asymptotic distribution.4更多还原