標籤

code.google.com

2012年4月20日 星期五

賭徒破產問題:(gambler’s ruin problem)

甲、乙兩人輪擲一不公正銅板,此銅板出現正面之機率為 2/3,出現反面的機率為 1/3。
若出現正面,甲給乙 1 元,若出現反面,乙給甲 1 元。
今甲有 m 元,乙有 n 元,則甲將乙的錢贏光之機率為?
令 N=m+n.
令 P(m) 代表甲有 m 元時, 甲把乙的錢都贏過來的機率.
則 P(0)=0, P(N)=1.

P(m) = P(第1局出現正面)P(甲將乙的錢贏光|第1局出現正面)
    + P(第1局出現反面)P(甲將乙的錢贏光|第1局出現反面)
= (2/3)P(m-1) + (1/3)P(m+1)

(2/3){P(m)-P(m-1)} = (1/3){P(m+1)-P(m)}
或即
  P(m+1)-P(m) = 2[P(m)-P(m-1)]
  = 2^2[P(m-1)-P(m-2)]
  = 2^m[P(1)-P(0)] = 2^m P(1) 

  P(m) = P(m-1)+2^{m-1} P(1)
  = P(m-2) +2^{m-2}P(1) + 2^{m-1}P(1)
  = P(1) + 2P(1)+...+2^{m-1}P(1)
   = (2^m-1)P(1)
由 P(N)=1, 得
    P(1) = 1/(2^N-1)

    P(m) = (2^m-1)/(2^N-1) = (2^m-1)/(2^{m+n}-1).



沒有留言:

張貼留言