Re: [問題] 徵求數學高手~~

[Favonia (sdfmskdlfksmdflkskdfmsl)]

設有n+1個狀態 s0,s1,s2,s3...sn
si代表n個球中還有i個球沒有拿到
當目前的狀態是si時，多抽一顆球有i/n的機率變成s(i-1)，有(n-i)/n的機率變成si
因此與之前的狀態無關，適用於馬可夫鍊的理論

---

令hi代表由si這個狀態到達s0這個狀態的步數的期望值
顯然題目可轉化為求出hn (一開始每個球都沒抽過，平均要抽幾次才能全抽過)

又，h0 = 0
    hi = 1 + (i/n) * h(i-1) + ((n-i)/n) * hi
=>  hi = (n/i) + h(i-1)

故 hn = n/n + n/(n-1) + n/(n-2) + .... + n/2 + n/1
      = n * (1/1 + 1/2 + 1/3 ... 1/n)

我只能說，結果好漂亮阿

Markov Chain 萬歲

※ 引述《vogoho (小小小...)》之銘言：
:      無聊的話幫我解這題試試看吧~~
:      一個袋子裡放了n個球....上面編號分別為1~n
:      每次抽一球後放回,攪拌均勻再抽一球
:      直到所有球都曾經被抽起來過為止....請問抽球次數的期望值是多少??

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 210.85.36.69
※ 編輯: Favonia         來自: 210.85.36.69         (10/19 01:03)
→ pipibjc:這個人是?
→ Aves:推馬可夫鏈 好懷念喔
→ Favonia:我
※ 編輯: Favonia         來自: 210.85.36.69         (10/19 01:11)
→ phylin:資訊金牌彼得
→ lorderic:某金牌學弟
→ Dawsen:強者！！
→ wanderer:看完之後有一種莫名的感動~~
→ Deatheye:Amazing.......it's really amazing......
→ amozartea:太強了...