结果族 115：Sampling and counting contingency tables with arbitrary margins · 学科：Theoretical computer science · 验证状态：暂无形式化证明，请以社区核验为准
还是填表，但有些格子被贴了封条或限了容量：比如”三季度×广告部”这一格禁用，”差旅费”那一格至多 2。行和、列和、逐格上界都以二进制给出，数清所有合法填法的总数——精确计数是 #P 难的，本文给出 FPRAS：多项式时间的随机估计，误差 ε、失败率 δ 可控，而且每次运行都有最坏情形的时间上界。
关键词卡片
@@M@@b_{ij}=0@@ 表示此格为禁区。看个具体例子
行和 (3,2)、列和 (2,3) 的 2×2 表本有 2 张。现给左上格加上界 @@M@@b_{11}=1@@：左上格为 2 的那张被排除，只剩第一行 (1,2)、第二行 (1,1) 的一张，故 Z=1；若取 @@M@@b_{11}=0@@，则一张都不剩，Z=0。定理的数字版：@@M@@\Pr[(1-\epsilon)Z\le\hat Z\le(1+\epsilon)Z]\ge1-\delta@@，且 Z=0 时每次执行必输出 0。
为什么值得关心
它把列联表计数推到”两维任意、数据全二进制、允许禁区”的最一般形态，还顺带解决了有界整值网络流的计数与采样——从填表到物流都在射程内。此前的研究都要固定行数、正容量下界或密度假设，禁区更让可行集失去规整形状。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读的”贴封条的填表”可以改述为：往 m 行 n 列的格子里填非负整数，除了每行合计、每列合计被钉死外，每个格子还有各自的容量上限，上限为零即禁区；要数的是同时满足这三层要求的填法总数。困难仍是计费：一切数字以二进制书写，一个格子的容量可以远大于它的描述长度，”按数值展开”的路被堵死。
第二级台阶
用本科术语精确化。给定行和 r、列和 c 与逐格上界 b，可行集 Ω(r,c,b) 是满足全部约束的非负整数矩阵，b_ij=0 刻画结构性零；记其基数为 Z(r,c,b)，精确计数是 #P 难的。FPRAS 指这样的随机算法：以多项式于总输入长 L、ε⁻¹ 与 log δ⁻¹ 的时间，输出落中 (1±ε)Z 的估计、概率至少 1−δ。
第三级台阶
定理在这样的语境下陈述：存在单一随机算法，只使用独立无偏比特、不需要任何计数或采样预言机，输出落中 (1±ε)Z(r,c,b) 的 ̂Z；可行集为空时每次执行必输出零；且一个关于 L、ε⁻¹、log δ⁻¹ 的固定多项式在每次执行——包括失败事件中——都界定总位操作数。不固定行数或列数、不要求正容量下界、不设密度或平衡假设——这些正是旧结果各自依附的条件；”每格上界”更让可行集不再是完整运输多面体的整点集，组合形状由此破碎。结论用导读的话说：填表到物流（有界整值网络流）都在射程内。
本文证明：行和、列和与逐格上界（允许取零，即结构性禁区）都以二进制编码、两个维数任意变化的列联表计数，存在完全多项式随机近似方案（FPRAS），且每次运行的比特开销都有一致多项式上界。
在列联表（contingency table）上再给每个格子一个上界 @@M@@b_{ij}@@，其中 @@M@@b_{ij}=0@@ 表示该格被禁止放置（结构性零），要数的是同时满足行和 @@M@@r@@、列和 @@M@@c@@ 与所有格界的非负整数矩阵个数 @@M@@Z(r,c,b)@@。精确计数是 #P 难的，目标是完全多项式随机近似方案（FPRAS，fully polynomial randomized approximation scheme）：以 @@M@@1-\delta@@ 的概率给出 @@M@@(1\pm\epsilon)@@ 相对误差内的估计。困难仍在二进制编码：一个格子的容量可以远大于其描述长度，不能被展开成那么多独立选择；此前已知的列联表计数与采样结果都需要固定行数、正容量下界或密度/平衡之类的假设，而逐格上界还让可行集不再是完整的运输多面体（transportation polytope）整点集，组合结构更复杂。
主定理：存在一个随机算法，输入 @@M@@(r,c,b)@@ 与有理数 @@M@@\epsilon,\delta\in(0,1)@@，输出非负有理数 @@M@@\widehat Z@@，满足
@@M@@D\P\bigl((1-\epsilon)Z(r,c,b)\le\widehat Z\le(1+\epsilon)Z(r,c,b)\bigr)\ge 1-\delta.@@
若可行集为空，则每次执行都输出零。算法只使用独立无偏比特，且存在关于总输入长度 @@M@@L@@、@@M@@\epsilon^{-1}@@ 与 @@M@@\log(\delta^{-1})@@ 的一个固定多项式，在每一次执行（包括失败事件中）都界定其总比特操作数；不需要任何计数或采样预言机。
证明把”数值大小”与”组合复杂度”拆开处理。先用网络流（Edmonds–Karp 最短增广路）做可行性判定，并用二分搜索把每格收紧到其可达区间，平移后每格的 @@M@@0@@ 与 @@M@@b_s@@ 两端都各自被某张可行表取到；再按多项式阈值 @@M@@W@@ 把格子分成小格与大格。大格构成一张二部图，取最大容量生成森林：林外的大格作为自由坐标，树上格子的值由非根行/列方程经叶子消去唯一确定，根处的偏差记入罚项。小格则引入双视角：行贡献 @@M@@x_s@@ 与列贡献 @@M@@b_s-y_s@@，二者相等当且仅当 @@M@@x_s+y_s=b_s@@。对自由取值定义罚项 @@M@@D@@ 度量其对根边际与树格界的违反，软化权重 @@M@@h_j=\sum_z 2^{-jD/H}@@ 只在平衡轮廓上求和得到配分函数 @@M@@C(j)@@；@@M@@C(0)@@ 显式可算，”污染界” @@M@@Z\le C(H)\le(1+\epsilon/32)Z@@ 则把近似计数与原问题挂钩。
接下来做二进制化编码：把界为 @@M@@b_s@@ 的小格替换成 @@M@@b_s@@ 个带标号的”行–列”元素对，横截面（transversal）从每对中恰选一个元素；配上阶乘归一化后横截面的总质量恰为 @@M@@C(j)@@。作者构造了两个不同的提升权重 @@M@@f_j@@ 与 @@M@@\widetilde f_j@@：它们在横截面上相等，分别满足”删二”与”添二”二次型性质——相关矩阵至多有一个正特征值，即 Brändén–Huh 的 Lorentzian 准则在此的离散版本。算法运行在扩充链上：状态空间为横截面加上”一对空、一对满”的缺陷类（defect），Metropolis 交换链配上每类一个乘子 @@M@@w_{il}@@；乘子从观测到的类频率在线学习，这是 Jerrum–Sinclair–Vigoda 求积算法的经典手法。传输（transport）与可观测量方差分析改编自该团队关于两个拟阵公共基计数的工作，同时控制相邻比值 @@M@@C(j+1)/C(j)@@ 与缺陷类概率的估计精度，以及横截面迹（trace）的混合与回返成本；退火乘积 @@M@@C(H)=C(0)\prod_j C(j{+}1)/C(j)@@ 给出计数。权重 @@M@@h_j@@ 本身无法枚举：把自由坐标范围分成每坐标 @@M@@B@@ 个箱，在 dyadic 箱权重上做 Metropolis 游走、估计相邻比值、再做人口修正，得到有界的权重求值子程序。最后，单次运行成功概率超过 @@M@@3/4@@，取中位数放大到 @@M@@1-\delta@@；所有有限选择都用固定数量的公平比特实现，并用耦合控制实现误差。
本结果暂无 Lean 形式化证明，请以社区核验为准；OpenAI 官方声明”未经形式化的结果可能有问题”。姊妹篇《Exact Uniform Sampling of Contingency Tables with Arbitrary Margins》解决同族的无界采样侧，两文共享二次签名与传输骨架、互为支撑；本文末节还把结论推及有界整值网络流（network flow）的计数与总变差采样。作者也自陈文中多项式指数非常宽大，是统一的理论保证而非实用运行时间估计。
问 1：证明里最关键也最脆弱的一步是哪里？
答：污染界 Z ≤ C(H) ≤ (1+ε/32)Z。算法退火的目标 C(H) 是软化权重下的配分函数，除合法表外还混入违反根边际或树格界的”污染”完成；论文靠树坐标边际的对数凹性与可达端点控制边界附近的违反、靠指数衰减控制远处违反（引言 From tables to weighted transversals 段）。这个 (1+ε/32) 相对因子若在任何一类污染完成上失控，退火终点就不是 Z，整条连乘计数失去意义。
问 2：为什么允许 b_ij=0（结构性禁区）是个实质性难点？
答：禁区让可行集不再是完整运输多面体的整点集——多面体的规整组合结构（顶点、邻接、整数性）随之破碎，几何方法与热浴链的经典论证不再直接适用。历史上 cell-bounded 结果（Cryan–Dyer–Randall）须固定行数，0/1 表的 BBV 结果只覆盖二值格；本文同时放开维数、二进制数值与零界，是三重松绑的首次叠加。
问 3：与已有工作相比真正的新意是什么？
答：把”两维任意＋数据全二进制＋允许禁区”的列联表计数做成 FPRAS，且每次执行（含失败事件）都有一致位操作多项式界；附带把有界整值网络流的计数与总变差采样一并解决（flows 节）。技术上，双阶乘提升 f_j 与 f̃_j 在横截面上重合、分别满足”删二/添二”的 Lorentzian 型二次签名，是 Brändén–Huh 准则在此需要的离散版本——论文明言”成对求和下的保持将被证明而非假设”。
问 4：这个结果最可能以什么模式出错？
答：三处高危：其一，签名封闭性的整数求和论证（删二/添二矩阵至多一个正特征值、在成对求和下保持），这是从母篇（两拟阵公共基计数，已 Lean 形式化）改编而来的新件，改编部分不在形式化范围内；其二，权重求值子程序——在每坐标 B 个箱的格点上做 Metropolis 游走再加人口修正，箱内整数个数不同引入的偏倚若修正不净会污染各级比值；其三，乘子在线学习与自适应估计的耦合。全文无形式化证明，多项式指数刻意宽大。
问 5：为什么要构造两个不同的提升权重，而不是一个？
答：分工明确：f_j 的删二签名控制条件横截律之间的运输（比值估计的精度来源），f̃_j 的添二签名比较缺陷类的质量（乘子平衡的依据）；两者在横截面上相等保证同一链可同时服务两套估计，在缺陷类上仅差多项式因子使不等式可以互相搬运（引言 Binary encodings 段）。单权重无法同时具备两种互补的二次型性质。
问 6：谁会用到它？
答：统计侧，带结构性零的列联表精确检验与隐私数据合成发布获得首个一般计数工具；组合侧，有界整值网络流的计数与采样（每条弧有容量上限的整数流）是现成的推论；方法侧，”双签名权重＋迹链”与姊妹篇的采样骨架互为印证，也是族 114 多拟阵篇的直接技术来源之一。
总评
它把列联表计数推到现行输入模型下最一般的形态，并外溢到网络流计数，分量十足；最大风险集中在污染界与签名封闭性两处新证明上——都未经形式化，且直接决定退火目标是否真的是要数的那个 Z。