结果族 238：Optimal logarithmic mixing of the Thorp shuffle · 学科：Probability and statistical mechanics · 验证状态：暂无形式化证明，请以社区核验为准
最强版本的”防偷看”测试：把半副牌的全部行程公开——每一步谁走到哪里都告诉观众——然后问，剩下那半副牌的排列还是随机的吗？这篇论文回答：是的（在平均意义下）。观众看光了一半的戏，另一半的剧本依然完全随机；由此整副牌在常数乘 @@M@@d@@ 次物理洗牌内混合，阶数最优。
关键词卡片
看个具体例子
取 @@M@@n=2^{10}=1024@@，公开 @@M@@512@@ 张牌的完整轨迹。数字版定理：经 @@M@@400+40000\times401=16040400@@ 扫（每扫 @@M@@d=10@@ 次物理洗牌，共 @@M@@160404000@@ 次），剩余 @@M@@512@@ 张牌的条件排列与均匀排列的期望总变差 @@M@@\E\|\nu_{\mathcal E}-U_{n/2}\|_{\mathrm{TV}}\to0@@。常数大得吓人，但阶数恰为 @@M@@\Theta(d)@@，与信息论下界 @@M@@2d-O(1)@@ 同阶。
为什么值得关心
条件混合比”单牌均匀”“无条件全牌均匀”都强：它说明随机性在被部分观察时依然完整，连接着小域加密分析；同时要读准结论——均匀性只对路径取平均成立，并非对每条固定的揭示路径都成立。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读把本篇比作最强版本的”防偷看”测试：把半副牌每一步走到哪里全部公开给观众，问剩下半副牌之间的排列换算还是不是随机的。答案是在平均意义下依然是——观众看光了一半的戏，另一半的剧本仍完全随机。这比”单张牌洗匀”“整副牌（无人偷看时）洗匀”都强：周边运动被看光之后，剩余的牌必须一起被随机化。
第二级台阶
精确化：被公开轨迹的那半副牌携带的信息称为揭示环境；把每个时刻的空闲位置按二进制递增编号，未暴露的随机开关便在自由位置集合间诱导一个双射，经编号映射成为固定对称群 @@M@@S_{n/2}@@ 上的一个置换，其条件律记 @@M@@\nu_{\mathcal E}@@。误差取条件总变差再对揭示路径取平均，即期望总变差；@@M@@d@@ 个坐标方向各更新一次称为一扫，耗 @@M@@d@@ 次物理洗牌。
第三级台阶
定理在牌数 @@M@@2^d@@、任意确定性初始牌序、公开恰好一半标签这三条设定下陈述。结论是：经 @@M@@J(s_0+1)@@ 个扫（@@M@@s_0=400@@，@@M@@J=40000@@）后，@@M@@\sup\E_{\mathcal E}\|\nu_{\mathcal E}-U_{n/2}\|_{\TV}\to0@@；等价地说，条件置换与揭示环境几乎独立。证明节奏是”准备—激活”交替：多扫预热压缩误差，一扫激活读取表示论收缩。推论给出整副牌在 @@M@@16040400\,d@@ 次物理洗牌内混合；配合每次洗牌只耗 @@M@@n/2@@ 个随机比特的支撑下界 @@M@@2d-O(1)@@，混合阶 @@M@@\Theta(d)@@ 最优。注意均匀性只对路径取平均：罕见环境可由删去小质量处理，论文不逐条断言。
证明了更强的条件混合：在 @@M@@2^d@@ 张牌的 Thorp 洗牌中固定并公开一半牌的全部轨迹后，剩余半副牌的条件置换律仍在期望总变差意义下趋于均匀，从而整副牌在 @@M@@16040400\,d@@ 次物理洗牌内混合，阶数 @@M@@\Theta(\log n)@@ 最优。
Thorp 洗牌把 @@M@@2^d@@ 张牌对半分、成对独立公平交换后交叉；在旋转坐标下等价于沿 @@M@@\mathbb F_2^d@@ 的坐标方向依次做公平交换，一个方向为一层，@@M@@d@@ 层各方向一次为一”扫”（sweep），耗 @@M@@d@@ 次物理洗牌。洗牌的随机开关不只移动单牌，它定义了全部起始与结束位置间的一个双射：若部分牌的完整路径被公开，其余牌仍经历一个随机双射，但其律依赖被揭示的路径。何时这整个条件双射近乎均匀？这一问比单牌混合与无条件全牌混合都强——所有剩余标签必须在”周边运动被看光”之后一起被随机化。此前 Morris 的熵方法研究无条件全牌混合（@@M@@O(d^3)@@），Czumaj–Vöcking 对固定比例的部分牌给出 @@M@@O((\log n)^2)@@（需向网络填充空牌、改变链本身），而对”揭示环境下的条件置换”此前没有显式界。该问题还连接小域加密分析（Morris–Rogaway–Stegers）与 swap-or-not 混洗中的条件能量方法（Hoang–Morris–Rogaway）。
定理：@@M@@n=2^d@@，从任意确定性牌序出发，固定 @@M@@m=n/2@@ 个”外部”标签并揭示其全部轨迹 @@M@@\mathcal E@@。把每个时刻的自由（未被占）位置按二进制递增编号，未暴露的开关诱导自由位置集合间的双射 @@M@@T_e@@，经编号映射得到 @@M@@S_m@@ 上的置换 @@M@@g_e=\iota_T^{-1}T_e\iota_0@@，其条件律记为 @@M@@\nu_{\mathcal E}@@。则在 @@M@@J(s_0+1)@@ 个扫后（@@M@@s_0=400@@，@@M@@J=40000@@），
@@M@@D\sup_{\text{初始牌序}}\ \E_{\mathcal E}\|\nu_{\mathcal E}-U_{n/2}\|_{\TV}\longrightarrow0\qquad(d\to\infty).@@
等价地，联合律 @@M@@\mathcal L(\mathcal E,g)@@ 与 @@M@@\mathcal L(\mathcal E)\otimes U_{n/2}@@ 的总变差趋于零：条件置换几乎独立于揭示的环境。推论：全牌在 @@M@@400+40000\times401=16040400@@ 个扫、即 @@M@@16040400\,d@@ 次物理洗牌内与均匀律混合；结合信息论下界 @@M@@1-2^{tn/2}/n!@@（每次洗牌仅用 @@M@@n/2@@ 个随机比特），混合时间为 @@M@@\Theta(d)@@ 阶。
出发点是条件置换核的构造（slot-kernel 引理）：揭示外部路径恰等于在独立的开关币数组中固定一个柱集，未被规定的币仍是独立公平比特；它们诱导自由集合间的双射，用递增编号把双射化为固定群 @@M@@S_m@@ 上的置换。两个关键性质：该条件律不依赖进入区间的自由标签分配，且相邻区间的核按卷积复合、彼此条件独立——即使全部未来路径已被揭示。
第一步（准备）：任意有序半副牌在 @@M@@400@@ 个扫内混合。对单张自由牌在阻挡路径条件下的误差向量 @@M@@u_s@@，用两副本实验算出一扫的精确碰撞核 @@M@@A_E(x,y)=2^{-j}\prod_{k>j}q_k(x)@@：两张独立副本在首次失配坐标 @@M@@j@@ 前每步以 @@M@@1/2@@ 概率相遇，会合后同行概率由伙伴被挡比例决定。按高位比特把空间切成大子方块（coarse blocks）：好阻挡集上一扫收缩子方块内部涨落（@@M@@\E\|uQ\|^2\le\|u_{\rm c}\|^2+q^{d-h}\|u\|^2@@，@@M@@q=7/8@@），同时让输出的粗平均能量变小（借负相依性——乘积边际界在公平交换下保持——控制”坏输出”概率）；两扫合并得 @@M@@a_{s+1}\le n^{-1/20}a_{s-1}@@，跳两步迭代 @@M@@400@@ 扫得 @@M@@a_{s_0}\le n^{-10}@@，再按序暴露插值得半副牌距离 @@M@@\le n^{-3}@@。
第二步（准备+激活交替）：把时间切成”@@M@@400@@ 扫准备 + @@M@@1@@ 扫激活”的块。准备区间按 @@M@@\min(1,u_*/p(y))@@ 加权截断为次概率测度，其对路径的平均被”均匀自由集 + 独立均匀槽置换”联合支配；激活扫中若两个独立副本在 @@M@@a@@ 个终点上一致，则由单扫路径唯一性，至少 @@M@@d(a-L)/8@@ 个自由开关币必须全部吻合，联合界给固定点概率 @@M@@\le n^{-a/32}@@；经 Larsen–Shalev 特征界（固定松驰的均匀版本）化为归一化迹 @@M@@b_\rho\le 2D^{-1/800}@@。再对均匀置换做 Schur 共轭平均，把迹界升级为半正定序的矩阵不等式 @@M@@\E[(F_aF_b)^*(F_aF_b)]\preceq b_\rho I@@，对 @@M@@J=40000@@ 块迭代得 @@M@@\E[F_{\mathrm{tot}}^*F_{\mathrm{tot}}]\preceq b_\rho^J I@@；Plancherel 恒等式加倒二次度和（@@M@@J/1600=25@@）给出期望总变差 @@M@@o(1)@@，被删去的质量以次概率恢复。
第三步（耦合收尾）：先用准备命题把两副牌的外部半副牌耦合，再对剩余标签用条件结论做极大耦合，总失败概率 @@M@@\le\delta_n+o(1)<1/4@@，得全牌混合界。后文的 reset、overlay、两半构造等给出改变机制各环节的另外三种构造，各有独立的量化陈述。
本篇主结果暂无形式化证明，请以社区核验为准。族内关系：伙伴篇《Optimal-order mixing of the Thorp shuffle》独立给出 @@M@@1600d@@ 的全牌混合；同族《Conditional information under deterministic coordinate sweeps》研究确定坐标扫下的条件信息，其定理并非本篇输入，二者互补；已 Lean 形式化的《Routing densities and representation contraction for Thorp sweeps》给出绝对常数个扫的收缩。注意条件结论只对路径取平均，不对每个固定环境断言。按 OpenAI 官方声明，未经形式化的结果可能有问题。
问 1：证明中最关键也最脆弱的一步是什么？
（答：激活扫的表示论收缩。若两个独立副本在 @@M@@a@@ 个终点上一致，单扫路径唯一性迫使至少 @@M@@d(a-L)/8@@ 个自由开关币全部吻合，联合界给固定点概率 @@M@@\le n^{-a/32}@@；再经 Larsen–Shalev 特征界（固定松弛版本）化为归一化迹 @@M@@b_\rho\le 2D^{-1/800}@@，Schur 共轭平均把迹界升级为矩阵不等式后对 @@M@@J=40000@@ 块迭代。指数 @@M@@1/800@@ 极小，全靠 @@M@@J@@ 与倒二次度和垒出收敛——任何一环松动，衰减便不够付 Plancherel 求和。）
问 2：条件结论为什么只对揭示路径取平均，不逐条断言？
（答：论文自己说得很直白：罕见的路径环境可能留下”太少有用的开关”，处理办法是在真实外部路径律下删去小质量恢复归一化，”并不假设典型自由集在进一步条件化后仍典型”。环境与置换几乎独立的等价式 @@M@@\|\mathcal L(\mathcal E,g)-\mathcal L(\mathcal E)\otimes U\|_{\TV}=\E\|\nu_{\mathcal E}-U\|_{\TV}@@ 与 Markov 不等式给出的只是概率陈述，非逐环境保证。）
问 3：为什么固定公开恰好半副牌？其他比例行吗？
（答：主定理取 @@M@@m=n/2@@：自由槽数量恰为半副，条件置换落在固定的 @@M@@S_{n/2}@@ 上，编号与卷积复合规则都按此设计。其他比例论文未以主定理形式给出；后文的 reset、overlay、双色三构造改变机制环节并各有独立量化陈述，不改变”半副”设定。）
问 4：与已有工作相比真正的新意是什么？
（答：问的是全新的量。单牌均匀一扫即得；无条件全牌混合姊妹篇已给 @@M@@1600d@@；Czumaj–Vöcking 的部分牌结果是 @@M@@O(d^2)@@ 且改链；”揭示环境下整个剩余分配的条件律”此前没有显式界。本文首次给出 slot-kernel 构造（揭示路径=币数组柱集、相邻区间核条件独立卷积）与准备—激活交替机器，常数虽差，阶数最优。）
问 5：这类 AI 生成证明最可能在哪里出错？
（答：三处高危。slot-kernel 引理的”条件律不依赖进入区间的自由标签分配、相邻区间在全部未来路径已揭示时仍条件独立”，双射构造差半步就坍塌；准备区间截断后被”均匀自由集+独立均匀槽置换”联合支配的次概率论证，截断与支配的次序极易颠倒；负相依性（乘积边际界在公平交换下保持）控制坏输出的适用范围。）
问 6：常数 @@M@@16040400@@ 为什么这么大，能压吗？
（答：@@M@@400@@ 扫准备来自两扫收缩率 @@M@@n^{-1/20}@@ 的跳步迭代，@@M@@J=40000@@ 块来自迹指数 @@M@@1/800@@ 太弱，根源是激活扫里”多终点一致迫使多币吻合”的换算损耗。文中三构造各带独立时间界，说明作者知道机器未调优；压常数非本文目标。）
问 7：下游谁会用到？
（答：直接连接小域加密——揭示环境正是”攻击者看穿部分状态”的模型，条件置换均匀意味着剩余部分仍可当一次一密用；全牌常倍 @@M@@d@@ 混合是副产品；族内与 @@M@@1600d@@、@@M@@2048d@@ 及已形式化的 Routing densities 篇互相校验。）
总评
这是族中概念上最强的一环——把”部分观察下随机性是否存活”变成可证明的定理，机器全新、诚实标注平均意义；最大风险是准备—激活长链条中任何一环的指数损耗被低估，@@M@@1/800@@ 与 @@M@@40000@@ 的悬殊比例本身就是机器精度的自白。