1
" 完美 " 的洗牌次数 - 7 次
source link: https://zhiqiang.org/math/the-perfect-number-of-shuffling-7-times.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
" 完美 " 的洗牌次数 - 7 次
系列：生活中的数学
在大家玩牌的时候，每一局之前都需要重新洗牌——一次洗牌指将牌分为左右两垛然后穿插放牌，但多少次洗牌才是正当的呢？就我多次打牌的观察，多数人都不超过 4 次。
但就 D. Aldous 和 P. Diaconis在 1992 的一个结果，要想达到「比较完美」的洗牌效果——洗完牌后牌局基本上随机分布，至少需要 5 次，要达到「完美」洗牌，则需要 7 次。但更多次数不会有太多改进。这还是对于一副牌而言的。对于两副牌则需要 9 次， 6 副牌需要洗 12 次。
所用方法是计算图上随机游走达到稳定分布的速度。而这个方法就应用于上面这个结果之后，对于理论计算机的概率算法产生了深远的影响，这也使得 P.Diaconis 的这篇论文超出了它本身看似玩物的领域。
再谈一下P. Diaconis，此君 14 岁离家，去做职业魔术师，没上高中，后来用白天魔术表演挣来的钱晚上念大学课程，最后获得哈佛的博士和斯坦福的教职。另传说中，此人赌技惊人，是赌场不受欢迎之人物。
Q. E. D.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK