回家的平均時間與凱梅尼常數

考慮一個不可分解的馬可夫矩陣 \(M\) 及其首見矩陣 \(H\)、首訪矩陣 \(\check{H}\)。回顧我們有以下性質：

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

而第 \(3\) 點可以改寫為

\[ (I - M)H = J - D. \]

這裡對角矩陣 \(D\) 上紀錄的是 \(\check{h}_{i,i}\)，也就是從點 \(i\) 出發後，首次回到點 \(i\) 所需的平均時間。上一節對於 \(H\) 的解法雖然可以找到 \(D\)，但似乎看不出什麼特性。

實際上在解 \(H\) 之前我們就可以先算出 \(D\)。原因是 \(I - M\) 的每一行都和穩定態 \(\pi\trans = (p_1, \ldots, p_n)\) 垂直（實際上當 \(M\) 不可分解時，\(\Col(I - M) = \vspan\{\pi\}^\perp\)），而因此 \((I - M)H = J - D\) 的每一行也要和 \(\pi\trans\) 垂直。以 \(J - D\) 的第 \(j\) 行來說，我們會有

\[ p_j\check{h}_{j,j} + \sum_{i\neq j} p_i = 0. \]

如此可得

\[ \check{h}_{j,j} = -\frac{1}{p_j}\sum_{i\neq j} p_i = \frac{p_j - 1}{p_j} = 1 - \frac{1}{p_j}. \]

如果我們令 \(\Pi\) 為對角線項為 \(\pi\trans\) 的對角矩陣，則我們有

\[ D = \Pi^{-1}. \]

由於 \(\pi\trans = (p_1, \ldots, p_n)\) 是穩定態，我們可以想像每走一輪，平均就有 \(p_j\) 比例的人跑到點 \(j\)，所以要湊滿 \(1\) 個完整的人跑到點 \(j\) 需要 \(\frac{1}{p_j}\) 步。這就像是丟一次骰子平均可以得到 \(\frac{1}{6}\) 個 \(1\)，所以平均來說要丟出一個 \(1\) 的次數是 \(\frac{1}{1/6} = 6\) 次。

所以現在我們知道 \(\pi\trans (J - D) = \bzero\trans\)。由於 \(J - D\) 是對稱矩陣，我們發現

\[ (I - M)H\pi = (J - D)\pi = \bzero. \]

然而當 \(M\) 是不可分解時，\(\ker(I - M)\) 只有一個維度，也就是 \(\vspan\{\bone\}\)。這表示 \(H\pi\) 可以寫成 \(\bone\) 的倍數，也就是 \(H\pi = \hat{K}\bone\)，其中 \(\hat{K}\) 為一常數。同時也可以計算

\[ \check{H}\pi = (H + D)\pi = (H + \Pi^{-1})\pi = (\hat{K} + 1)\bone. \]

當我們選定一個點 \(i\) 時，我們可以計算從點 \(i\) 出發，擴散到穩定態平均所需的時間

\[ \sum_{j=1}^n\check{h}_{i,j}p_j. \]

由於這個數就是 \(\check{H}\pi\) 的第 \(i\) 項，我們發現不管從哪一個點出發，這個平均時間都是 \(K = \hat{K} + 1\)。匈牙利裔美藉數學家 John G. Kemeny 發現了這個性質，而後人將這個常數稱之為 凱梅尼常數（Kemeny's constant）。直觀來說，凱梅尼常數愈小表示這個隨機漫步模型從一點出發後，愈容易到到每一點。

想想以下問題：

考慮一個不可分解的馬可夫矩陣 \(M\)，描述 \(I - M\) 的左零解空間 \(\ker((I - M)\trans)\) 及右零解空間 \(\ker(I - M)\)，並用其說明 \(I - M\) 刪掉任一行任一列後都是可逆矩陣。
由期望值的定義計算丟一枚公正硬幣時，第一次要出現正面所需的平均次數。
計算以下馬可夫矩陣的凱梅尼常數。
1. \(M = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\)。
2. \(M = \begin{bmatrix} 0 & 1 & 0 \\ 0.5 & 0 & 0.5 \\ 0 & 1 & 0 \\ \end{bmatrix}\)。