淺談集齊卡片問題

2019-09-05 01:39:58郵編230026

(郵編：230026)

中國科學技術大學

1 問題由來

看到近來群里在討論如下的概率問題,

例1 有M種卡片,每種卡片數量無限,每次隨機從M種卡片中選擇一張,選擇到每種卡片的概率相同.現在需要集齊M種卡片,即每種卡片至少需要一張,集齊之后則終止.問:選擇n次(n≥M),能夠集齊M張卡片的概率是多少?

這個問題提得挺有趣,設問也看似合理,但是,要解答它卻非易事.這是一類等待勝利問題,而且是帶有參數變化的等待問題,已經遠遠超出中學數學中關于概率論的知識范圍.

但是,如果把問題稍加改變,不求分布列,直接求平均次數,則不但可以解答,而且可以豐富中學概率知識:

例2 有M種卡片,每種卡片數量無限,每次隨機從M種卡片中選擇一張,選擇到每種卡片的概率相同.現在需要集齊M種卡片,即每種卡片至少需要一張,集齊之后則終止.試求能夠集齊M張卡片所需的平均選擇次數.

這就是說,我們可以繞過隨機變量的分布律,直接求它們的數學期望.

我們先來考察如下問題:

例3 一次接一次地向一個目標射擊,各次射擊獨立進行,每一次射擊的命中率都是p，0

這就是一種等待首次勝利的問題.X就是等來勝利所需的射擊次數.可以相見,X的取值集合是全體正整數,而且對任一正整數n,事件(X=n)表示前n-1次都未擊中目標,但是在第n次射擊命中了,我們記q=1-p,由于各次射擊相互獨立進行,所以

P(X=n)=qn-1p,n=1,2,…

由于這個分布列是一個等比數列,所以人們形象地把這種分布稱為幾何分布,因為等比數列也叫做幾何級數.

對于服從幾何分布的隨機變量X,它的數學期望是

這是一個無窮級數,為求出它的值,需要用到它的絕對收斂性,逐項可積性以及逐項可微性.

我們知道

對一切0

這種求期望的方法對大學本科生而言, 不難接受, 卻遠遠超出中學數學的知識范圍. 所以我們來換一個角度討論它.

如果第一次射擊就命中了目標, 那么顯然等待次數就是1, 發生這個事件的概率是p, 如果第一次射擊沒有命中目標,那么第一次的努力白費, 我們還要從頭開始等候, 所以等待的總次數與1+X同分布, 發生這個事件的概率是q=1-p.如此想來, 我們的數學期望就是

EX=p+q(1+EX)=1+qEX，

解得

①

現在我們回過頭來看例2.

以X表示集齊M張卡片所需的選擇次數, 我們要求EX.

現在, 我們的等待勝利的總次數就是

X=1+X2+…+XM.

而根據①式, 有

所以集齊M張卡片所需的平均選擇次數是

②

下面給出最終勝利的平均等候次數的又一個例子.幾天前, 有人問過我如下的一個問題:

例4 一次接一次地拋擲一枚質地均勻的骰子,各次拋擲獨立進行, 直到六個面都出現為止. 試求所需的平均拋擲次數.

這就是例2中M=6的情況.以X表示所需的拋擲次數, 根據(2)式,即得

前面說到, 我們的等待勝利的總次數就是X=X1+X2+…+M.這是M-1個獨立不同分布的隨機變量的和, 要求出它的分布并非不可能, 但確實是一個復雜的表達式:對正整數n≥M, 有

其中∑是對滿足n1+n2+…+nM-1=n-M的一切非負整數組(n1,n2,…,nM-1)求和.

也可以簡化為

其中∑是對滿足n1+n2+…+nM-1=n-M的一切正整數組(n1,n2,…,nM-1)求和.

不知道是否可以得到一個簡潔的表達式? 而且對于我們來說, 平均等待次數更為重要. 既然有辦法直接求出平均次數, 那就不需要再去硬鉆牛角尖了. 在討論概率問題時,更需注意問題的深淺, 不是所有問題都能解決的, 更不是所有問題都是要硬碰硬解決的.