随机置换图与马氏链的联系

Random permutation graphs and related Markov chains

研究n个顶点的随机置换图的一些性质,利用已有的一个确定划分的概率(使得顶点都被记录在不同的连通分支当中),去构造一个放球模型,并可以证明这个放球模型是马氏链,还可以证明随机置换的某些性质是包含在这个放球模型当中,最后得到随机置换连通分支的极限联合分布.

The property of random permutation with n nodes is investigated. By using the probability that fixed classes of finite non intersected subsets of nodes are located in different components to construct a scheme of allocating particles and prove this scheme is a Markov chain. Some behaviors of random permutation may be represented in the Markov chain in certain sense are proved. Finally, the limit associated distributing about the connection component of random permutation is found.