例題3-1-淡江大學.ppt

Chapter 8 馬可夫鏈與競賽理論 淡江大學資訊管理系侯永昌 編輯自滄海書局所提供之投影片 馬可夫鏈 例題 2 例題 3 例題 3-1 例題 3-1 (cont.) 例題 2-1 例題 2-1 (cont.) 例題 3-1 例題 6-1 例題 6-1 (cont.) 例題 6-2 例題 6-2 (cont.) 例題 1-1 例題 1-2 例題 3-1 例題 3-1 (cont.) 例題 3-2 例題 3-2 (cont.) 例題 3-2 (cont.) 例題 1-1 例題 2-1 例題 2-2 例題 3-1 例題 3-2 例題 2-1 例題 2-1 (cont.) 例題 2-2 例題 2-2 (cont.) 例題 3-1 例題 3-1 (cont.) 例題 3-2 例題 3-2 (cont.) 轉換矩陣P的固定機率向量t為[0.157 0.154 0.689] 故可計算出下列的結果： 例題3-3 股票漲跌問題 (cont.) 1.45 N 6.49 D 6.37 I 平均再現時間(天) 狀態 I II I II 在每一列的最小中，找每一行的最大 在每一列的最小中，找每一行的最大 14 頁的例 3-1 t = t P 假設賭徒I有$3，賭徒II有$2，他們投擲一枚公正的硬幣：如果出現正面，賭徒I輸$1；如果出現反面，賭徒I贏$1。試問要經過多久時間，賭博就會結束(其中一個賭徒會破產)？ 解： 任何時候贏$1和輸$1的機率都是50%，當某人擁有0元或5元時，賭博結束。因此轉換矩陣P為 例題3 賭徒競賽問題 首先，子分割轉換矩陣 例題3 賭徒競賽問題 (cont.) T矩陣提供了在結束賭博以前，停在非吸收狀態的期望次數 最右邊的數字代表如果某個賭徒他現在只有一元，則他在贏光或輸光所有的錢之前的期望賭局數為4局，也就是賭局將於第五局時結束。在這之前，他有1.6局的時間剩下一元，有1.2局的時間剩下二元，有0.8局的時間剩下三元，有0.4局的時間剩下四元 其他的情況可以依此類推 例題3 賭徒競賽問題 (cont.) 現態 次態 T?S代表由非吸收狀態到吸收狀態的機率 例如：某賭徒只有一元時，他輸光的機率為80%，贏光的機率為20%；若他只有三元時，他輸光的機率為40%，贏光的機率為60% 例題3 賭徒競賽問題 (cont.) 請注意！ 1、有些書本對於轉換矩陣的定義剛好與本書相反，他們的列代表次態，他們的行代表現態 2、因此吸收馬可夫鏈的求解方式也有一些不同 1-2 假設股票交易有三個狀態：上漲(I)、下跌(D)、平盤(N)，他的轉換矩陣P假設為 這個轉換矩陣並不存在吸收狀態，要如何進行吸收馬可夫鏈呢？假設想求某之股票在下跌以前，停留在上漲或平盤的時間，則可假設狀態D是一個吸收狀態 例題3-3 股票漲跌問題 現態 次態 將P’予以子分割 表示： 如果某支股票目前為上漲，則在它下跌之前，平均有4.4天的上漲和10.5天的維持平盤，也就是這支上漲的股票在它下跌之前，平均共經過14.9天 如果某支股票目前為平盤，則在它下跌之前，平均有2.4天的上漲和12.8天的維持平盤，也就是這支平盤的股票在它下跌之前，平均共經過15.2天 例題3-3 股票漲跌問題 (cont.) * * 現態 次態 請注意！本例中的遞移矩陣的定義 從某個狀態轉換到另外一個狀態的機率，僅與其目前的狀態有關，與時間的變化無關 現態 次態 請注意！有些書本對於轉換矩陣的定義剛好與本書相反，他們的列代表次態，他們的行代表現態 遞移矩陣 第k階段的狀態僅與第k-1階段的狀態和轉換矩陣有關，而轉換矩陣內的值都是常數，代表不會隨著時間而變化，因此與時間的變化無關 請注意！ 1、有些書本對於轉換矩陣的定義剛好與本書相反，他們的列代表次態，他們的行代表現態 2、因此(1)式應修改為V (k) = P V (k-1) V (k) = V (k-1) P (1) 請注意！ 1、有些書本對於轉換矩陣的定義剛好與本書相反，他們的列代表次態，他們的行代表現態 2、因此(2)式應修改為V (k) = P k V (0) 現態 次態 請注意！本例中的遞移矩陣的定義 P矩陣的值呈現收斂的狀態，大概P 7以後就沒什麼改變了 (b) (a) ? ? *