要多久才能見到每一種?
設想隨機測試獨立地抽取 個情況之一,問題是要抽多少次,才能使每個情況至少被抽到一次。只有抽樣模型正確時,答案才描述該測試的覆蓋情況。
定義 8.1.1
(集齊時間與等待時間)
假設每次獨立抽取都等概率地返回 種類中的一種,有放回,每次概率相同。集齊時間 是見到所有 種類所需的抽取次數。對 ,在已出現 種不同種類之後,令 為等到下一種新種類的額外抽取次數,包括成功的那一次。於是 ,且 。
定理 8.1.2
(期望集齊時間)
在上述模型下,,其中 。
證明
(幾何等待時間)
見過 種之後,下一次抽到新種類的概率為 。在第 種不同種類出現時的歷史條件下,之後的抽取仍是獨立而均勻的,所以 服從成功率為 的幾何分佈,期望為 。因此
第一個等式把每次抽取恰好算進一個等待階段。期望的線性性不要求各等待時間互相獨立;每個成功率都大於零,所以各期望有限。
證明透視
為甚麼每個等待時間只取決於一個數量
這個分解在每次出現新種類的時刻把整個過程切開,所以每次抽取恰好屬於一個 。不尋常的一點是:在第 個新種類出現之後,再抽到新種類的機會 只取決於已見過多少種,而不取決於是哪幾種。這正是用到等概率的地方,也是每個 為幾何分佈的原因。各次抽取獨立,使每個切點之後都是重新開始。於是期望的線性性把各平均值相加,無須對 之間的相依性作任何斷言;每個成功率至少為 ,所以有限性是自動的。
平均值不是期限
單憑平均值不能說到那個時刻一定集齊。我們可以為等待過久的概率給出上界。
定理 8.1.3
(集齊時間的尾部界)
對每個整數 ,
因此,給定 ,每個整數 都保證 。
證明
(對缺少種類取聯集界)
某一指定種類在 次抽取後仍缺少的概率為 。若 ,則至少缺少一種,對 種使用聯集界即得第一個不等式;第二個不等式來自 。至於後半部分, 給出 。
不同種類缺少的事件可以重疊,所以上界可能偏鬆;證明並沒有假設這些事件獨立。這個結果是高概率的充分界,不是每次運行都成功的保證,並且仍依賴上述理想的獨立均勻抽樣模型。 時聯集界大於一,雖然無害,卻沒有資訊。
例題詳解
例題 8.1.4
(兩種類)
當 ,第一次抽取必定見到一種。之後每次抽到缺少種類的概率為 ,所以平均次數是 。兩次抽取可以集齊,但並非總是如此:,因為第二次必須與第一次不同。
例題 8.1.5
(三種類)
當 ,各等待時間的平均值為 、 和 ,所以 。事件 要求三次抽取各不相同; 個等可能序列中有 個符合,所以 。
例題 8.1.6
(十種類所需的抽取次數)
對 及失敗概率至多為 ,取 。此時該界給出 。這是充分的抽取次數,不一定是最小的可行整數。
例題 8.1.7
(兩種類的精確尾部概率)
當 、 時,失敗概率為 :三次抽取必須全部為同一種類。此例中聯集界恰好等於真值,因為在非空的抽取序列之後,兩個缺少事件不可能同時發生。
假設為何重要?
若某種類的概率為零,便永遠無法集齊。若各類概率 不相等但都為正,而抽取仍獨立,指定種類缺少的概率為 ,有效的聯集界是 。但等待新種類的概率取決於已見過哪一些,而非僅取決於數量,所以均勻公式 未必成立。若抽取之間有相關性,連上述缺少概率的乘積形式也可能失效。
反例模式
概率不相等會改變平均值
一個誘人的說法是:無論各種類的概率如何,都有 。取 ,兩種類的概率為 和 。若第一次抽到的是常見種類,其概率為 ,缺少的便是罕見種類,平均還要再抽 次。若第一次抽到的是罕見種類,缺少的便是常見種類,平均還要再抽 次。因此
失效的一步是:下一次抽取的成功概率現在取決於已見過哪些種類,而不只是見過多少種。等概率正是使 恢復成立的假設。
常見錯誤
常見錯誤
(把平均值當作期限)
當 ,平均值為 ,但 。事實上,對每個 都有 ,所以不存在一個必定足夠的有限抽取次數。平均值說明分佈的中心在哪裏,並沒有說明它在哪裏終止。
常見錯誤
(把聯集界當作精確概率)
當 、,聯集界給出 ,但精確值是 。三個缺少事件互相重疊:三次抽取全相同的序列會使兩個種類同時缺少,聯集界把它計算了兩次。
練習
快速檢查
(當 ,求 與 。)
用前兩次抽取描述事件 。
解答 · 答案
第二次與第一次不同的概率為 ,故 。事件 表示三次抽取全相同,概率為 。
快速檢查
(當 ,求 。)
數一數三次抽取見到三個不同種類的序列。
解答 · 答案
三次抽取必須各不相同。 個等可能序列中有 個符合,故概率為 。
快速檢查
(對 及失敗概率至多為 ,上述界給出多少次抽取足夠?)
使用 並向上取整。
解答 · 答案
取 。這是充分界,不一定是最小的整數。
快速檢查
(為何 不需要缺少事件獨立?)
這是哪一個一般的不等式?
解答 · 答案
這是聯集界,對任意事件都成立。抽取的獨立性是另外用來計算各個缺少概率的。