同一個實驗,不同問題
假設獨立抽選的 個人各有 種可能的生日,而且每種生日同樣可能。我們忽略閏日和季節差異;這是一個模型,並非聲稱真實生日符合這些假設。我們可以問有沒有兩人生日相同、出現了多少個不同生日,或要抽多少人才見齊所有生日。這些問題由同一個機制出發,但研究的是不同隨機變量。
更一般地,設 獨立且均勻分佈於 ,其中 是正整數。前 次抽取構成一個有序序列; 個序列各有概率 。令 為前 次出現的不同類別數, 為首次見齊 個類別時的抽取次數。類別可以重複;計算基本序列時次序重要,但 本身不記錄次序。
第一次碰撞
定理 31.1.1
(沒有重複類別)
當 ,
當 時,此概率為零。 時空乘積為一。至少一次碰撞的概率是上述概率的補事件概率。
證明
(按次序計數或逐步條件化)
第一次有 個選擇;若第二次與第一次不同,則有 個選擇,如此類推。相乘得到無重複的有序序列數,除以等可能序列總數 即得公式。也可以逐步看:已有 個不同類別時,下次避開它們的概率是 。若 ,鴿巢原理保證必有碰撞。
求補事件特別方便,因為碰撞可以多種重疊方式發生:一對可能相同,幾對也可能同時相同。直接相加各對相同的概率,會重複計算有多對相同的結果。當 相對 很小時,利用小 下的近似 ,無碰撞概率的對數約為 。這是近似而非恆等式;它解釋為何當 約為 的量級時,碰撞機會已可能不小,遠早於 達到 。
例題 31.1.2
(二十三人與三百六十五日)
取 、。把 個因子 ()相乘,得
所以至少有一對生日相同的概率約為 。近似式給出 ;由於 相對 很小,它與精確值相當接近。在這個模型中, 人已令碰撞概率超過一半,雖然 遠小於 。
出現了多少個類別?
若類別 在前 次出現,令 ,否則為零。於是 ;按定義 。
定理 31.1.3
(已佔類別數的期望與方差)
當 ,令 ,並在 時令 。則
若 ,對 有 ,方差為零。
證明
(指示變量及其協方差)
類別 在全部 次獨立抽取中都缺席的概率為 ,故 。期望的線性性不需要這些指示變量獨立,對 求和即得 。
當 且 不同,兩類同時缺席的概率為 。由容斥原理,,因此 。把總和的方差展開為 個方差 與 個協方差,即得公式。
協方差項不可省略:這些指示變量共用固定次數的抽取。由於 推出 ,此處協方差非正。
例題 31.1.4
(從三個類別抽取三次)
共有 個等可能序列。三類都出現的序列有 個,故 。只有一類出現的序列有三個,所以 ;餘下概率為 。因此
所以 。期望公式也給出 。
反例模式
邊際概率相等並不足夠
改設 ,兩者都是同一個從 均勻抽取的結果,。每次抽取單獨看都是均勻的,但兩次並不獨立。碰撞概率為一,而非 ;且 幾乎必然成立。先前公式同時需要獨立性和均勻性。
等到集齊所有類別
定義 為首次滿足 的 。已收集 個不同類別後,由抽取的獨立性,下次得到新類別的概率是 。令 計算從這時起直到首次得到新類別的抽取次數,包括成功那次。給定這時以前的歷史, 服從成功概率 的幾何分佈,因此其條件期望和無條件期望都是 。最終幾乎必然集齊:任何指定類別在 次後仍缺席的概率為 ,而類別只有有限個。
定理 31.1.5
(集券問題的期望)
在獨立均勻模型下,
證明
(分開各個等待階段)
各等待階段恰好把直到最後一個新類別出現為止的抽取分段,故 逐樣本路徑成立。取值於 、成功概率為 的幾何隨機變量的期望是 ,故 。由線性性,
最後一步代入 。
證明透視
為甚麼最後幾個類別佔去大部分時間
關鍵一步是量度由一個新類別到下一個新類別的時間,而不是追蹤整個已收集類別的集合。在第 階段只有一個數值要緊,就是仍然缺少的類別比例 ;獨立均勻的抽取令這個階段不論之前發生甚麼都是幾何等待。這是唯一用到模型假設的地方。
之後由線性性完成論證;各 在這裏確實獨立,但計算期望不需要這一點。調和和顯示時間花在哪裏:前一半類別平均每個至多需要 次抽取,而單是最後一個缺少的類別就需要 次。這就是總期望在 時大於 ,並以 的量級增長的原因。
當 ,三個階段的平均等待分別是 、、,因此 。這並不是說必定在第 或第 次集齊: 是隨機的,而且可以任意大。
例題 31.1.6
(集齊骰子的六個點數)
對公平骰子,,各階段的平均等待為 。其和為
單是最後一個階段就佔 ,最後兩個階段共佔 ,超過總數的一半。退化情況 與公式一致:,而事實上 ,因為第一次抽取已出現唯一的類別。
常見錯誤
常見錯誤
(把各對相同的概率相加)
人、 日時共有 對,每對相同的概率為 。它們的和 是相同生日對數的期望,而不是碰撞概率;碰撞概率約為 。這個和會把有多對相同的結果重複計算。它是碰撞概率的上界,而補事件公式給出精確值。
常見錯誤
(把佔據指示變量當作獨立)
當 ,若假設獨立,會得 。協方差項 並不可忽略;正確的方差是 ,約為前者的一半。
練習與解答
快速檢查
(從五個類別獨立均勻抽取四次。求出現碰撞的概率,以及不同類別數的期望。)
使用無碰撞的乘積及 的公式。
解答 · 答案
無碰撞概率為 ,故碰撞概率為 。期望類別數為 。
快速檢查
(設 。求第一個類別出現後,還需要的額外抽取次數的分佈及期望。)
之後每次抽取以概率 得到另一類別。
解答 · 答案
之後每次抽取都獨立地以概率 得到另一類別。對 ,等待恰為 次的概率是 ,期望為 。第一次抽取已經發生,不計入此等待,所以 。
快速檢查
(一位同學認為第二次抽到新類別的概率是 ,於是算出 。指出錯誤並給出正確值。)
想一想第一次抽取貢獻甚麼。
解答 · 答案
第一次抽取必然貢獻一個新類別,而不是以概率 。第二次以概率 貢獻新類別,故 。指示變量公式給出同樣結果:。