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

导语

这篇 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（描述系统如何概率性地在状态之间移动的模型）中。

1.2 1992 年证明强大，但依赖严格条件

• Bayer 和 Diaconis 的“七次足够”定理之所以重要，是因为它不只证明真实系统存在精确截断，还给出适用于任意牌数的公式。Diaconis 的背景也让这个问题格外有趣：他 14 岁离家跟魔术师学习，10 年后回到学校并成为数学家，纸牌技巧一直和他的研究有关。
• 限制也很硬。第一，桥式洗牌必须按严格模型进行：每张牌从左堆或右堆落下，概率与该堆剩余牌数成比例，而不是机械交替。第二，每次都要把牌大致切成两半。Diaconis 说，原证明的所有分析都依赖这些细节；如果像普通人一样随意切牌，结论就不再直接成立。

2. 冷点解释了为什么不均匀切牌会保留秩序

2.1 Lalley 试图放松条件，但证明卡住了

• 1999 年，University of Chicago 数学家 Steven Lalley 试图证明：即便切牌不是很均匀，桥式洗牌也存在截断。这个问题很自然，因为现实中有人会切得高一点或低一点。
• 不均匀切牌会让牌堆中某些区域长期保持相对顺序。Lalley 把这些区域称为 cold spots（冷点）。例如把牌标成 1 到 52，多次洗牌后 16 和 17 未必相邻，但 16 仍可能比随机情况下更常出现在 17 前面；如果 15 到 25 这一段里许多牌对都有类似偏向，这一段就是冷点。

2.2 冷点如果消失，最后的秩序也应消失

• Lalley 的直觉是：当冷点消失，牌堆中最后残留的原始秩序也会消失，这就能证明截断存在。但他没能完成证明。文章用这一失败为新证明铺路：难点不只是“洗几次”，而是如何追踪哪些牌还保留共同路径。

3. 条码方法让随意切牌也能被追踪

3.1 Sellke 从课堂问题发展到更现实模型

• 2019 年，Mark Sellke 还是 Stanford 研究生时，在 Diaconis 课上听到“如果不对半切，原证明就完全失效”的随口说明，于是把它当成可攻克问题。到 2021 年，他已经找到了更不均匀切牌的截断，包括切成多于两堆的情况；但那时每次洗牌仍必须按同一种方式切。
• 2024 年夏天，他与 Jialu Shi、Jiamin Wang 合作，转向更现实的问题：每次切牌都可能不同。这个模型更贴近普通玩家，而不是魔术师式稳定切牌。

3.2 每张牌获得一串 0 和 1 的路径标签

• 三人给每张牌分配 barcode（条码）。第一次切牌时，左堆牌标 1，右堆牌标 0；洗完再切，如果某张牌进入左堆，就在标签后加 1，进入右堆就加 0。多次洗牌后，每张牌都会得到越来越长的 0/1 串，记录它在左右堆之间跳转的路径。
• 如果原本相邻或相对顺序固定的两张牌，比如 16 和 17，最后拥有相同条码，就说明它们走过完全相同路径，仍保留原始相对顺序。要证明截断，就要说明在某个洗牌次数后，匹配条码已经很少。

3.3 图结构把检查范围压缩到冷点

• 直接比较所有条码很耗时，冷点提供了捷径。研究者只需要检查那些最抗拒混合的区域。方法是：从 n 张牌开始，把所有冷点里的条码按升序列出，再把每张牌表示成图上的点；如果两张牌条码相同，就连一条边，表示这对牌尚未真正混合。
• 他们对第二副 n 张牌重复同样过程，再把两张图对齐，看未混合区域在哪里重叠。Sellke、Shi 和 Wang 证明，在某个依赖牌数的洗牌次数后，这种重叠会以指数速度消失。这个 exponential tail（指数尾部）给出了典型牌堆中最后秩序消散所需次数的上界。

4. 新结果把 52 张牌的粗切洗牌上界推到约 14 次，但问题还没结束

4.1 随机切牌时，14 次左右足够混合

• 新证明给出的结论是：对 52 张牌，如果每次都在随机位置切牌，约 14 次桥式洗牌后牌堆会充分混合。Sellke 的个人动机很朴素：他偶尔和朋友打牌，想知道自己到底该洗几次。
• Lalley 对结果评价很高，因为这个问题放了 26 年，终于被破解。Diaconis 也认为新想法非常有效，是出色的数学。

4.2 “成团落牌”的普通人洗法仍是下一步

• 文章最后保留了一个技术限制：新证明和 Bayer-Diaconis 的旧证明一样，仍假设牌是一张一张交错落下，而不是成团落下。许多普通玩家并没有这种细腻洗牌技能。
• Sellke 说自己很想继续研究 clumpy shuffle（成团洗牌）问题，但暂时没有进展。因此，新证明不是把所有现实洗牌都解决了，而是把“切牌不均匀”这个长期障碍移开，并为更粗糙的洗牌模型留下下一步。

思想框架

文章先用 52! 和七次洗牌定理说明，洗牌是研究随机化和截断现象的经典入口；然后指出旧定理依赖对半切牌和严格交错，现实切牌会留下冷点。Lalley 提出冷点思路却未能证明，新一代数学家用条码记录每张牌左右堆路径，再把冷点里的相同条码转成图的重叠问题，最终证明重叠会指数衰减。结论是，52 张牌在随机切牌下约 14 次桥式洗牌可充分混合；但如果牌是成团落下，问题仍开放。