各位同學好!
今天要延續上回的話題:
到底要幾顆改石才夠用?
上回講了如何解 "
從第 i 階段改到第 j 階段，消耗改石數目的期望值"
相信聰明的同學應該已經發現，我們為什麼只算 “改到第三階段就收手” 的情況。因為這樣只有
四個狀態的推移，解算起來只要解個
三元一次方程式。如果真要計算
更多個狀態的變換的話，就會是
更多元的方程式，這樣會
複雜到很難不算錯。
所以嘛，本回要先介紹一下 Absorbing Markov Chain 的矩陣解法。
我們就拿上次
只改到第三階段的情況當範例吧
首先，要講一下 Markov Chain 的機率矩陣 P，和他的標準寫法
這樣寫的話…
第1 列從左到右分別是 P(0->0) , P(0->1), P(0->2), P(0->3)
第2 列則是 P(1->0), P(1->1), P(1->2), P(1->3)
其他以此類推，
P(i,j) = P(i->j)
如此可以很有條理地表示每個狀態變換成其他狀態的機率，如果弄個表示初始分佈的向量 V，PT x V 就是走了一次後的分佈情況，(P^n)T x V 就是 n 步後分佈的狀況。
解 Absorbing Markov Chain 的時候，P有一個標準型 (Standard form) 的寫法。就是把過渡狀態 (Transient state) 和吸收狀態 (Absorbing state) 分兩邊站寫到矩陣中。
我們的例子會寫成:
"第三階段" 是我們設定的吸收狀態，把它寫到最前頭去。
(一般習慣把吸收狀態寫在前頭，其實寫在後頭也是一樣的。)
這樣寫的話 P 矩陣分成四個子區塊
- 左上角的地方是 P(吸收->吸收)，由於吸收狀態 100% 只會變自己，所以這一區會形成對角一排1其他都是0 的單位矩陣 I (Identity Matrix)。
- 左下角是 P(過渡->吸收)，表示成 R。
- 右上角是 P(吸收->過渡)，由於吸收狀態都是死胡同不會變回過渡狀態，想也知道這區的數值都是 0。
- 右下角是 P(過渡->過渡) 的子矩陣，表示成 Q。
P^n 反應出 n 步後，初始態會如何飄移到各狀態......
- 右下角Q^n 會趨近於零，這叫夜路走多了一定碰到鬼，走了越多步以後 “失足跌落吸收狀態” 的比例就越高，無限次後還留在過渡狀態的機會是 0。
- 左下角會是一長串 Q^n 的總合乘上 R，我們把它簡稱 N，N 的正式名稱叫做基本矩陣 ( Fundamental matrix).
相減可以推得:
也就是
--
N 算出來之後呢?
首先我們要看看
是啥意思:
Q^n(i,j) 是從過渡狀態 i 出發，持續 n 次過渡狀態間轉換後，停留在 j 過渡狀態的機率。也可說成 1 個樣本從 i 狀態進入，成經過 n 次轉換後，停在 j 狀態的比例的期望值。
如此一來 N 就很容易理解了
不管 I 的話，(N - I) 矩陣中的 (i, j) 項就是: “從 i 狀態出發，終止在吸收狀態前，每一步停留在 j 狀態的期望值的總合 (或者說就是被吸收前，共期望在 j 狀態待了幾步)”
所以 N 的 i 列上所有數值的總合就是:
1 + (從 i 起始到被吸收前、期望在所有過渡狀態共停留了幾步)
= 到達吸收狀態時期望走了幾步
拿範例的 N 矩陣來看的話:
所以從第零階段改到第三階段，期望要走 3 + 4 + 2 = 9 步。也就是會用掉 9 顆改石。
--
搞完了有點難理解但是不易出錯的矩陣算法之後，
現在，讓我們回到原題
算算瑪奇特殊改造到底期望花掉多少改石:
各種改法的解整理成下表:
(從黃色階段走到紫色階段期望要改造幾次)
From/To
|
1
|
2
|
3
|
4
|
5
|
6*
|
0
|
1
|
4
|
9
|
17.3
|
29.7
|
68.3
|
1
|
|
3
|
8
|
16.3
|
28.7
|
67.3
|
2
|
|
|
5
|
13.3
|
25.7
|
64.3
|
3
|
|
|
|
8.3
|
20.7
|
59.3
|
4
|
|
|
|
|
12.4
|
51.0
|
5
|
|
|
|
|
|
38.6
|
* 第六階段的期望值是 "武器炸了就換一把繼續，不裝到不停" 的。
下圖是從第零段改到各段所期望消耗的改石:
--
由於第六階段很搞怪，這邊我們把 Markov Chain 畫出來。
F 狀態表示武器改失敗炸掉的狀況，
所以，到底會期望炸掉多少次才上第六階段咧?
回頭來看看這個 Markov Chain 的 Fundamental matrix
進入吸收狀態 (第六階段) 前，期望會在 F 狀態待 1.2 回。
也就是說:
改到第六段會期望消耗近 70 顆的改石，還期望炸掉 1.2 把武器!
--
附記:
第六階段有一些算錯的小地方，
圖也有筆誤的地方，已經修正，請安心食用 XD。
