隔离引理

不逐对比较指数多个集合 ​

任意两个不同集合，总在某个元素e上一个包含、一个不包含。因此，若最低总权仍并列，至少有一个元素的“是否属于最优解”没有确定下来。

证明逐个检查这样的成员身份。固定其它元素权后，含e的集合总权随wₑ以斜率1一起上升，不含e的集合总权完全不动。两类的最低值至多在一个wₑ上打平，无须比较两类内部究竟有多少候选。

每个元素只有一个危险权 ​

固定所有 $w_f$（f≠e），定义

若某一类为空，所有可行集合都强制包含e或都排除e，成员身份不会含糊。两类都非空时，最小总权分别为aₑ与bₑ+wₑ；只有在 $w_e=a_e-b_e$ 时，两类都能达到全局最优。

aₑ−bₑ完全由其它权决定。条件于这些权后，wₑ仍在1..R上均匀，因此e成员身份含糊的概率至多1/R。危险值不在1..R内时，概率为0。

若存在两个不同的全局最小集合A、B，从它们的对称差选e，便有一个最优集合含e、另一个不含e。故“不唯一”包含于m个成员身份坏事件的并集。用并集界理路并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。，失败概率至多m/R。不同e的坏事件可以高度相关；并集界不要求它们独立。

两个互斥候选的精确失败率 ​

取 $E=\{a,b\}$、$\mathcal{F}=\{\{a\},\{b\}\}$、R=4。16种等概率权向量中，只有(1,1)、(2,2)、(3,3)、(4,4)仍并列，实际失败率1/4。引理给m/R=1/2，是可靠但较松的上界。

若改成只抽一个r并令wₐ=wᵦ=r，每个权的边际分布仍均匀，却每次并列。固定其它权后wₐ不再自由，阈值证明失效。

一次权表可以隔离指数族，却不会替你找到最优者 ​

取全部非空子集为集合族，权均为正。最小集合必是某个单元素集；若最小元素权唯一，就已隔离。这只是一个容易求解的例子。对一般隐式集合族，判断是否存在可行集合、计算最低权或验证唯一性，仍可能很难。

引理只保证随机扰动的结果具有唯一最优解，不提供一个通用求解器。若求解器依赖唯一性，应证明在成功隔离时它确实恢复该解，并规定未隔离时怎样安全失败。

权随输入族变化的量词陷阱 ​

如果先看见权，再故意挑两个权相同的集合来定义 $\mathcal{F}$，便把集合族变成随机量。即使某些权向量找不到这样的两个集合，也不能逐轮筛选后再引用固定族的失败概率。应用时应先写清楚：图、可行性约束与原成本先固定，随机的只有新扰动权。

保留原整数目标，再打破最优解并列 ​

设每个元素已有固定整数成本cₑ，目标先最小化 $c(A)=\sum _{e\in A}{c}_e$。仍取wₑ∈1..R，改用

两个集合的原成本若相差至少1，缩放差至少mR+1；它们的扰动总权之差绝对值至多mR，所以原来的严格优劣不会翻转。再对事先固定的原成本最优族 $\mathcal F_* $ 应用引理，即以至少1−m/R概率从原最优解中挑出唯一者。负整数原成本也不破坏这一比较。

若原成本是任意实数、最小正差未知，不能机械使用mR+1；扰动可能压过极小的原成本差。即使成本是二进制整数，后续若把数值用作指数，也要另算产生的大整数位长，不能把“输入位数小”与“成本数值小”等同。

完美匹配的代数提取 ​

Tutte矩阵理路Tutte矩阵Tutte matrix · 图匹配的Tutte矩阵以反对称边变量矩阵编码一般图完美匹配，证明随机行列式判定，并用隔离权与二进阶主子式提取可验真匹配。把边权wₑ编码成整数 $2^{w_e}$。唯一最低权的完美匹配使行列式的最低二进制幂次不被其它项消去；删去一条候选边两端点的主子式，再识别这条边是否属于该匹配。

整个过程不需要预先证明这次权表确实隔离。它最后逐边检查返回集合是否覆盖每个顶点且无冲突；证书失败就重试。R=2m只给YES实例每轮至少1/2的成功概率，不保证无解实例经过若干失败后就获得不存在证书。

手算迁移与成本账 ​

对 $\mathcal{F}=\{\{a,b\},\{b,c\},\{a,c\}\}$，固定wᵦ=2、w𝚌=5。含a的最小余重是2，不含a的权是7，故a的危险权为5。若wₐ=1，唯一最小集合为{a,b}；若wₐ=5，{a,b}与{b,c}并列；若wₐ=6，唯一最小集合为{b,c}。不要把“a成员身份确定”误认为整族已经唯一：还须所有元素身份都确定。

生成一张权表需m次整数抽样和O(m log R)位存储。若R不是2的幂，可以用拒绝抽样获得精确均匀分布，每项期望少于两次候选；它没有固定最坏抽样次数。需要固定随机位上界时，改选不小于2m的二次幂R，仍有m/R≤1/2。求最优集合或执行代数提取的成本不包含在这张权表成本内。