麻痺生活: 到底要花多少顆改石啊? (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。

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

大家好，我是哈姆寶的工讀生。
本單元一如往常，是跟大家聊聊簡單的數學，
以及如何透過這些簡單的原理，解釋遊戲中的一些現象。

話說瑪奇因為出雙槍的關係，紅改石的售價又被炒得火熱。

新手頻沒幾天就會聽到有人抱怨:
”花了大錢買改石，改了半天最後改出第一階段改造的武器 Q Q”
這類的發言。

所以，問題來了:
要改到第五階段或是第六階段改造，預期要多少改石?


要回答這個問題，我們先想簡單點的狀況:
假設不管怎樣裝到第三階段就收手(或者說當它第四階段之後不存在)

讓我們想一下瑪奇的武器特殊改造系統
把每階段之間的關係圖畫出來:

1. 武器的改造狀態有第零到第三階段，共 4 個狀態，用圓表示。
2. 圖中第零階段到第二階段是過度狀態(Transient state)，也就是說還沒改好，有改石就會繼續改下去；用藍色的圓表示。
3. 圖中第三階段是我們的目標，改到這邊就會收手，不會繼續改下去，這種狀態稱作吸收狀態(Absorbing state)，用紫色的圓表示。
4. 武器的初始狀態是第零階段，我們加上黃框標示。

現在，來看看不同狀態之間變換的關係…

我們把改造成功用綠色箭頭表示，失敗用紅色箭頭。每個箭頭標上該變換發生的機率。每一個狀態變換的機率用 P(i->j) 表示。

• (0->1) 改一定會成功，所以是第一個綠色箭頭是 P(0->1) = 100% = 1。
• 武器在第一階段時拿去改造，有 50% 機會成功(1->2)，50%機會失敗倒退一階段 (1->0)。同理，武器在第2段時拿去改造也是一樣狀況。
• 改到第三階段這個吸收狀態的時候，我們就會立刻收手。所以狀態再也不會變換了。或者說一直進行著 (3->3) 的 100% 不變的變換 (最右邊的紫色箭頭)。

我們用 Ei(Tj) 表示從 i 變換到 j 這個狀態期望會走多少步。

所以本文的問題，要從第 m 階段到第 n 階段期望要改多少次? 
Em(Tn) 就是要求的答案。

--

在繼續解下去之前，要先說明期望值的一個特性:

我們知道每次的改造，或者說每次狀態的變換，都只跟目前所在的狀態有關，跟到底怎麼走到目前這個狀態是完全無關 (或者說是獨立的)。

舉例來說:
不管你是一口氣改到第4階段，或是改了 500 次才改到，面對接下來的變換，是沒有差別的: 都一樣是 45% 的機會成功變第5階段，和55% 的機會失敗變第 3 階段。

在這種 “無記憶效應” 獨立的狀態變換下，期望值符合線性加疊。

由於證明起來頗麻煩，我們用簡單的例子說明:
猜拳獲勝的機會是 1/3，如果每次兩方出拳都是隨機的，每猜一次拳就期望獲勝 1/3 次，猜3次拳獲勝的期望值是 1 = (1/3 + 1/3 + 1/3)，猜12次拳期望獲勝 4 次 (期望猜 3 次贏 1次，要贏 4 次期望要猜 3+3+3+3 次)...

--

知道這個特性之後，我們回來看看剛剛的圖，
寫一下每個狀態之間變換的期望步數會是如何:

先從右邊看起...

從第三階段走到第三階段的期望步數:  E3(T3)

因為一但到第三階段就達成了我們改造的目標，不會再改了，也沒有必要再動了。想當然 E3(T3) = 0

從第二階段走到第三階段的期望步數: E2(T3)

首先，因為第二階段是個過渡狀態，我們不論如何要先改下去一次，改完之後有 50% 的機會到第三階段，50% 的機會掉回第一階段。到達第三階段的情況下，我們還要期望走 E3(T3) = 0 步 (廢話，因為已經改好不用再動了)；在掉回第一階段的情況下，我們期望要走 E1(T3) 步才能再爬到第三階段。

寫成方程式就是...

E2(T3) = 1 + 0.5*E3(T3) + 0.5*E1(T3) = 1 + 0.5*E1(T3)   …... (1)

在第一階段和第零階段可以寫出類似的方程式:

E1(T3) = 1 + 0.5*E2(T3) + 0.5*E0(T3)   …... (2)

E0(T3) = 1 + 1*E1(T3)   …... (3)

(1), (2), (3) 形成三元一次聯立方程式，用一點耐心就可以解出:

E0(T3) = 9  ;  E1(T3) = 8  ;  E2(T3) = 5

現在回頭看看，一口氣從第零階段改到第三階段的機率是 25%。

也就是平均四個改造武器的案例，就有一例是一口氣改到第三階段的。

這似乎讓很多人有錯覺以為準備個 4 ~ 8 顆改石就能改到第三階段。

事實上改到第三階段期望會用掉 9 顆改石。

事情總是比想像中要棘手啊!

-- 我是分格線 --

下回預告:

今天講的是 Markov Chain 簡單的應用

結構上很單純，但是用手動硬算實在很累 XD

下一回我們將使用線性代數解更多段的狀況

還有大致推估一下到底改造次數會怎麼分佈…

也就是說算一下最雖小的 25% 玩家到底會多慘!