A strong uniform time for random transpositions
Tóm tắt
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.
Tài liệu tham khảo
Diaconis, P., and Shashahani, M. (1981). Generating a random permutation with random transpositions,Z. Wahrsch. verw. Geb. 57, 157–179.
Aldous, D. (1983). Random walks on finite groups and rapidly mixing Markov chains, inSeminaire de Probabilities XVII, pp. 243–297 (Springer Lecture Notes 986), Springer, New York.
Aldous, D., and Diaconis, P. (1986). Shuffling cards and stopping times,Am. Math. Mon. 93, 333–348.
Diaconis, P. (1988).Group Theory in Statistics, IMS, Hayward, California, to appear.
Broder, A. (1985). Unpublished manuscript.
Riordan, J. (1978).An Introduction to Combinatorial Analysis, Princeton University Press, Princeton, New Jersey.
Kolchin, V. F., Sevast'yanov, B. A., and Chistyakov, V. P. (1978).Random Allocations, V. H. Winston and Sons, Washington, D.C.