优先级抽样

暂时拿走一条记录，门槛就不再依赖它 ​

固定所有 $U_j$（j≠i），令 ${\theta }_i$ 为其它记录的第 k 大优先级；不足 k 条时设为0。此时只有 $U_i$ 还随机。i入选当且仅当 $q_i>{\theta }_i$，而它一旦入选，全体第 k+1 大优先级恰为 ${\theta }_i$。

若 $w_i\ge {\theta }_i$，则 $q_i>w_i\ge {\theta }_i$，i必入选，贡献就是 $w_i$。若 $w_i<{\theta }_i$，入选条件是 $U_i<w_i/{\theta }_i$，概率为 $w_i/{\theta }_i$，入选时贡献为 ${\theta }_i$。两种情况的条件期望理路条件期望Conditional expectation以信息分组的加权平均建立条件期望直觉，再连接测度定义、最小均方预测、塔式性质和可计算反例。都是 $w_i$。再对其它随机数取平均，逐项无偏成立；对子集求和只需期望线性性。

这个证明解释了阈值修正的作用。较小记录经常缺席，偶尔入选时被提高到门槛；较重记录若本来就高于门槛，无须放大。把入选后的原权重直接相加，会漏掉缺席记录应有的平均贡献。

为什么需要多保留一名 ​

用一个容量 k+1 的最小二叉堆理路二叉堆Binary heap用完全二叉树形状与父子堆序维护极值、常以数组隐式表示的数据结构。维护最大优先级，堆顶是这 k+1 项中最低者。读新记录时，堆没满就加入；满后只在新优先级更大时替换堆顶。处理任意前缀后，堆包含该前缀的前 k+1 名，这是普通截断极值不变量。

最终最高 k 项参与查询，额外一项只提供 $\tau$。只保存前 k 项及它们原权重，通常无法恢复这个阈值。若两份流的记录ID互斥，局部前 k+1 名合并后再截断就是全局前 k+1 名：被某片丢弃的记录，在该片已有 k+1 个更高者，不可能进入全局前列。

记录若在两片重复，不能直接拼堆。即使同ID共用 U，不同片给出的权重也未必是同一最终权重；合并部分计数会改变优先级。本文附件的 merge_disjoint 明确要求互斥ID，既不猜测重放含义，也不暗中保存全体已见ID。

方差与两项乘积也可在条件下算清 ​

仍固定除i外的随机数。写 $p_i=min(1,w_i/{\theta }_i)$、$m_i=max(w_i,{\theta }_i)$，${\theta }_i=0$ 时取 $p_i=1$。条件二阶矩为 $p_i{m}_i^2=w_i{m}_i$，所以条件方差为 $w_i(m_i-w_i)$。条件均值恒为 $w_i$，其自身没有额外波动，因此再取平均即得到真实方差。

入选时报告 ${\theta }_{i}max(0,{\theta }_i-w_i)$，乘上条件入选概率，恰等于 $w_{i}max(0,{\theta }_i-w_i)$，与条件方差相同。这证明单项方差估计无偏。

对不同 i、j 且 $k\ge 2$，固定其它所有随机数，令 $\theta$ 为剩余记录第 k−1 大优先级，不足时为0。i、j同时入选，当且仅当两者优先级都超过 $\theta$：否则二者较小者前面至少已有 k−1 个其它记录和另一项，共 k 个更高者。同时入选时 $\tau =\theta$，故条件乘积期望为

零门槛按必入选处理。这里使用 $U_i,U_j$ 的条件独立性，得到的是贡献乘积的期望。由此零协方差成立，子集方差等于单项方差之和。

四条记录的完整阈值账 ​

取k=2，依次读入：

前三条后，堆保存优先级4、10、5。第四条与ID0并列，按较小ID优先的规则不替换；最高两条为ID1、2，$\tau =4$。这是手工指定随机数的轨迹，并列规则用于检验程序；连续随机模型中恰好并列的概率为零。

ID1的估计贡献为5，ID2为4，总量估计9，而真实总量11。若查询事先确定的子集 $I=\{0,2\}$，估计为4，真实总量3。该样本的全体方差估计为 $4max(0,4-5)+4(4-1)=12$；一次方差估计本身也不是已知真实方差。

固定子集不等于看完抽样再挑获利者 ​

协议为某个固定值、记录日期落在某段区间，或由独立外部资料确定的类别，都可以在摘要生成后才提出查询。证明不要求早就知道查询名称，而要求集合成员身份不依赖这次抽样的 U。

若看完样本后把 I 定义为“恰好入选的那些ID”，I已经是随机输出的一部分。逐项证明对固定系数求和，不能自动推广成任意依赖样本的选择规则；尤其不能只挑估计贡献最大的属性组合，然后仍把它当作预先固定查询的无偏比较。

有限随机网格会让轻项永远没有机会 ​

设两条权重为1、4，k=1，却让每个 U 只能等概率取1/3、2/3。轻项优先级至多3，重项至少6，所以轻项永不入选，估计期望为0而非1。确定破并列也无法修补这个例子，因为根本没有并列。

因此附件用有理数做堆轨迹和门槛积分，并没有声称有限网格就是理想连续模型。工程浮点或有限位随机源若要获得量化误差界，需要把可取最小 U、舍入和权重动态范围另行纳入分析。

容量一的无穷方差不是实现异常 ​

k=1时，${\theta }_i$ 是其它正权优先级的最大值。任取另一条 j，当 t大于 $w_j$，有 $\text{Pr}({\theta }_i>t)\ge \text{Pr}(w_j/U_j>t)=w_j/t$。尾积分发散，$\mathbb{E}{\theta }_i=\mathrm{\infty }$，故i的二阶矩 $w_i\mathbb{E}max(w_i,{\theta }_i)$ 为无穷。

k≥2时，${\theta }_i>t$ 要求至少k个其它独立优先级超过t。对有限记录集，按k元子集作并集界，尾概率为 $O(t^{-k})$，因而一阶尾积分有限，贡献的二阶矩也有限。若n≤k，所有正权项保留、$\tau =0$，总量与方差分别精确和为零。

堆成本与数值模型 ​

在实数算术和比较按单位成本的模型下，每条记录至多一次 $O(\log (k+2))$ 堆操作，n条记录时间 $O(n\log (k+2)+1)$，状态为 O(k+1) 条记录。合并两个互斥分片的堆需 $O((k+1)\log (k+2))$ 时间；查询可扫描保留记录，属性判定为常数成本时需 O(k+1) 时间。

附件为清楚输出名次，会先把堆排序，因此 estimates() 实际花 $O((k+1)\log (k+2))$。使用 Fraction 的除法、比较还取决于整数位长，不能用实数RAM界声称任意大有理数操作常数时间。记录身份唯一是输入合同；若输入方不能保证，验证全部历史ID还需额外存储。

权重聚合是抽样之前的决定 ​

若目标是每个不同键的总字节数，必须先得到该键固定总权重，再给它一个 U；若目标单位是每条事件，则每条事件必须有不同ID。两种对象均可采用本构造，但不能在同一ID上不断重抽U，或把局部权重的优先级摘要直接当成聚合权重的摘要。

删除或减轻一个保留项后，可能需要补回此前丢弃的第 k+2 名，本状态无法恢复它。共享随机键可以支持正确分片协调，却不会凭空补出没有保存的数据。

共享随机键终结任务要求报告第 k+1 名、固定子集估计、无偏性条件积分及有限网格反例；另将两份互斥ID流的合并堆与集中排序逐项比较。