《七次完美洗牌之外：随意切牌要洗多少次才随机》

导语

这篇 Quanta 文章从一个经典结论进入：1992 年，Dave Bayer 和 Persi Diaconis 证明七次 riffle shuffle（桥式洗牌）足以随机化一副牌。但那个结论要求切牌非常接近一半。新工作由 Mark Sellke、Jialu Shi 和 Jiamin Wang 完成，回答更接近日常洗牌的问题：如果每次切牌位置很随意，混合是否仍会突然发生？

1. 七次洗牌定理重要，是因为它展示了“逐渐然后突然”的截断现象

1.1 一副牌的复杂性让洗牌成为严肃数学问题

• 普通 52 张牌的排列数是 52!，也就是大约 8 后面跟 67 个 0，接近银河系中原子数量的估计值。每次洗牌几乎都会得到此前从未存在、以后也不会再存在的排列。洗牌问题看似日常，背后却是巨大状态空间如何走向随机的问题。
• 1981 年，Diaconis 和 Mehrdad Shahshahani 已经在洗牌中发现 cutoff phenomenon（截断现象）：系统一开始保留相当多秩序，随后在某个时刻突然接近随机。这个现象类似物理中的相变，也出现在 Markov chains（描述系统如何概率性地在状态之间移动的模型）中。