樣本能回答甚麼問題?
數據串流可能大得無法全部保存和排序,但讀者仍希望知道有多少觀測值不超過某門檻,或希望求中位數。前一節的蓄水池算法毋須預先知道串流長度,便可在一次掃描後均勻抽取若干筆記錄。現在我們用樣本近似秩次。
定義 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 個位置,每個秩次均精確。充分的最壞情況界未必對此列表划算。
快速檢查
(母體為 ,樣本為 。求 時的返回值及其母體秩次區間。是否必有 ?)
解答 · 答案
第一個樣本值為 。其母體秩次區間 包含 ,但右端點為 ,不是 :數值門檻不能切開平手。
快速檢查
(研究者看過蓄水池後才選門檻。為何不能直接使用固定門檻的切比雪夫估計?哪個結果可處理此選擇?)
解答 · 答案
由隨機樣本選出的門檻不是固定事件,不能直接套用單一門檻的計算。上面的定理先構造對所有門檻同時成立的高概率事件,因此選出的門檻也受保護,前提仍是原始序列和最終長度符合獨立條件。
本節涵蓋保守的蓄水池同時秩次界及顧及平手的分位數解釋;緊湊的確定性秩次摘要、更銳利的集中界、可合併分位數摘要和自適應串流仍未涵蓋。