麻痺生活: 到底要花多少顆改石啊? (2)

各位同學好!
今天要延續上回的話題: 到底要幾顆改石才夠用?

上回講了如何解 "從第 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 步後，初始態會如何飄移到各狀態......

現在我們來看看當 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。