【排組機統】期望值

[曾阿牛 10]

一甕中裝有m個相同大小的球　分別標有1~m號

如果　從甕中取球n次　每次都取出一球並記下球號後放回甕中

令此n個號碼最大值為X　　求X之期望值

＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿

以上題目　據說是有辦法解的　

而以下的題目　是個人自己想的　不知是否有解　

重做上述的問題　只不過將題目改成取球之後不放回甕中

[heinsolid 10]

取n個不大於k的整數有k^n種排列（可重複）。所以取n個最大是k的整數有k^n - (k-1)^n種排列。

Σ(1 <= k <= m) k [k^n - (k-1)^n] = Σ(1 <= j <= m) Σ(j = k <= m) k^n - (k-1)^n = Σ(1 <= j <= m) m^n - (j-1)^n

= m^(n+1) - Σ(1 <= j <= m-1) j^n

除上所有可能排列數m^n得到<X> = m [1 - Σ(1 <= j <= m-1) (j/m)^n]

這個summation應該沒辦法再化簡，但對於很大的m，可以用積分作近似。

[hellwd0217 10]

球不放回去的話...

由題可知 n<=m (拿到沒球就不能拿了..)

設P(X)為取n個數 X為最大數的機率

由於數字不會重複 所以

排列數 = n! 倍組合數 所以

P(X)

= ( X為最大數 的排列數 ) / ( 所有排列數 )

= (X為最大數 的組合數) / (所有組合數)

= C(X-1,n-1) / C(m,n)

= [ (X-1)! / (n-1)!(X-n)! ] / [ m! / (m-n)!n! ] = n(X-1)!(m-n)! / (X-n)!m!

然後 當 X<n 時 P(X) = 0 (取了n個數絕對不可能最大數比n小...)

故期望值 = Σ(n <= X <= m) [ P(X) X ] = Σ(n <= X <= m) [ nX(X-1)!(m-n)! / (X-n)!m! ]

[曾阿牛 10]

感謝 heinsolid 和 hellwd0217兩位大大的解答　　非常謝謝