標籤：

奧林匹克數學數學概率論隨機數學

有N個水果，每次取n個出來洗，洗完放回去打亂，平均需要洗幾次能全洗完？

01-21

n=1或者n=N似乎都不難，剩下的要怎麼算啊？

洗水果的過程可以用狀態(X, Y)來完全描述，其中X是當前已經洗了的水果，Y是還沒有洗的水果。

考慮下n = 2, N = 5的情況，洗水果的過程中有如下可能的狀態：

(0, 5), (2, 3), (3, 2), (4, 1), (5, 0)

狀態之間的轉化關係如下圖：

問題於是轉化成：從（0， 5）到（5， 0）平均需要多少步。狀態之間的轉移概率很容易計算，比如：

要從(2, 3)轉移(3, 2)，我們需要從2類中各選一個： $inom{3}{1}inom{2}{1}/inom{5}{2}=0.6$

完整版見下圖：

按照從左到右的順序排列這些狀態，轉移矩陣可以寫為：

$P = left( egin{array}{ccccc} 0 1 0 0 0 \ 0 0.1 0.6 0.3 0 \ 0 0 0.3 0.6 0.1 \ 0 0 0 0.6 0.4 \ 0 0 0 0 1 \ end{array} ight)$

其中 $P_{ij}$ 是i到j的概率。問題就等價於求這個馬爾科夫鏈的mean time to absorption。定義R為transient states之間的轉移矩陣:

$R = left( egin{array}{cccc} 0 1 0 0 \ 0 0.1 0.6 0.3 \ 0 0 0.3 0.6 \ 0 0 0 0.6 \ end{array} ight)$

$[1,0,0,0]R^k$ 是從（0， 5）出發，第k步訪問每一個狀態的概率。於是各個狀態的平均訪問次數為：

$au =sum_i^{infty}[1,0,0,0]R^i= [1,0,0,0](I - R)^{-1}=[1, 1.11111, 0.952381, 2.2619]$

期望的總次數為：

$E = au_1 + au_2 + au_3 + au_4 = 5.3254$

如果對馬爾科夫鏈不熟悉，可以通過狀態之間的轉移關係，寫出遞歸式來計算訪問次數。設 $g(x)$ 為從狀態x出發，洗水果的期望次數。那麼：

$g(0) = g(1) + 1\ g(1)=.1g(1)+.6g(2)+.3g(3)+1\ g(2)=.3g(2)+.6g(3)+.1g(4)+1\ g(3)=.6g(3)+.4g(4)+1\ g(4)=0$

解以上線性方程，g(0)就是我們求得期望。

進一步，我們可以求洗的次數的分布，為此，需要把(0, 5)改造成transient state，並添加一個新的absorbing state。新的轉移矩陣：

$Q=left( egin{array}{cccccc} 0 1 0 0 0 0 \ 0 0.1 0.6 0.3 0 0 \ 0 0 0.3 0.6 0.1 0 \ 0 0 0 0.6 0.4 0 \ 0 0 0 0 0 1 \ 0 0 0 0 0 1 \ end{array} ight)$

容易驗證， $p^k=[1,0,0,0,0,0]Q^k[0,0,0,0,1,0]$ 是恰好第k次洗完的概率，概率質量函數如下圖：

橫軸是洗的次數，縱軸是剛好在這一次洗完的概率。

期望也可以用過概率質量函數來驗證：

$E=sum_{i}^{infty}ip_i=5.3254$

這種計算方法很容易泛化到某一具體n和N，但要計算一般式，需要仔細的寫出上面的遞歸式。

更新：容斥的那個-1的指數應該是i-1。

很絕望啊……怎麼……退役前的坑現在還會跳出來把我打一頓啊？

可以用高斯消元做，這一點應該是很簡單的。 @paid Pay

dalao："給你講過那麼多遍容斥你都忘了"

於是照著他給的做法(並且對著課件)寫了一遍……

就是這種比較有趣的做法：

clj計數專題_圖文_百度文庫

考慮容斥原理來做，令 $X_i$ 為第 $i$ 個蘋果被染色的輪數。根據課件中提供的做法：

$E(max(X_i))=sum_{S in [1,2,...,n],|S|geq1}(-1)^{|S|-1}E(min(X_i)_{iin S})$

注意到這道題可以寫成組合形式：

$sum_{i=1}^{n} inom n i (-1) ^i sum_{j=1}^{+infty}P_i^j$

其中 $P_i$ 表示 $i$ 個蘋果沒有任何一個被洗到的概率，有 $P_i=frac{inom {n-i}{m}}{inom{n}{m}}$

由 $sum_{j=0}^{+infty}P_i^j=frac{1}{1-P_i}$ ，原題就可以解決啦！

答案就是這個 $sum_{i=1}^{n} inom n i (-1) ^ifrac{1}{1-P_i}$

至於那個容斥係數對不對……嗯……我也不知道……

(所以怎麼才能確定這個係數啊QAQ)

謝邀...Well...這個問題是不是同構于贈券收集...

有n種卡片,每次抽k張,抽到每一張的概率相等,求抽到全部卡片的次數期望.

一個是有限集一個是無限集,但是只考慮概率是相同的.

有n個水果,每次取k個出來洗,洗完放回去打亂,平均需要洗幾次能全洗完?

那這個

樣本空間為M，每次隨機選取N個樣本，X次選取之後剛好每個樣本都至少被選取一次，請問X的期望值是多少？

用的容斥原理,然後可以進一步化簡,前面的一堆容斥係數吃進去...

最終結果就是: $E_k(n)=sum_{i=1}^nfrac{1}{1-inom{i}{k}ig/inom{n}{k}}$

按照基本法 $inom{a}{b}=0quad mathrm{if} a<b$ 這個都知道對吧...

一階展開似乎是: $E_k(n)simfrac{n}{d} (ln n+gamma +O(1))+Oleft(frac{1}{n} ight)$

設已有 $x$ 個洗完時，離全部洗完平均還需要的次數為 $gleft( x ight)$

易知： $gleft( 0 ight)=1+gleft( n ight)$ ， $gleft( N ight)=0$

且 $gleft( x ight)=1+Sigma_{i=0}^{n}gleft( x+i ight)*frac{C_{N-x}^i*C_x^{n-i}}{C_N^n}$ （ $C_m^n=0quad if quad n>m$ ）

解線性方程組解出 $gleft( 0 ight)$ 即可。

當然了數字一大，硬解是很麻煩的。

（希望沒有筆誤）

唔，喜歡 @張辛寧的答案

設 $P(x)$ 為洗了 $x$ 次後仍舊有沒洗過的水果的概率。

顯然最終答案為 $sum_{x=0}^{infty}P(x)$ 。

如何求 $P(x)$ ?

$P(x)=1-sum_{i=0}^{N}(frac{C_{N-i}^{n}}{C_{N}^{n}})^x(-1)^iC_N^i$

$=sum_{i=1}^{N}(frac{C_{N-i}^{n}}{C_{N}^{n}})^x(-1)^{i-1}C_N^i$

$sum_{x=0}^{infty}P(x)=sum_{i=1}^{N}frac{1}{1-frac{C_{N-i}^{n}}{C_N^n}}(-1)^{i-1}C_N^i$

$=sum_{i=1}^{N}frac{(-1)^{i-1}C_N^iC_N^n}{C_N^n-C_{N-i}^n}$

深夜意識模糊推了式子不知對不對...

算了，睏覺去了

....依我看是怎麼也洗不完，洗完放回去又髒了

是誰要這麼喪心病狂地洗水果越來越搞不懂城裡人了!

emmmm……想吃什麼洗什麼，洗完為什麼還要放回沒洗的那堆里，一般不都是要麼不洗要麼全洗的嗎？還是城裡人會玩……

問平均洗多少遍……我腦子不好想不通……

N個水果，每次拿n個上來洗的很有可能是上次已經洗過的n（或＜n）個，沒洗過的可能永遠也洗不到……

如果這個題再多點條件，比如說要洗的這n個裡面有k（0＜k＜n）個沒洗過的……

誒呀我的媽……

一次洗完，N個水果，拿N個，又不是拿N-x個，這問題問的很符合我的口味！

這個問題就像：每期都買一次體育彩票7位數，幾次可以中獎？

一本正經回答的沒有常識嗎，還要回答嗎。。。。。

推薦閱讀：

※如何在KTV或者酒吧中吹牛，就是搖色子，所向披靡？
※如果X服從標準正態分布，那X的絕對值符合什麼分布?
※一根1米長的繩子，隨機切N刀，變成(N+1)根繩子，為什麼最短的一根繩子長度的期望是1/(N+1)^2？
※離散型隨機變數有沒有概率密度？
※網易遊戲筆試題目，怎麼做？

TAG:數學 | 隨機數學 | 奧林匹克數學 | 概率論 |