小型随机样本为何需要精确约定
日志文件可能大得无法全部保留,而且第一条记录到达时,我们未必知道最终共有多少条。保留最初一千条记录虽然便宜,却完全剥夺了后来记录入选的机会。若每条记录各自以千分之一的概率保留,所有记录都有机会,但保留数量又未必能限制在一千条。我们要的是另一种约定:读完任何有限前缀后,在固定容量内保留一个均匀抽出的子集。
抽样对象是每次出现的记录,以其位置或不可变的唯一标识符区分。两条数值相同的记录仍是两个不同的对象。不放回抽样禁止同一次出现被选两次,并不禁止样本含有相同数值。以下先把输入数据流固定,再讨论抽样的概率律。若数据本身是随机的,而抽样随机数与数据独立,则在给定数据后仍有相同结论。若对手会查看蓄水池,再改变后续输入或决定何时停止,就需要另外分析。
方法只保留有界数量的记录、精确整数计数,以及明确指定的随机来源。实现一节会区分数学模型与可以实际执行的伪随机示范。
蓄水池不变量与单次扫描更新
定义 11.1.1
(容量为 的均匀蓄水池)
固定整数容量 。读入 次出现后,记 及 。正确的蓄水池 是 的随机无序子集,并满足
公式最后一项表示:每个大小为 的目标子集都具有同一概率。当 ,唯一子集是空集。当 ,所有记录都保留,所以分布集中在 。容量为零时,蓄水池始终为空。存储数组的先后位置只供算法使用;不变量并没有声称数组顺序也是均匀排列。
先填满最初 个数组位置。其后每次收到 ,都重新抽取一个在 上均匀的整数 。若 ,以 替换第 个位置的记录;否则不变。因此新记录以 的概率入选,而每个特定已占用位置以 的概率被替换。抽取范围必须反映目前计数,不能一直使用固定上限。
定理 11.1.2
(每个有限前缀都有均匀子集)
假设给定全部先前抽样历史后,每个更新整数仍条件均匀,并与固定输入独立。对每个确定的有限 和每个容量 ,算法都满足上述不变量,而且无需预先知道最终数据流长度。
证明
(对前缀长度归纳)
当 或 ,结果是确定的,已满足不变量。对 ,由 开始归纳。设 ,并假设读完 条时不变量成立。固定 的一个 元子集 。
若 ,先前蓄水池必须恰为 ,且本次不能替换任何位置。因此
若 ,令 。先前蓄水池必须是某个 ,其中 。这样的选择共有 个。对每一种先前蓄水池,恰有一个位置存储 ,而本次选中该位置的条件概率是 。各种先前状态互不相交,故
两种情况涵盖所有 元子集。条件均匀性让我们把先前状态概率乘以相应的更新概率,无论 在数组的哪个位置都成立。归纳完成。
证明透视
每项假设在归纳中的位置
归纳假设用在 的整个 元子集上: 的情形要对 个先前蓄水池 求和,每一项都需要确切值 ,而不只是某条记录的存活概率。给定全部历史后 的条件均匀性用了两次:不替换时乘以 ,选中存放 的唯一位置时乘以 ;由于每个位置的条件概率相同, 在数组的哪个位置并不重要。两种情形都化为恒等式 ,归纳因此闭合。若各更新整数共用随机数,即使每个 的边际分布均匀,这些乘积也不再成立;下文共用抽取的练习题会算出由此产生的偏差。
常见错误
(相同入选概率不等于不变量)
很容易只验证每条记录以 的概率被保留。考虑四条记录、容量二:各以一半概率选 或 ,每条记录的入选概率的确都是一半,但六种可能配对中有四种永不出现。不变量是关于每个目标子集的陈述,所以证明追踪的是子集。
对无限到来的数据流,每个固定有限前缀都有正确蓄水池,但不存在可数无限数据流的最终均匀固定大小样本。若每个正整数的入选概率都相同且为正,样本的期望大小便是无限;若它们都为零,可数个零概率事件的并集仍为零,所以样本几乎必然为空。当 ,两者都不可能描述大小为 的样本。
有限前缀定理亦容许与抽样过程独立的随机停止计数:先给定该计数,再使用固定计数的结论即可。
常见错误
(因蓄水池“看起来有趣”而停止)
查看蓄水池的停止规则与抽样随机数并不独立。例如 时,若第二条入选便在计数二停止,否则到计数三才停止。以“在二停止”为条件,第二条的入选概率是一,而不是二分之一。定理只适用于每个固定计数,或与抽样决策独立选取的计数。
分区摘要必须保留什么
定义 11.1.3
(分区摘要)
在容量 下,含 次出现的分区的摘要是一对 :精确计数 ,以及该分区大小为 的均匀蓄水池 。
设互不重叠的分区 分别有 次出现,各工作节点用彼此独立的随机数建立并返回摘要。计数描述原始分区,不是保留数组的长度。空分区的计数为零,其蓄水池也为空。
令 及 。并集的均匀 元子集,会含有一个随机数量 的 区记录。直接计算子集数量,得到超几何分配律
合并时,先使用与两份摘要独立的随机数,按此概率律抽取 。再以独立的新决策,从 的保留数组中均匀不放回选 条,从 的保留数组中选 条,返回并集及计数 。所有可行分配都放得进原有蓄水池,因为 ,且 。
为什么还不知道最终分配,工作节点就能先丢弃数据?关键是:均匀蓄水池的均匀子抽样,仍是原始分区的均匀子集。
引理 11.1.4
(均匀子抽样可以组合)
设 是某个 元集合的均匀 元子集,其中 。给定 后,从 中均匀选一个 元子集 。那么 是原始集合的均匀 元子集。
证明
(计算包含目标的蓄水池)
固定目标 元子集 ,恰有 个可能蓄水池包含它。给定其中任何一个,选出 的概率都是 。所以
这里用到恒等式 。采用 的惯例后,这个阶乘恒等式也涵盖 和 。
定理 11.1.5
(加权合并保留完整子集概率律)
对固定且互不重叠的分区,若容量 的局部蓄水池独立且均匀,分配及子抽样随机数亦独立,则上述合并输出是 的均匀 元子集,并返回正确计数 。
证明
(以分配为条件)
固定一个目标 元子集 ,记 。只有 时,合并才可能返回 。给定此分配,子抽样引理给出的两个目标部分概率分别是 与 。原始蓄水池独立,后续选择又使用新随机数,因此两事件独立。相乘得到
同一惯例亦涵盖 、 及 :对应的全集或空集都是唯一可能子集。计数可相加,是因为分区互不重叠。
证明透视
一个分配、两次引理、一次约去
唯一的关键一步是以 为条件:满足 的目标 只能来自分配 ,所以无需对多种情形求和。然后在两边分别使用子抽样引理:一边取 、,另一边取 、;这正是工作节点可以在分配确定前丢弃记录的理由。两个节点及合并新决策的独立性只用了一次,就是把两边概率相乘。证明能够闭合,是因为超几何分子恰好约去两个引理分母,所以其他分配律都不行。结论是对节点抽样取平均的:给定某份已实现摘要后,被丢弃的记录不能重新出现;两个节点重用同一种子,即使分区不重叠,也会破坏这次相乘。
合并树可逐层归纳使用定理。只要来源随机数独立,互不重叠子树的摘要便维持独立,所以任何固定合并树都返回正确均匀律。不同的树却未必返回同一个实现样本。正如先前的分布式归约一节,分区必须不重叠且恰好处理一次;重复或遗漏分区会改变抽样总体。只检查摘要长度,不能证明这些外部识别条件。
例题 11.1.6
(五条记录的精确合并)
取 、 及 。 的分配概率依次为
配对 的概率是 。当中的 同时涵盖第一个节点的三选二蓄水池,以及其后的二选一。配对 的概率是 ;配对 的概率也是 。三者代表三种分配类型;全部十种配对的概率都为十分之一。
例题 11.1.7
(低于容量的合并使分配确定)
取 、 及 。由于 、,每个局部蓄水池就是整个分区。此时 、,可行范围是 。唯一分配是 ,概率为 。两次子抽样都取走全部记录,合并返回三条记录及计数 ,正是并集唯一的 元子集。若改为 ,范围同样迫使 ,空摘要不贡献任何记录。
反例模式
摘要大小相同,不代表总体权重相同
令 , 只有一条 ,而 有九条各不相同的记录。两节点各返回一条。若从两份摘要均匀选一份,保留 的概率是 ,每条特定 区记录的概率则是 。可是每条原始记录的目标概率应为 。正确分配是以 选 摘要、以 选 摘要。容量更大时需要超几何分配;固定按比例配额,会排除均匀子集本应容许的某些分配。
使用有限随机字的完整实现
假设理想来源每次返回一个独立均匀的 比特字,且与所有输入及先前调用独立。此处 。对任意正整数上限 ,串接足够多个(记为 个)字,取得在 上均匀的整数 ,其中 。设 ;若 就拒绝重抽,否则返回 。每个余数恰有 个获接受的代表值。因此重复独立尝试后,每个余数的返回概率都是 。接受概率 ,故程序几乎必然终止,平均少于两次尝试;尝试次数却没有固定上限。
使用新的独立来源字,即使上限依赖过去决策,各次调用仍然条件均匀。特别是,数据流计数增加时,不必把精确整数决策改成浮点概率比较。
分配时,可想象罐中有 个 标签和 个 标签。以整数决策不放回抽 个标签,却不实际存储它们。含有 个 标签的某个特定类型序列,概率是 ,其中 ,且 。这样的类型序列共有 个。相乘化简,正好得到上述超几何公式。程序只须存储剩余计数。
以下完整 Python 程序以带种子的生成器实现可执行的随机字接口。其确定输出并不能证明理想独立性假设。示范中每次出现都有不同整数标签;摘要验证只检查计数与长度一致,而分区不重叠及使用新随机数仍由调用者确保。
import random
class FiniteWords:
def __init__(self, seed):
self.rng = random.Random(seed)
def below(self, bound):
if not isinstance(bound, int) or bound < 1:
raise ValueError("positive integer bound required")
if bound == 1:
return 0
words = ((bound - 1).bit_length() + 15) // 16
size = 1 << (16 * words)
limit = size - size % bound
while True:
candidate = 0
for _ in range(words):
candidate = (candidate << 16) | self.rng.getrandbits(16)
if candidate < limit:
return candidate % bound
def reservoir(items, capacity, source):
if not isinstance(capacity, int) or capacity < 0:
raise ValueError("nonnegative integer capacity required")
count, kept = 0, []
for item in items:
count += 1
if len(kept) < capacity:
kept.append(item)
elif capacity:
slot = source.below(count)
if slot < capacity:
kept[slot] = item
return count, kept
def subsample(items, take, source):
if not 0 <= take <= len(items):
raise ValueError("invalid subsample size")
pool = list(items)
for i in range(take):
j = i + source.below(len(pool) - i)
pool[i], pool[j] = pool[j], pool[i]
return pool[:take]
def merge(left, right, capacity, source):
if not isinstance(capacity, int) or capacity < 0:
raise ValueError("nonnegative integer capacity required")
for count, kept in (left, right):
if (not isinstance(count, int) or count < 0
or len(kept) != min(capacity, count)):
raise ValueError("summary count/length mismatch")
na, ra = left
nb, rb = right
total = na + nb
take = min(capacity, total)
remaining_a, remaining_total, allocated_a = na, total, 0
for _ in range(take):
if source.below(remaining_total) < remaining_a:
allocated_a += 1
remaining_a -= 1
remaining_total -= 1
kept = (subsample(ra, allocated_a, source)
+ subsample(rb, take - allocated_a, source))
return total, kept
left = reservoir(iter(range(3)), 2, FiniteWords(101))
right = reservoir(iter(range(3, 5)), 2, FiniteWords(202))
count, sample = merge(left, right, 2, FiniteWords(303))
assert count == 5 and len(sample) == 2 and len(set(sample)) == 2
assert set(sample) <= set(range(5))
assert reservoir(iter(range(2)), 5, FiniteWords(404)) == (2, [0, 1])
assert reservoir(iter(range(5)), 0, FiniteWords(505)) == (5, [])
assert merge((0, []), (0, []), 2, FiniteWords(606)) == (0, [])
print("merged", count, sorted(sample))
函数 subsample 的部分交换,使每个由不同条目组成的有序序列都具有 的概率;忽略顺序后,就是均匀 元子集。它只复制蓄水池,不会复制整个分区。分配循环最多执行 次,两个子抽样循环合计最多执行 次。
单次扫描最多保留 条记录及一个计数,亦即 个记录位置,再加上计数及暂存随机整数所需的 比特。对任意长度数据流,这不是固定比特的内存上限:精确计数随数据流增长,就需要更多存储空间。每个有限前缀仍只用有限内存,而且没有建立输入列表。此计算也假设保留记录的大小有界,或使用有界大小的引用;任意大记录内容需要另外的字节预算。
在精确整数抽取成本为常数的理想模型下,扫描有 次更新,合并两份摘要需要 工作及 个额外记录位置。使用此处的字来源时,在 以下抽取一个整数,平均需 个来源字;整数运算及复制大型记录另有成本。示范的不同种子标记可重现的不同数据流,但种子不同并不构成数学独立性的证明。
均匀子集对估计有什么作用
命题 11.1.8
(蓄水池平均的期望与方差)
对固定实数 ,设 、,并令 及 。若 是 的均匀 元子集,则蓄水池平均 无偏,其有限总体方差为
证明
(入选指标与成对入选)
记 。计算子集数目可得 ,而对不同索引,。期望的线性性给出无偏性。再设 ,则 ,且 。展开 ,得到
亦即所需方差。
成对入选概率正是完整抽样设计发挥作用的地方。当 ,方差为零;容量为零时,样本平均没有定义。若 ,则全部数据都保留;只要 ,把总和除以实际样本数 ,就得到精确平均。当 且容量为正,这个平均的方差也为零;上述使用 的公式则假设 。这些是固定有限总体下基于抽样设计的结论,并非对未知未来数据生成过程的置信保证。
例题 11.1.9
(核对有限总体修正)
对数值 和 ,三个等概率的配对平均是 。它们的平均为 ,方差为 。总体量为 ,所以 。若把保留的两个值当作独立抽取,就会漏掉不放回抽样带来的方差缩减。
练习与完整解答
快速检查
(容量为二,读完三条后的蓄水池是均匀配对。读入第四条后,得到配对 和 的概率各是多少?)
追踪先前配对,以及位置被替换的概率。
解答 · 答案
第一个配对要求先前配对为 ,概率 ,并且本次不替换,概率 ,故结果是 。若目标为 ,先前必须是 或 。每种先前配对的概率均为 ,而替换另一条所在的唯一位置,概率是 。相加得到 。推理依赖位置被替换的概率,而不依赖数组是否按数值排序。
快速检查
(两个工作节点及归约器均使用容量三,两个分区大小为四与二。求各分配概率,以及指定子集 的概率。)
从 、 开始。
解答 · 答案
此时 。可行的 区数量为 ,概率分别是 、 和 。指定子集要求分两个位置给 、一个给 。均匀子抽样给出 。即使分配稍后才决定,第一个节点容量三的蓄水池仍然足够。
快速检查
(容量为一。在 上均匀抽一次 ,并重用它设定 、。两个更新整数各自都在所需范围上均匀。求最终三条记录的入选概率,并指出哪项定理假设失效。)
列出 的六个值,逐一跟踪两次更新。
解答 · 答案
若 ,最后一次更新选位置零,保留第三条。若 ,第二次更新保留第二条,第三次不替换。若 ,两次更新都不替换第一条。因此第一、二、三条的最终概率依次是 。这些决策共用 ,给定先前历史后并不条件均匀。正确的一维边际分布,不能支持归纳中相乘的步骤。
快速检查
(为什么蓄水池最多一百条记录,仍不能证明任意长度数据流有固定的字节内存上限?能否在合并树中加入同一摘要两次?)
考虑计数本身,以及合并定理的假设。
解答 · 答案
精确计数 需要约 比特,而保留记录的字节大小也可能不同。除非另行限制整数范围和记录大小,否则界限只是记录位置数。把同一摘要放入两次,会同时破坏不重叠性与独立性:记录被重复计入,两份副本也共用抽样决策。合并定理因此不再描述原本只应计算一次的总体的均匀样本。