样本能回答什么问题?
数据流可能大得无法全部保存和排序,但读者仍希望知道有多少观测值不超过某阈值,或希望求中位数。前一节的蓄水池算法无需预先知道数据流长度,便可在一次扫描后均匀抽取若干笔记录。现在我们用样本近似秩次。
定义 13.1.1
(经验分布及其蓄水池估计)
先固定非空的有限实数序列 ,再进行抽样。不同位置即使数值相同,也是不同的记录。设 是从 个位置均匀选出的 元子集,。经验分布及其蓄水池估计为
两个函数均采用“不超过”;左极限则计算严格小于阈值的比例。将 乘以 得秩次计数,故比例误差 对应最多 的计数误差,却不保证数值之间的距离很小。
标准容量 的蓄水池,在固定的最终长度 处有上述子集分布,条件是每个位置 均在给定此前历史下,从 均匀抽取整数;若该数不超过 ,便替换对应的槽位。完整输入及最终长度必须独立于抽样随机性而固定。若输入本身随机,但与抽样器独立,以下结论可在给定输入后成立。依据蓄水池内容改变未来输入或决定何时停止,均不在此论证范围内。
一个阈值:有限总体方差
命题 13.1.2
(单一阈值的均值与方差)
对固定阈值 及均匀 元子集 ,当 ,
把 换成 ,同一公式适用于 落在任何固定的 个位置之内的比例。
证明
(均匀子集的指示变量矩)
令 是成功次数。记 ,直接计算包含指定位置的子集数目,可得
以下计算对任何固定的 个位置组成的子集均成立,不限于阈值集合。把 个成功位置的指示变量相加,得 ,所以 的均值为 ,而
除以 即得所列方差;再由 及 得上界。
这是不放回抽样;样本中的指示变量并不独立。因子 反映不会重复抽到同一位置的好处。 时答案精确; 时也是精确的,不必使用上式。切比雪夫(Chebyshev)不等式因而给出:固定阈值的误差超过 的概率不大于 。但只控制固定阈值,不能直接容许看过样本后再挑选阈值。
常见错误
(对蓄水池使用二项方差)
把保留的 笔当作独立抽样,会得到方差 ,漏去因子 。两者可以相差很远: 时蓄水池保存整个列表, 精确成立,二项公式却仍给出正方差。这里二项值是上界,用于保证是安全的,但作为精确方差则是错的。
同一事件控制所有阈值
以下不用假设样本项目独立,也不用引用更强的摘要算法定理,就能证明保守的同时界。给定 ,令
并使用容量 的蓄水池;若 则保存全部 笔。
定理 13.1.3
(有限序列上的同时秩次保证)
对每个固定的非空有限序列,按上述独立条件抽样,均有
概率来自蓄水池的建立过程。同一事件保护所有实数阈值,包括看过蓄水池后才选出的阈值。
证明
(前缀网格与联合界)
若 ,全部位置都被保留,误差为零。否则 。由 得 。按数值排序所有位置,数值相同时按原位置打破并列。对每个前缀长度 ,令 ,并令 为蓄水池中属于此前缀的比例。每个前缀都是固定的总体子集,故即使前缀切开一组相同数值,上述方差界仍适用。
令 ,标记 中不超过 的前缀长度,必要时再加上 。由 及 时 ,有 及 。故 ,连同两端共有 个标记;相邻标记相距至多 。
对每个固定标记,用切比雪夫不等式取偏差 ,其失败概率至多 。联合界不需要各标记的误差独立,故任何标记失败的概率至多
在其余的事件上,任取相邻标记 之间的前缀。由 单调递增,
同理 。每个阈值都对应包含所有不超过该阈值数值的前缀,因此同一事件控制所有阈值,包括数值之间的间隙及相同数值处。
证明透视
有限个固定事件,然后用单调性
证明有三步。第一,把不可数多、且可能在抽样后才选的阈值,换成位置固定次序下的前缀。按位置打破并列,使每个前缀都是固定集合,因此即使前缀切开一组相同数值,单一阈值的命题仍适用;而每个阈值都是其中一个前缀,故没有遗漏。第二,只直接控制网格上的 个前缀,每个用偏差 的切比雪夫不等式,联合界把失败概率相加而无需任何独立性; 必须大到 ,正是因为这一步。第三, 与 的单调性把网格点上的界传到其间每个前缀,代价是网格间距,即另一个 。 的情形要分开处理,因为此时蓄水池保存全部;保证 的不等式 只因 才成立。本界故意采用初等方法,较为保守;它不是对 KLL 或 Greenwald–Khanna 摘要的空间复杂度或失败率的断言。
例题 13.1.4
(十万个数值的网格)
取 、,则 、(见下文计算),并设 。于是 ,标记为 ,共 个,而 本身已是标记。前缀 位于 与 之间。若蓄水池在两个标记上的比例分别与 及 相差不超过 ,则 ,且 ,两者都在 之内。
上述容量为 个记录位置;若容量大于列表长度,保存全部数据便精确。抽样器亦需精确计数,占 比特,并须存储随机状态。记录本身的字节数需要另行预算。这是充分界,并非所需样本数的下界,也不声称是最锐利的置信界。
例题 13.1.5
(确定蓄水池容量,以及何时保存全部)
取 、,则 ,而
对 个数值的列表,蓄水池保留 个位置,并以至少 的概率使每个秩次比例误差不超过 。对 的列表,,规则保存整个列表,每个秩次均精确。这个边缘情形并非方法失效,只是保守容量比数据还大。
由秩次到分位数
给定 ,将 个样本值排序,返回第 个值 。按构造, 且 。同时界亦控制左极限:可从低于 的阈值取极限,或考虑相等值整组之前的前缀。因此
这表示总体中 所占的秩次区间,距离 不超过 :若 在区间以外,离它较近的端点与 的距离不超过 。但它不表示 :若许多数值等于 ,右端点可以远远跳过 。由于成功事件控制所有阈值,即使看过样本后才选 ,同一事件仍适用。它也不保证数值误差小:相邻的总体数值可以相距任意远。
例题 13.1.6
(含相同数值的样本与总体秩次)
设固定总体为 ,容量四的蓄水池恰好包含 。这是位置均匀抽样的一种可能结果;两个 3 来自不同位置。若 ,第二个样本值为 。此时 ,,而 ,。在阈值 6,估计为 ,真实比例为 。这只是一次样本的算术,不证明四笔记录符合定理的置信要求。
反例模式
返回的分位数其秩次未必接近所求水平
断言:在成功事件上 。设总体所有数值都是 7,取 。每个非空蓄水池都返回自然的中位数 ,即使保存全部总体也是如此,所以抽样误差为零。可是 ,,大于每个 。断言失败,因为一组相同数值占据整段秩次区间。正确的是上面的区间形式: 包含 ,与 及 一致。
区间形式只涉及秩次;关于数值另有一个警告。
常见错误
(秩次准确不等于数值准确)
总体有 50 个零和 50 个 ,容量 99 的样本恰好漏掉一个零。总体的下中位数为 0,样本中位数,即 99 个排序值中的第 50 个,却是 。最大秩次比例误差只有 ,数值误差 却可以任意大。
练习与解答
快速检查
(100 个数值中有 30 个不超过 ;均匀蓄水池有 10 笔。求估计比例的期望及方差。)
解答 · 答案
期望为 ;方差为 。样本观测并不独立,没有有限总体修正的二项方差 并非精确值。
快速检查
(取 、。计算充分容量;若 ,会怎样?)
解答 · 答案
,。因 ,保存全部 100 个位置,每个秩次均精确。充分的最坏情形界未必对此列表划算。
快速检查
(总体为 ,样本为 。求 时的返回值及其总体秩次区间。是否必有 ?)
解答 · 答案
第一个样本值为 。其总体秩次区间 包含 ,但右端点为 ,不是 :数值阈值不能切开并列值。
快速检查
(研究者看过蓄水池后才选阈值。为什么不能直接使用固定阈值的切比雪夫估计?哪个结果可处理此选择?)
解答 · 答案
由随机样本选出的阈值不是固定事件,不能直接套用单一阈值的计算。上面的定理先构造对所有阈值同时成立的高概率事件,因此选出的阈值也受保护,前提仍是原始序列和最终长度满足独立条件。
本节涵盖保守的蓄水池同时秩次界及考虑并列值的分位数解释;紧凑的确定性秩次摘要、更锐利的集中界、可合并分位数摘要和自适应数据流仍未涵盖。