首見時間與首訪時間

考慮一個不可分解的馬可夫矩陣，除了穩定態以外，隨機漫步模型裡在意的另一個問題是從點 \(i\) 出發，首次出現在點 \(j\) 所需的平均時間，我們將其稱為 \(i\) 到 \(j\) 的 首見時間（hitting time），記作 \(h_{i,j}\)。如果把所有 \(h_{i,j}\) 記在一個矩陣裡，則 \(H = \begin{bmatrix} h_{i,j} \end{bmatrix}\) 稱為 首見矩陣。

如果單純用定義來看，首見時間通常不容易計算。比如說我們考慮馬可夫矩陣

\[ M = \begin{bmatrix} 0 & 1 & 0 \\ 0.5 & 0 & 0.5 \\ 0 & 1 & 0 \end{bmatrix} \]

在這個模型中，點 \(1\) 出發後的下一點必定是點 \(2\)，所以 \(h_{1,2} = 1\)。

反之從點 \(2\) 出發後，只有一半的機率回到點 \(1\)，有另一半的機率會走到點 \(3\) 再走回點 \(2\)，而這一半的機率又有一半會走到點 \(1\)，另一半又走到點 \(3\) 再回點 \(2\)，所以能夠走到點 \(1\) 的時間是 \(1, 3, 5, \ldots\)，而相對應的機率是 \(0.5, 0.5^2, 0.5^3, \ldots\)，也就是其期望值是

\[ \begin{aligned} h_{2,1} &= (0.5)\cdot 1 + (0.5)^2\cdot 3 + (0.5)^3\cdot 5 + \cdots \\ &= 3. \end{aligned} \]

基於對稱性，我們也知道 \(h_{2,3} = h_{2,1} = 3\)。這時候我們就可以知道 \(h_{1,3} = 1 + h_{2,3} = 4\)，因為點 \(1\) 出發以後必定先走一步到點 \(2\)。最後依照定義得到 \(h_{i,i}\) 都是 \(0\)，所以

\[ H = \begin{bmatrix} 0 & 1 & 4 \\ 3 & 0 & 3 \\ 4 & 1 & 0 \end{bmatrix}. \]

如果我們計算

\[ \begin{aligned} \check{H} &= MH + J \\ &= \begin{bmatrix} 0 & 1 & 0 \\ 0.5 & 0 & 0.5 \\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} 0 & 1 & 4 \\ 3 & 0 & 3 \\ 4 & 1 & 0 \end{bmatrix} + \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \\ \end{bmatrix} \\ &= \begin{bmatrix} 4 & 1 & 4 \\ 3 & 2 & 3 \\ 4 & 1 & 4 \end{bmatrix} \end{aligned} \]

會發現 \(\check{H}\) 和 \(H\) 除了對角線上的元素以外其它都一樣。這是因為 \(J\) 代表「先走一步」，而 \(MH\) 代表由點 \(i\) 依機率往各鄰近點偷走一步以後，「第二步開始」前往點 \(j\) 的時間。因此 \(\check{H}\) 的各項 \(\check{h}_{i,j}\) 指的是由點 \(i\) 出發且 一定要先走一步 後，首次造訪點 \(j\) 的平均時間，我們稱為 首訪時間（mean first passage time）。自然而然當 \(i\neq j\) 時有 \(h_{i,j} = \check{h}_{i,j}\)，而 \(\check{h}_{i,i}\) 指的是一開始不算第一次回到自己的平均時間。

以下整理這些矩陣的相關性質：

  1. \(H\) 的對角線項均為 \(0\)。
  2. \(\check{H} = H + D\)，其中 \(D\) 是對角矩陣。
  3. \(MH + J = \check{H} = H + D\)。

我們可以整理第三點得到 \((I - M)H = J - D\)，其中 \(H\) 和 \(D\) 是未知的項，但我們知道 \(H\) 在對角線上均為 \(0\)。以上述的例子來說，在給定 \(M\) 以後可以寫下等式

\[ \begin{bmatrix} 1 & -1 & 0 \\ -0.5 & 1 & -0.5 \\ 0 & -1 & 1 \end{bmatrix} \begin{bmatrix} 0 & ? & ? \\ ? & 0 & ? \\ ? & ? & 0 \end{bmatrix} = \begin{bmatrix} ? & 1 & 1 \\ 1 & ? & 1 \\ 1 & 1 & ? \\ \end{bmatrix}. \]

如此就不難回推 \(H\) 和 \(D\)，也可以避免解無窮級數。

更精確來說，令 \(A = I - M\) 而 \(A(j)\) 為將 \(A\) 的第 \(j\) 行及列都刪掉的矩陣。當 \(M\) 是不可分解時，每一個 \(A(i)\) 都是可逆的，而 \(A(j)^{-1}\bone\) 所得的 \(n - 1\) 個數字，就會是 \(H\) 中第 \(j\) 行中除了對角線項（該項為 \(0\)）以外的 \(n - 1\) 項。

想想以下問題：

  1. 令
    \[ M = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0.5 & 0 & 0.5 & 0 \\ 0 & 0.5 & 0 & 0.5 \\ 0 & 0 & 1 & 0 \\ \end{bmatrix}. \]

    與其在理論上不斷思考自己有沒有算錯，更直接的方法就是寫一個程式來作實驗。

    1. 寫一個函數 markov_next(i, M) ，其隨機回傳點 \(i\) 出發的下一個點。
    2. 寫一個函數 from_to(i, j, M) ，其計算從點 \(i\) 出發隨機走到點 \(j\) 所需的時間。
    3. 寫一個函數 hitting_time(i, j, M) ，其執行 from_to(i, j, M) 許多次，並將得到的結果取平均。
    4. 寫一個函數模擬 \(h_{i,i}\)。
  2. 說明為什麼
    \[ (0.5)\cdot 1 + (0.5)^2\cdot 3 + (0.5)^3\cdot 5 + \cdots = 3. \]
  3. 令
    \[ M = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0.5 & 0 & 0.5 & 0 \\ 0 & 0.5 & 0 & 0.5 \\ 0 & 0 & 1 & 0 \\ \end{bmatrix}. \]

    利用 \((M - I)H = D - J\) 的方法求出 \(H\) 及 \(D\)。

  4. 說明為什麼當 \(M\) 是不可分解時，\(I - M\) 拿掉任一行任一列後都是可逆矩陣。