## [¼Æ¾Ç]¬~´X¦¸µP¤~¡u°÷¡v¡H

### [¼Æ¾Ç]¬~´X¦¸µP¤~¡u°÷¡v¡H

¨s³º¡A¬~µP­n¬~´X¦h¦¸¤~¡u°÷¡v¡H

³oºØ¬~µP¤èªk¥sinverse Gilbert-Shannon-Reeds shuffle (inverse GSR shuffle)¡CBayer©MDiaconisµý©ú¤F­Y¶i¦æ¤j¬ù$\frac{3}{2}\log_2 n$¦¸inverse GSR shuffle¡A°ÆµP´N¤j¬ù¡u¬~¤Ã¡v¤F¡C´«¨¥¤§¡A¹ï°àµP¨Ó»¡¡A»Ý­n¬~µP¤j¬ù 8.55 ¦¸¡C

-----

Below is for more advanced math students. Only people who have some background on Markov Chain theory should continue reading:

Forthose who know about Markov Chain theory, you may easily see that it isa Markov process. As every element in the symmetric group has aninverse, it is easy to observe that the eigenvector with eigenvalue 1is indeed the "uniform distribution vector".

The period of thecorresponding stochastic matrix must be 1, since there is non-zeroprobability that the inverse GSR shuffle remains the deck unchanged.Hence by Perron-Frobenius theorem, all other eigenvectors must be witheigenvalue of modulus strictly less than 1. So after shufflingsufficiently many times, no matter how the intial distribution is, itmust converge to the unifrom distribution.

In other words, youmay say converging to uniform distribution is an immediate result ofPerron-Frobenius theorem. Bayer and Diaconis were analyzing

how fast the convergence is.

http://mathdb.blogspot.com/2009/09/blog-post_20.html

¬Ý¨£¤@­Ó»Ý­n¡A¨Ã¥Î¼Æ¾Ç¸Ñ¨M¥¦¡I

yll
«Ó­ô¨}~

¤å³¹: 4367
µù¥U®É¶¡: 2002-08-28
¨Ó¦Û: ¤Ñ¤÷ªº¤pªá¶é~

¼Æ¾Ç¤å³¹