摘要
给定顶点集合[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: 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
引文
[1] Aldous, D.J. The continuum random tree Ⅰ, Ann. Probab. (1991)19 1-28.
[2] Aldous, D.J. The continuum random tree Ⅲ, Ann. Probab. (1993)21 248-289.
[3] Aldous, D.J. and Pitman, J., Brownian Bridge Asymptotics for Random map-pings, Random Structures Algorithms, (1994)5: 487-512.
[4] Aldous, D.J. and Pitman, J., Invariance principles for non-uniform random mappings and trees. Asymptotic Combinatorics with Applications to Mathematical Physics, (2002)113-147.
[5] Aldous, D.J. and Miermont, G. and Pitman, J., Brownian Bridge Asymptotics for Random p-mappings Electronic Journal of Probability, (2004)9: 37-56.
[6] Aldous, D.J. and Pitman, J., The asymptotic distribution of the diameter of a random mapping, C.R. Acad. Sci. Paris, Ser. Ⅰ 334(2002) 1021-1024
[7] Alm, S.E., Monotonicity of the difference between median and mean of Gamma distributions and of a related Ramanujan, Bernoulli 9 (2003), no. 2, 351-371;
[8] Bagaev, G.N., The distribution of the number of vertices in a component of an in decomposable random mapping, Dokl. Akad. Nauk BSSR (1977)21, 1061-1063
[9] Barabasi, A.L. and Albert, R., Emergence of scaling in random networks. 1999, Science 286, 509.
[10] Bollobas, B., RANDOM GRAPHS, Cambridge University Press, 9(2001).
[11] Chen, X. and Ying, J., Asymptotic local image of random mapping graphs, to appear on Ann Inst Henri-Poicare: Probab & Stat.
[12] Diestel, R., Graph theory, New York, Springer Berlin Heidelberg, 2005.
[13] Drmota, M., Correlations on the strata of a random mapping. Random Struct. Algebra (1995) 6. 357-365.
[14] Drmota, M., Gittenberger, B., Strata of random mappings-A combinatorial approach Stochastic Processes and their Applications (1999)82, 157-171
[15] Drmota, M., Gittenberger, B., On the profile of random trees. Random Structures and Algorithms, (1997) 10: 42-451,
[16] Duquesne, T., A limit theorem for the contour process of conditioned Galton-Watson trees, Ann. Probab, (2003)31, No.2, 996-1027.
[17] Erdos, P. and Renyi, A. On random graphs, I, Publ. Math. Debrecen (1959)6, 290-297
[18] Erdos, P. and Renyi, A. On the evolution of random graphs, Publ. Math. Inst Hungar. Acad. Sci.(1960)5, 17-61
[19] Erdos, P. and Renyi, A. On the evolution of random graphs, Bull. Inst. Int. Statist. Tokyo (1961) 38, 343-347.
[20] Feller, W., AN INTRODUCTION TO PROBABILITY THEORY AND ITS APPLICA-TIONS, Vol Ⅰ, John Wiley & Sons, 3rd edition, 1968;
[21] Folkert, J.E., The distribution of the number of components of a random mapping function, Ph.D.Dissertation, Michigan State University. 1955.
[22] Gertsbakh, I.B., Epidemic processes on a random graph: some preliminary results, J. Appl. Probab. (1977)14, 427-438.
[23] Goncharov, V.L., From the realm of combinatorics, Izv. Acad. Nauk SSSR, SerMatem. 8 (1944), 3-48.
[24] Gutjahr, W. and Pflug, G.Ch., The asymptotic contour process of a binary tree is Brownian excursion, Stochastic Proc. Appl. (1992)41 69-90.
[25] Harris, B., Probability Distributions Related to Random Mappings, Ann. Math. Statist. 31, 4(1960): 1045-62.
[26] Katz, L. The probability of indecomposability of a random mapping function Annals Math. Statist. (1955).
[27] Kolchin, V.F., RANDOM MAPPINGS, Optimization Software, New York, 1986 (Translation of Russian original).
[28] Kolchin, V.F., A problem of the allocation of particles in cells and random mappings, Theory Probability Appl.(1976)21, 48-63.
[29] Kruskal, M.D., The expected number of components under a random mapping function, The American Mathematical Monthly, Vol.61, No. 6(1954)pp.392-397
[30] Mutafchiev, L., The limit distribution of the number of nodes in low strata of a random mapping. Statist. Probab. Lett. (1989)7.247-251
[31] Perman, M., Order statistics for jumps of normalised subordinators, Stochastic Processes and their Applications (1993)46, 267-281.
[32] Pitman, J., COMBITORIAL STOCHASTIC PROCESSES, Lect. Notes in Maths (to appear), Springer, Berlin. Available now via http://bibserver.berkeley.edu/csp/csp.html
[33] Pittel, B., On distributions related to transitive closures of the random finite mappings, Ann. Probab. (1983) 11, 428-441
[34] Proskurin, G.V., On the distribution of the number of vertices in the strata of a random mapping, Theory Probab. Applies (1973)18, 803-808.
[35] Quine MP., A calculus-based proof of a Stifling formula for the gamma function, International Journal of Mathematics Education, Science and Technology, (1997)28, 914-917
[36] Ramanujan, S., Question 294, J. Indian Math. Soc. 3(1911), 128;
[37] Riordan, J., Enumeration of linear graphs for mappings of finite sets, Annls Math. Statist.(1962) 33, 178-185
[38] Ross, S.M., A RANDOM GRAPH, J. Appl. Probab.(1981)18, 309-315.
[39] Ross, S.M., INTRODUCTION TO PROBABILITY MODELS, Academic Press, 7th edition, 2000;
[40] Rubin, M., Sitgreaves, R., Probability distributions related to random transfor-mations of a finite set. Tech, Rep. 19A, Applied Mathematics and Statistics Laboratory, Stanford University 1954.
[41] Sachkov, V.N., Random mappings with bounded height, Theory Probab. Applics (1973)1, 120-130
[42] Shepp, L.A. and Lloyd, S.P., Ordered cycle lengths in random permutations, Trans. Amer. Math. Soc. (1966) 121, 340-357
[43] Stepanov, V.E. Combinatorial algebra and random graphs, Theory Probab. Applics(1969a) 14, 373-399.
[44] Stepanov, V.E., Limit distributions of certain characteristics of random mappings, Theory Probability Appl. (1969b)14, 612-626.
[45] Stepanov, V.E., Random mappings with a single attracting centre. Theory Probability Appl. (1971)16, 155-161.
[46] Temperley, H.N.V., Graph theory and applications, Ellis Horwood, Chichester, (1981)130pp.
[47] Watts, D.J., and Strogatz, S.H. Collective dynamics of 'small-world' networks, Nature, 393: 440-442, 1998
[48] 马志明，《随机图选讲(Ⅰ)》，第九届全国数学研究生暑期学校教材，2004，7。
[49] 应坚刚，金蒙伟，《随机过程基础》，复旦大学出版社，上海，2005．