前言

昨天提到馬可夫鏈，說明這是一個描述「一連串相關事件所組成的系統，會怎麼隨著時間變化」的數學模型。並提到可以用這個方法計算第 n 次觀察時，小明各狀態的機率。

小明的狀態轉移 (續)

今天我們將接續昨天提到的例子，以 Python 計算小明各狀態的機率確實會收斂，以下先說明我使用的環境與套件，未來幾天的實作也將以這些環境、套件為主。

• Ubuntu 18.04 LTS
• Python 3.6.6
• numpy

不過在 Windows 上也可以執行 Python，安裝方法也很多 (官網下載、Anaconda)，這邊就不多做說明。

實作

我們先針對轉移矩陣本身，確認其會不會收斂。

import numpy as np
Matrix_trans = np.array([[0.9,0.1],[0.5,0.5]])

# after n steps
Matrix_trans_step3 = np.linalg.matrix_power(Matrix_trans, 3)
Matrix_trans_step5 = np.linalg.matrix_power(Matrix_trans, 5)
Matrix_trans_step10 = np.linalg.matrix_power(Matrix_trans, 10)
Matrix_trans_step50 = np.linalg.matrix_power(Matrix_trans, 50)
Matrix_trans_step100 = np.linalg.matrix_power(Matrix_trans, 100)

# print the result
print('After 3 steps: \n', Matrix_trans_step3, '\n')
print('After 5 steps: \n', Matrix_trans_step5, '\n')
print('After 10 steps: \n', Matrix_trans_step10, '\n')
print('After 50 steps: \n', Matrix_trans_step50, '\n')
print('After 100 steps: \n', Matrix_trans_step100, '\n')

執行上方內容後，可以得到

After 3 steps:
 [[0.844 0.156]
 [0.78  0.22 ]]

After 5 steps:
 [[0.83504 0.16496]
 [0.8248  0.1752 ]]

After 10 steps:
 [[0.83335081 0.16664919]
 [0.83324595 0.16675405]]

After 50 steps:
 [[0.83333333 0.16666667]
 [0.83333333 0.16666667]]

After 100 steps:
 [[0.83333333 0.16666667]
 [0.83333333 0.16666667]]

表示轉移矩陣本身即會收斂，因此再加上任意狀態，也都會收斂。不論起始的狀態是 或隨機。

# set s0 = [1, 0]
s0 = np.array([1.0, 0.0])

# print the result
print('Initial state: \n', s0, '\n')
print('After 3 steps: \n', np.dot(s0, Matrix_trans_step3), '\n')
print('After 5 steps: \n', np.dot(s0, Matrix_trans_step5), '\n')
print('After 10 steps: \n', np.dot(s0, Matrix_trans_step10), '\n')
print('After 50 steps: \n', np.dot(s0, Matrix_trans_step50), '\n')
print('After 100 steps: \n', np.dot(s0, Matrix_trans_step100), '\n')

 Initial state:
 [1. 0.]

After 3 steps:
 [0.844 0.156]

After 5 steps:
 [0.83504 0.16496]

After 10 steps:
 [0.83335081 0.16664919]

After 50 steps:
 [0.83333333 0.16666667]

After 100 steps:
 [0.83333333 0.16666667]

# random initial state
rand_num = np.random.rand(1)
random_s0 = np.array([rand_num, 1-rand_num]).reshape(2)

# print the result
print('Initial state: \n', random_s0, '\n')
print('After 3 steps: \n', np.dot(random_s0, Matrix_trans_step3), '\n')
print('After 5 steps: \n', np.dot(random_s0, Matrix_trans_step5), '\n')
print('After 10 steps: \n', np.dot(random_s0, Matrix_trans_step10), '\n')
print('After 50 steps: \n', np.dot(random_s0, Matrix_trans_step50), '\n')
print('After 100 steps: \n', np.dot(random_s0, Matrix_trans_step100), '\n')

Initial state:
[0.6913491 0.3086509]

After 3 steps:
[0.82424634 0.17575366]

After 5 steps:
[0.83187941 0.16812059]

After 10 steps:
[0.83331845 0.16668155]

After 50 steps:
[0.83333333 0.16666667]

After 100 steps:
[0.83333333 0.16666667]

限制

那麼，只要符合馬可夫性質，結果都會收斂嗎？針對這個問題，我發現在 Quora 上有人有一樣的疑問，並發現除了馬可夫性質，還有兩個條件需要遵守：

• 任意狀態能夠轉移到任意其他狀態：狀態之間不一定要可以直接轉移，但必須能夠到達那個狀態。
• 狀態轉移不是固定的週期 (ex: 1 -> 3 -> 2 -> 4 -> 1 ...)

如果只滿足條件一，那麼最終不會收斂，而是卡在重複的週期中 [example]；
如果只滿足條件二，那最終只會在連通的部分收斂 [example]；
如果兩個都不滿足，那就在連通的狀態中，會出現重複的週期 [example]。

個人認為版面上再貼程式碼會很亂，所以用外部連結呈現結果。

至此，是針對馬可夫鏈的說明，明天將進入馬可夫決策過程。

Reference

[1] How do I tell whether a Markov chain can converge to equilibrium? [link]