淺談集齊卡片問(wèn)題

(郵編：230026)

中國(guó)科學(xué)技術(shù)大學(xué)

1 問(wèn)題由來(lái)

看到近來(lái)群里在討論如下的概率問(wèn)題,

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

這個(gè)問(wèn)題提得挺有趣,設(shè)問(wèn)也看似合理,但是,要解答它卻非易事.這是一類等待勝利問(wèn)題,而且是帶有參數(shù)變化的等待問(wèn)題,已經(jīng)遠(yuǎn)遠(yuǎn)超出中學(xué)數(shù)學(xué)中關(guān)于概率論的知識(shí)范圍.

但是,如果把問(wèn)題稍加改變,不求分布列,直接求平均次數(shù),則不但可以解答,而且可以豐富中學(xué)概率知識(shí):

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

這就是說(shuō),我們可以繞過(guò)隨機(jī)變量的分布律,直接求它們的數(shù)學(xué)期望.

2 從幾何分布談起

我們先來(lái)考察如下問(wèn)題:

例3 一次接一次地向一個(gè)目標(biāo)射擊,各次射擊獨(dú)立進(jìn)行,每一次射擊的命中率都是p，0

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

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

由于這個(gè)分布列是一個(gè)等比數(shù)列,所以人們形象地把這種分布稱為幾何分布,因?yàn)榈缺葦?shù)列也叫做幾何級(jí)數(shù).

對(duì)于服從幾何分布的隨機(jī)變量X,它的數(shù)學(xué)期望是

這是一個(gè)無(wú)窮級(jí)數(shù),為求出它的值,需要用到它的絕對(duì)收斂性,逐項(xiàng)可積性以及逐項(xiàng)可微性.

我們知道

對(duì)一切0

這種求期望的方法對(duì)大學(xué)本科生而言, 不難接受, 卻遠(yuǎn)遠(yuǎn)超出中學(xué)數(shù)學(xué)的知識(shí)范圍. 所以我們來(lái)?yè)Q一個(gè)角度討論它.

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

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

解得

①

3 集齊M張卡片所需的平均選擇次數(shù)

現(xiàn)在我們回過(guò)頭來(lái)看例2.

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

現(xiàn)在, 我們的等待勝利的總次數(shù)就是

X=1+X2+…+XM.

而根據(jù)①式, 有

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

②

下面給出最終勝利的平均等候次數(shù)的又一個(gè)例子.幾天前, 有人問(wèn)過(guò)我如下的一個(gè)問(wèn)題:

例4 一次接一次地拋擲一枚質(zhì)地均勻的骰子,各次拋擲獨(dú)立進(jìn)行, 直到六個(gè)面都出現(xiàn)為止. 試求所需的平均拋擲次數(shù).

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

4 求出X的分布律顯得相對(duì)困難

前面說(shuō)到, 我們的等待勝利的總次數(shù)就是X=X1+X2+…+M.這是M-1個(gè)獨(dú)立不同分布的隨機(jī)變量的和, 要求出它的分布并非不可能, 但確實(shí)是一個(gè)復(fù)雜的表達(dá)式:對(duì)正整數(shù)n≥M, 有

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

也可以簡(jiǎn)化為

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

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