A strong uniform time for random transpositions
A strong uniform time for random transpositions
复制标题
随机换位的强统一时间
DOI：
--
复制
发表时间：
1988
期刊：
影响因子：
--
通讯作者：
P. Matthews
中科院分区：
文献类型：
--
作者：
P. Matthews
考虑由K个随机置换序列生成的N个随机置换。利用强均匀次方法给出了生成的随机置换的分布与均匀分布置换的分布之间的变化距离的上界。利用强一致时间，得到了生成置换不动点个数的渐近分布。这用于给出相同变化距离的下限。这些界限一起给出了一个惊人的示范阈值现象的收敛迅速混合马尔可夫链平稳。
A random permutation ofN items generated by a sequence ofK random transpositions is considered. The method of strong uniform times is used to give an upper bound on the variation distance between the distributions of the random permutation generated and a uniformly distributed permutation. The strong uniform time is also used to find the asymptotic distribution of the number of fixed points of the generated permutation. This is used to give a lower bound on the same variation distance. Together these bounds give a striking demonstration of the threshold phenomenon in the convergence of rapidly mixing Markov chains to stationarity.