假設小浣熊隨機贈送的卡片共有 100 種（出現概率相同），那麼集齊所有卡片所需購買小浣熊包數的數學期望是多少？

12-03

相關問題選擇 n 次 (n ≥ M)，能集齊 M 種卡片的概率是多大？

這個是一個比較經典的數學題，叫做Coupon Collector『s Problem，公式太長，有興趣直接看這裡Coupon collector"s problem。最後計算結果應該是519.

首先考慮從擁有0種到擁有任意1種卡片需要抽取的卡片數量的期望，易知E0=1=100/100。
接下來
考慮從擁有1種卡片到擁有任意2種卡片需要抽取的卡片
數量的
期望，此時每抽取一張卡片，有99%的概率完成此事件，因此期望E1=100/99。
同理，可知En=100/n。
因此，要完成收集全部卡片所需卡片數量的期望是：
$E(x)=frac{100}{100} +frac{100}{99}+ldots+frac{100}{1}approx 519$

目前排名第二的匿名用戶的公式 $Eleft( T ight) =frac{100}{100} +frac{100}{99} +frac{100}{98} + frac{100}{97} +...+frac{100}{1} approx 519$ 是對的，但是論證過程有些匪夷所思。下面給出高中數學版本的論證：

一共有100種不同種類的小浣熊卡，你獲取第一種需要花費一包速食麵的錢，因此你獲得第一種浣熊卡所要購買的速食麵的數量的期望E（1）=1 。這是上面那個公式的 $frac{100}{100}$ 這個項的來源。

二現在你有一張卡片了，你繼續掏出人民幣給小浣熊公司買速食麵，那麼你為了獲得第二種浣熊卡需要繼續購買的速食麵的數量的期望
$E(2)=1 imes P(1) +2 imes P(2)+3 imes P(3) +...$
這裡，P（1）=0.99 ，因為你有0.01的概率抽到你已經擁有的那種卡片，所以你只有0.99的概率「再購買一包就獲得了第二種卡片」；而「你再購買兩包才獲得第二種卡片」的概率P（2）=0.01 $imes$ 0.99；「你購買三包才獲得第二種卡片」的概率P（3）=0.01 $imes$ 0.01 $imes$ 0.99；依次類推……
所以上式可以化為
$E(2)=1 imes0.99+2 imes0.01 imes0.99 +3 imes0.01 imes0.01 imes0.99...$

$=0.99 imes left[ 1+2 imes 10^{-2} +3 imes 10^{-4}+4 imes 10^{-6}... ight]$
這中括弧裡面是一個差比數列，高一的數學期末考試會經常碰到這種數列的求和問題，很容易可以求出這個差比數列的和是 $frac{100^{2} }{99^{2}}$ ，所以上式的結果為：

$E(2)=0.99 imes frac{100^{2} }{99^{2}} =frac{100 }{99}$
這就是總式中第二項的來源

三當你擁有兩種卡片時，你為了獲取第三種浣熊卡需要繼續購買的速食麵的數量的期望
$E(3)=1 imes P(1) +2 imes P(2)+3 imes P(3) +...$
$= 1 imes0.98+2 imes0.02 imes0.98 +3 imes0.02 imes0.02 imes0.98...$
$=0.98 imes frac{100^{2} }{98^{2}} =frac{100 }{98}$
剩下的以此類推。

如果有人想知道差比數列求和問題，也就是 $left[ 1+2 imes 10^{-2} +3 imes 10^{-4}+4 imes 10^{-6}... ight]$ 為什麼等於 $frac{100^{2} }{99^{2}}$ ，請留言。

你得到的下一張卡，與手中的卡不重複的幾率是（100-n）/100，n=你已經擁有的卡，那麼相應的得到這張與你手中的卡均不重複的卡，你需要買 1/{(100-n)/100} 包乾脆面,也就是概率的倒數。所以你總共要買1/1+1/0.99+1/0.98+……+1/0.01=518.73包乾脆面。取整519包。不怕吃到膩嘛。

n張卡片遍歷，相當於有放回取球要求全部取過。已經取過i個球，下次拿到新球的概率是（n-i）/n。
總期望是：E(X)=n*sum(i=1:n)(1/i).
當n=100時：
x=0;
for i=1:100
x=x+1/i;
end
答案是518.74

另外放出matlab模擬程序：
for j=1:10
n=100;
A=zeros(1,n);T=0;S=0;
for i=1:100
while sum(A,2)&<(n+1).*n/2
x=randint(1,1,[1,n]);
A(1,x)=x;
T=T+1;
end
A=zeros(1,n);
end
disp([num2str(n)," pieces need ",num2str(T/100)," bags"])
end

結果：
100 pieces need 536.9 bags
100 pieces need 509.06 bags
100 pieces need 520.98 bags
100 pieces need 523.43 bags
100 pieces need 520.87 bags
100 pieces need 534.84 bags
100 pieces need 543.73 bags
100 pieces need 517.98 bags
100 pieces need 542.51 bags
100 pieces need 538.44 bags

設買 $X$ 包（ $Xgeq 100$ ）小浣熊時，恰好集齊100種卡片。
即前 $(X-1)$ 包中包含99種卡片，第 $X$ 包恰好是最後一張卡片。

$X$ 可看作一個隨機變數，其取值範圍是100到無窮大之間的正整數。
因此，可通過如下公式求得 $X$ 的數學期望：
$E(X)=sum_{k=100}^{+infty }{kcdot P(X=k)}$

其中 $P(X=k)$ 是第 $k$ 包恰好買到的概率。

我們有：
$P(X=k)=frac{1}{100} P(Y)$ ，這裡 $P(Y)$ 表示剩餘99張分布在前 $k-1$ 包中的概率。由於剩下的一包有100種可能，而只有恰好抽到剩下的一張卡才行，所以要 $P(Y)$ 除以100才能算出 $P(X=k)$ 。

計算 $P(Y)$ 的分子。實際上問題等價於，將 $k-1$ 包小浣熊分成99類，每類的個數不能小於1，問分法有多少種。即求如下不定方程的正整數解的個數：
$x_{1}+x_{2}+...x_{99}=k-1$

根據不定方程原理，該方程正整數解的個數應該為 $C_{99-1}^{k-1+99-1}$ ，即：
$frac{(k+97)!}{98!(k-1)!}$

而 $P(Y)$ 的分母應為 $99^{k-1}$ ，因此有：
$P(Y)=frac{(k+97)!}{99^{k-1} cdot98!(k-1)!}$

綜上，得：
$E(X)=sum_{k=100}^{+infty }{frac{kcdot (k+97)!}{100cdot 98!(k-1)! cdot 99^{k-1}}}$

然後不知道怎麼算最終結果了。編程也解不出來，因為階乘的結果超出計算範圍了。

贊樓上幾個匿名用戶的簡潔而正確的答案。

優惠券收集問題，請參見莫特萬尼的《random algorithm》一書的「隨機遊走與優惠券收集" 那一章的例題。答案是 n(Hn) Hn 是調和技術的前n項和。

獲得第一種的概率是1，故只需要1/1=1次；
獲得第2種的概率是0.99,需要1/0.99次；
獲得第3種的概率是0.98,需要1/0.98次；
獲得第4種的概率是0.97,需要1/0.97次；
...
獲得第100種的概率是0.01，需要的概率是1/0.01次。

這個問題仔細一想還是比較複雜的，所以先從簡單的情形開始入手吧

讓我們先來設想一種最簡單的情形：擲一枚硬幣，平均投擲多少次可以第一次得到正面？

還記得離散型數學期望的定義嗎，所有可能的結果與它們所對應的概率的乘積之和:

$E=sum_{i=1}^{n}{x_{i} p_{i} }$ 那麼，一次投擲有二分之一的概率得到正面，投擲兩次時一定是一反一正的情況，那麼概率是四分之一......以此類推： $E=1 imes frac{1}{2} +2 imes frac{1}{2^{2} } +3 imes frac{1}{2^{3} } +...+n imes frac{1}{2^{n} }$

這是一個等差數列與等比數列相乘的數列，用交錯相減可以求得E=2，就是說平均仍兩次硬幣就可以得到正面了，既進行10000次試驗求得的次數平均值也是接近於2的。也許有人會說，扔一次得到正面的概率本來就是二分之一，所以仍兩次不就行了？這就是說，期望的次數是單次獲得概率的倒數，那這個結論究竟成不成立？別著急，我們需要驗證它。

假設一個情景，n張不同的卡片，一次隨機抽取一張（有放回），平均需要多少次可以獲得特定的某一張？這樣，單次獲得想要的結果的概率為p，那麼

$E=1 imes p+2 imes p imes (1-p)+...+n imes p imes (1-p)^{n-1}$

同樣的演算法，求得 $E=frac{1}{p}$ 。這說明這個結論的確是正確的。

那麼，對於收集問題呢？讓我們先把之前硬幣的問題稍稍複雜一點：

擲一枚硬幣，平均投擲多少次可以使得正面和反面都至少出現一次？

這次的情況似乎沒有那麼簡單了

別管那麼多，先扔一次再說！不管這次得到的是正面還是反面，除非是立起來的情況=。=，這一面肯定都是我們所需要集齊的。好了，扔完了？那麼現在想想看，問題似乎又變成了開始的問題，平均再扔多少次可以得到剩下的那一面？

理解了這種思想就不難理解這種演算法了，第一次是必然得到一種的，第二次有1/2的概率得到所需要的結果，所以平均需要1+2=3次來得到集齊正反面的結果。如果還存有疑慮，可以用前面期望定義的方法來進行驗證。

那麼現在，對於一張一張集齊卡片的問題就有了一個簡便的方法了。集齊每種卡片的問題中，每張卡都是需要的，就相當於骰子的面數、硬幣的正反面

每張卡片的獲得概率是相等的，那麼集齊所有n張卡片的期望次數為：

$E=1+frac{n}{n-1} +frac{n}{n-2} +...+frac{n}{1}$

這也正是所謂的優惠券收集問題（Coupon Collector『s Problem）的一種經典解法。

所以當n=108時，期望的次數應該是

$E=1+frac{108}{107} +frac{108}{106} +...+frac{108}{1}$

用Excel簡單計算一下就知道結果了，大概是568.51，取整數就是569.

這下終於知道了買多少包小浣熊速食麵才能集齊一百單八將了吧？569包速食麵，按一包5毛錢的市場價格計算，需要284.5軟妹幣大約才能集齊所有卡包，這對於當年一次只有一兩塊零用錢的我幾乎是個天文數字= =怪不得我總也集不齊......

當然了，現實當中是還有其它途徑獲取卡片的，比如：

1、和小夥伴兌換重複的卡片；

2、摔卡飛卡等日常遊戲手段贏得卡片（有輸的風險）

3、通過欺負小朋友等手段巧取豪奪別人的卡片（有被打的風險）；

而且我估計有幾張卡廠商是故意不發行的或者發行量極少的，這就打破了我們之前概率相同的假設了。

好了，讓我們再想想一種情形，假如速食麵廠商突然良心發現了，想多給我們發幾張卡，現在一包小浣熊速食麵裡面有兩張、三張或者五張卡了，而且同一包中的這幾張是不會重複的，那麼現在又需要買多少包才能集齊一百零八將了呢？

在捆綁抽卡的情況下，實際上情況又變得複雜了，因為它排除了連續幾張之間重複的情形。但我們還是一張一張來計算期望次數：

假設一百種不同卡，一包裡面有三張，那麼

$E=left[ (frac{100}{100} +frac{99}{99} +frac{98}{98} )+(frac{100}{97}+ frac{99}{96} +frac{98}{95} )+... ight] div 3$

具體的公式演算法和解釋懶得再寫了，暫時先到這裡吧。。。

附上一個MATLAB代碼來進行模擬驗證，它可以計算1000次試驗的平均值：

a0=0; n=100; %卡片張數 n0=1;%每包里卡片張數 for i=1:1000 %循環次數 cards=zeros(1,n); %將找到的卡片補上 m=0; %抽取次數 while sum(cards==0)~=0 %還有沒找到的卡片時繼續找 a=floor(1+rand(1,n0)*100); while length(unique(a))~=n0 a=floor(1+rand(1,n0)*100); end for j=1:n0 cards(a(j))=a(j); end m=m+1; end a0=a0+m; end s=a0/i

我想，這個問題的終極版將會是爐石開卡包，平均需要開多少包才能集齊所有爐石卡組？我們需要考慮的問題有很多，首先卡牌分為傳說、史詩、稀有和普通卡，它們出現的概率是不等的，且一包卡中至少有一張稀有，除去NAXX等以及新手就給的普通卡，分解重複卡還可以獲得奧術之塵，通過它我們可以合成所需要的卡片，那麼問題又來了，採用什麼樣的合成策略最有利於我們集齊所有卡牌呢？......複雜到寫一篇論文都綽綽有餘了吧。

24k純手工。首先了解一下幾何分布；總共試驗n次，前面n-1次都失敗，最後在第n次成功時的概率。下面進入正題：

數值解，么么噠！Matlab代碼如下，其實跟樓上差不多，當練習咯~

附上一篇有關數值解（Q）的好文：P Quant 和 Q Quant 到底哪個是未來？

a=0; for i=1:1000 %循環次數 n=100; %卡片張數 cards=zeros(1,n); %將找到的卡片補上 m=0; %抽取次數 while find(cards==0)~=0 %還有沒找到的卡片時繼續找 a1=floor(1+rand*100); if(cards(a1)==0) cards(a1)=a1; end m=m+1; end a=a+m; end a/i

ans =
518.6300

只有一種卡片，E(x)1=1
只有兩種卡片，E(x)2=1/2*2+1/(2^2)*3+1/(2^3)*4+....+1/(2^n)*(n-1) （其中，n趨向於+∞）
只有三種卡片，E(x)3=2/3*1/3*3+2/3*2/3*1/3*4+2/3*2/3*2/3*1/3*5+...+(2/3)^(n-2)*(1/3)*n（其中，n趨向於+∞）
只有四種卡片，E(x)4=3/4*2/4*1/4*4+....
拋磚引玉吧。。

記著我小時候買了一箱，全是李逵，史進這兩張卡⊙﹏⊙

定義隨機變數X為集齊100種卡片時購買的包數.則事件(X&<=n)可轉化為事件{購買的n包只含有小於等於99種卡片}.
故概率 $P(Xleq n)=1-frac{C_{100}^{1} imes 99^{n} }{100^{n} }$ .
則概率 $P(X=n)=P(Xleq n)-P(Xleq n-1)=frac{99^{n-1} }{100^{n-1} }$
根據數學期望公式 $EX=sum_{n=100}^{infty }{P(X=n) imes n}$ ,
代入計算，得
$EXapprox 3697.3$