结果族 238：Optimal logarithmic mixing of the Thorp shuffle · 学科：Probability and statistical mechanics · 验证状态：暂无形式化证明，请以社区核验为准
赌场里你买通了发牌员，全程盯死一大批牌每一步的去向，想把剩下的牌也看穿——这篇论文告诉你：盯了也是白盯。它证明即使观察到任意一大批牌的完整轨迹，其余牌的条件落点依然近乎均匀；整副牌经 @@M@@2048d@@ 次物理洗牌后彻底混匀，阶数 @@M@@\Theta(\log n)@@ 最优。
关键词卡片
@@M@@d@@ 个坐标方向各更新一次，恰好消耗 @@M@@d@@ 次物理洗牌。看个具体例子
取 @@M@@n=2^{10}=1024@@ 张牌：@@M@@256d=2560@@ 次后，任选不超过 @@M@@7n/8=896@@ 张牌的联合位置与均匀单射的距离为 @@M@@o(1)@@；@@M@@1024d@@ 次后误差缩到 @@M@@n^{-3/2}@@；@@M@@2048d=20480@@ 次后整副牌均匀。条件版更强：固定一批”路障牌”的完整路径后，再洗固定个数（依赖比例）的扫，剩余牌的条件分布在期望意义下与均匀单射相差不超过 @@M@@kn^{-4}@@。
为什么值得关心
“暴露部分牌之后还剩多少信息”正是全牌混合的核心难点；本文首次对指定的大列表给出均匀的条件界——误差只对被观察路径取平均，不逐条断言，这是它独有且诚实的强度。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读里”买通发牌员盯死一大批牌”的赌场比喻，翻译过来是：把一部分牌的完整行走轨迹全部公开，问剩下的牌还剩多少可预测性。答案是盯了也白盯——其余牌的落点在已知信息之下依然近乎均匀，被观察的牌只是充当了不改变结局的”路障”。
第二级台阶
精确化：@@M@@d@@ 个坐标方向各更新一次称为一扫，耗费 @@M@@d@@ 次物理洗牌；被观察的牌称为阻挡牌，其占住的位置构成可用位置集的补。在观察信息（阻挡牌的轨迹）之下，某张隐藏牌的分布称为条件律；基准分布是把可用位置无放回、均匀填满的均匀单射，两者之差用总变差度量。
第三级台阶
定理在确定性坐标循环（方向不随机）与”固定比例的牌未被观察”两条假设下陈述：前者使收缩完全来自日程的几何结构，后者保证两端可用的开关大量存在、平均机制不被路障堵死。结论对任意确定性初始牌序与任意指定列表一致成立：@@M@@256d@@ 次后任取至多 @@M@@7n/8@@ 张牌，其像与均匀单射的距离为 @@M@@o(1)@@；@@M@@1024d@@ 次后收紧到 @@M@@n^{-3/2}@@；整副牌经 @@M@@2048d@@ 次物理洗牌后总变差趋于零。条件版更进一层：固定阻挡集与不相交列表，固定个数（依赖比例）的扫之后，条件律与均匀单射的期望距离不超过 @@M@@kn^{-4}@@——误差只对被观察路径取平均，不逐条断言。
证明了 Thorp 洗牌整副牌的混合时间具最优阶：@@M@@n=2^d@@ 张牌经 @@M@@2048d@@ 次物理洗牌后排列律趋于均匀；关键在于即使观察任意一大批牌的完整路径，其余牌的条件落点仍近乎均匀。
Thorp 洗牌（Thorp shuffle）由 Thorp 于 1973 年研究 Faro 牌技时提出：把 @@M@@2^d@@ 张牌对半分开，对应位置两两配对，各自独立、公平地决定是否交换。等价地，牌位置是 @@M@@\mathbb F_2^d@@ 的顶点，一次物理洗牌沿一个坐标方向做独立公平交换并轮转坐标；@@M@@d@@ 个方向各更新一次称为一”扫”（sweep），耗费 @@M@@d@@ 次物理洗牌。单张牌一扫后即均匀，但所有牌共用同一批随机开关，联合秩序远未均匀。由于每次物理洗牌只消耗 @@M@@n/2@@ 个随机比特，混合时间至少 @@M@@2d-O(1)@@；而上界长期停留在 Morris 的 @@M@@O(d^{44})@@（2008）、Montenegro–Tetali 的 @@M@@O(d^{29})@@ 与 Morris 的 @@M@@O(d^3)@@（2013）。Morris 的熵方法已表明”暴露部分牌后剩余的信息”是全牌混合问题的核心，但此前无人能对指定的大列表给出均匀的条件界，这正是本文的切入点。
主定理对任意确定性初始牌序、任意指定的有序标签列表成立（@@M@@d\to\infty@@）：
@@M@@256d@@ 次物理洗牌后，任意 @@M@@k\le 7n/8@@ 张牌的像与均匀单射分布 @@M@@\Unif(\operatorname{inj}([k],V))@@ 的总变差距离（total variation）为 @@M@@o(1)@@；@@M@@1024d@@ 次后，任意 @@M@@k\le 15n/16@@ 张牌的距离不超过 @@M@@n^{-3/2}@@；@@M@@\|q_d^{*(2048d)}-U_{S_n}\|_{\TV}\to 0@@。结合支撑数下界得混合时间 @@M@@t_{\mathrm{mix}}=\Theta(\log n)@@，阶数最优。另有条件版强化：固定基集 @@M@@B@@ 与不相交列表（@@M@@|B|+k-1\le pn@@），固定个数 @@M@@2b(p)@@ 个扫后，条件律与均匀单射的期望总变差 @@M@@\le kn^{-4}@@，且误差只对被观察路径取平均而非逐条断言。这种”平均意义下对指定列表”的条件信息界是本文的独有贡献。
整个证明把”看牌”翻译为带噪声的线性递推。设已观察一组”阻挡牌”（blocker）的路径，@@M@@V_t@@ 为可用位置，被追踪牌的条件误差向量 @@M@@f_t(x)=\Pr\{\Pi_t(a)=x\mid\mathcal H_t\}-\mathbf 1_{V_t}(x)/|V_t|@@ 是 @@M@@V_t@@ 上支撑的零和向量。其更新规则：两端都可用的位置对上取平均，仅一端可用的位置对上把质量搬运到唯一可用输出。于是 @@M@@f_{t+1}=P_{i_t}f_t+\xi_t@@，其中 @@M@@P_i@@ 是坐标 @@M@@i@@ 的成对平均算子，@@M@@\xi_t@@ 是条件零中心的噪声。第一个关键恒等式：全部 @@M@@d@@ 个方向的 @@M@@P_i@@ 之积把任何零和向量压为零，故一扫之后能量 @@M@@a_t=\E\|f_t\|_2^2@@ 完全来自上一扫内部新生的噪声，且 @@M@@j@@ 步之前的噪声恰带几何权重 @@M@@a_t=\sum_{j=1}^d2^{-j}w_{t-j}@@，其中 @@M@@w_t@@ 度量”伙伴位置被阻挡”处的能量，正是搬运噪声的源头。
再证 @@M@@w@@ 相对 @@M@@a@@ 压缩（half-density 引理）。考察当前坐标上一次被使用的时刻：其后两半中的阻挡数接近平衡（Hoeffding 界），而中间的 @@M@@d-1@@ 层在两半中独立作用，故伙伴被挡的指示变量与 @@M@@f_s(x)^2@@ 条件独立，其条件均值就是该半的阻挡比例。在好历史上求和得 @@M@@w_s\le(1-\delta)a_s+\eta_n\|f_0\|_2^2@@（@@M@@\delta=\alpha/2@@，@@M@@\eta_n=2e^{-\alpha^2n/4}@@），代入比较递推得指数收缩 @@M@@a_t\le(\gamma^{t-2d}+\eta_n/\delta)\|f_0\|_2^2@@，@@M@@\gamma=1-\alpha/4@@。
然后按序暴露列表：把已见牌当作阻挡，下一张牌的条件期望误差 @@M@@\le\sqrt{na_T}/2@@（Cauchy–Schwarz）；在真实前缀律与均匀无放回延拓的相邻律之间插值并求和，分别取 @@M@@\alpha=1/8@@ 与 @@M@@1/16@@ 即得两个大列表界。
最后由部分信息回到全牌：把标签分成 8 个等块，对每块之补应用 @@M@@256d@@ 界（补集的端点像恰好是左陪集 @@M@@gH_i@@ 的信息），删去质量超过均匀两倍的陪集得保留律 @@M@@\nu@@；借助伙伴篇《From partial permutation information to Fourier bounds》的等型（isotypic）转移 @@M@@\|\widehat\nu(\lambda)\|_{\HS}^2\le 32C_2D_\lambda^{-1/2}@@，再经 Plancherel 恒等式与卷积完备化（取 @@M@@p=8@@ 次幂）得 @@M@@\|\nu^{*8}-U_{S_n}\|_{\TV}\to0@@，共 @@M@@8\times256d=2048d@@ 次物理洗牌。后续章节给出熵、调色板、探针等不同的条件机制——它们提供的是不同的条件陈述，而非更优的混合常数。
本篇主结果暂无形式化证明，请以社区核验为准。族内姊妹篇互相支撑：伙伴篇《Optimal-order mixing of the Thorp shuffle》独立给出 @@M@@1600d@@ 的局部证明；《Conditional permutations in a revealed switching environment》从”揭示环境下的条件置换”角度给出另一条常倍 @@M@@d@@ 路线；已 Lean 形式化的《Routing densities and representation contraction for Thorp sweeps》则给出绝对常数个扫的表示论收缩。按 OpenAI 官方声明，未经形式化的结果可能有问题。
问 1：条件界的误差为什么只对被观察路径取平均，而不逐条断言？这是技术偷懒吗？
（答：不是偷懒，是诚实标注强度。平均界一般不蕴含逐路径成立：个别的罕见历史（如阻挡牌恰好排成整排路障）可能携带大误差，只是概率小；论文原文明确写”it is not asserted for every possible history”。相对地，固定列表的无条件界是对每个指定列表一致成立的——两种量级不同的承诺，文章分得很清楚。）
问 2：证明中最关键也最脆弱的一步是什么？
（答：确定性日程为何收缩。条件误差向量满足 @@M@@f_{t+1}=P_{i_t}f_t+\xi_t@@，一扫的成对平均算子之积湮灭零和向量，能量全来自上一扫新生的噪声且带精确几何权重；控制噪声要看当前坐标上一次被使用的时刻——其后两半阻挡数近平衡（Hoeffding 界），中间 @@M@@d-1@@ 层在两半独立作用，使伙伴被挡的指示变量与误差平方条件可分离。与 swap-or-not 的随机配对不同，这里方向是 prescribed 的，收缩必须从日程几何中挣出来，这一分离论证是全篇命门。）
问 3：与 Morris–Rogaway–Stegers、Czumaj–Vöcking 的边际结果相比新在哪？
（答：MRS 只对至多 @@M@@n^{1-\varepsilon}@@ 张的指定列表给出 @@M@@O_\varepsilon(d)@@；Czumaj–Vöcking 用蝶形网络非马尔可夫耦合对固定比例列表做到 @@M@@O((\log n)^2)@@，但其全排列算法添加空牌、链不同。本文首次对指定的大列表（@@M@@7n/8@@、@@M@@15n/16@@）给出一致界并配套条件信息界，再借 Fourier 传递得 @@M@@2048d@@ 全牌混合。）
问 4：”固定比例的牌在两个列表之外”这条假设能去掉吗？
（答：去不得。若观察的牌几乎占满全副，两端可用的开关所剩无几，平均机制失效，误差只能靠搬运传播、不再收缩；假设正是保证两半各留固定比例空位、半密度引理得以运转的前提。列表与阻挡集合计 @@M@@|B|+k-1\le pn@@ 的记法即由此而来。）
问 5：这类 AI 生成证明最可能的出错模式？
（答：三处高危。几何权重 @@M@@2^{-j}@@ 的精确恒等式差一个因子就破坏比较递推；”跨半条件独立”常被误加强为无条件独立（例外事件与能量相关，只能靠 @@M@@\|f_0\|^2@@ 兜底）；后段熵、调色板、探针等章节陈述各异但共享同一标量输入，若某个”推广”悄悄更换了输入的适用范围而不重验，即成隐性漏洞。）
问 6：为什么后面大量章节给出的不是更优常数？
（答：论文自陈：熵、调色板、探针等机制提供的是不同的条件陈述而非改进的混合常数——不同信息结构对应不同下游应用，混合常数的改进路线在姊妹篇 @@M@@1600d@@。）
问 7：下游谁在用？
（答：全牌 @@M@@2048d@@ 混合确立最优阶 @@M@@\Theta(\log n)@@；条件信息界直接刻画”暴露部分明文后剩余不确定性”，是小域加密分析的天然语言；族内与 @@M@@1600d@@（局部证明）、随机坐标架 @@M@@32800d@@、已形式化的 Routing densities 篇互相校验。）
总评
本文把”暴露部分牌后还剩多少信息”从 Morris 熵方法中的启发式障碍变成可陈述、可证明的量，且诚实区分平均界与逐条界，方法论价值不亚于 @@M@@2048d@@ 本身；最大风险在跨半独立与精确几何权重这两处机器最精密的齿轮上。