马尔可夫链定阶
Published:
马尔可夫链定阶目的在于通过统计检验确定一个时间序列是否可以用一个有限阶的马尔可夫链来描述，为其他相关研究（比如独立性检验）奠定基础。
一、定阶检验原理
1.1 基于块熵的定阶检验
块熵是信息论中用于衡量序列不确定性的指标，描述长度为 $L$ 的连续序列块的熵值，反映了系统在特定时间尺度下的复杂度，计算公式为：
\[H(L) = - \sum_{x^L} P(x^L) \log P(x^L) \tag{1}\]如果序列完全随机，则 $H(L) = L\cdot H(1)$ 达到最大值；否则，$H(L) < L\cdot H(1)$。如果在 $L\geq K$时，$H(L+1) - H(L)$ 趋于稳定，则可以认为序列的马尔可夫阶数为 $K$。
Pethel等[1]提出了一种基于块熵和独立性检验的马尔可夫定阶方法，但我自己复现效果并不稳定，不能确定是算例的特殊性原因还是方法原因。
1.2 基于互信息和条件互信息的定阶检验
互信息（Mutual Information, MI）是衡量两个随机变量之间相互依赖关系的指标。对于离散和连续随机变量的定义分别为：
\[I(X;Y) = \sum_{x,y} P(x,y) \log \frac{P(x,y)}{P(x)P(y)} \tag{2}\] \[I(X;Y) = \int \int p(x,y) \log \frac{p(x,y)}{p(x)p(y)} dx dy \tag{3}\]条件互信息（Conditional Mutual Information, CMI）则衡量在给定第三个变量的条件下，两个变量之间的依赖关系。CMI可基于MI推导而得：
\[I(X;Y|Z) = I(X;Y, Z) - I(X;Z) \tag{4}\]在阶数为 $K$ 的马尔可夫链中，处于时刻 $t$ 的状态 $X_t$ 仅与前 $K$ 个状态 $X_{t-1}, X_{t-2}, \ldots, X_{t-K}$ 直接相关，因此存在如下的条件独立性：
当 $1 \leq k < K$ 时：
\[I(X_t; X_{t-k-1} | X_{t-1}, \ldots, X_{t-k}) > 0 \tag{5}\]当 $k \geq K$ 时：
\[I(X_t; X_{t-k-1} | X_{t-1}, \ldots, X_{t-K}) = 0 \tag{6}\]特别地：
\[I(X_t; X_{t-1}) > 0 \tag{7}\]二、定阶检验案例
骰子 $X$ 有6个面，对其进行 $N_{\text{steps}}=1000$ 次投掷，投掷过程分别遵循如下状态转移矩阵 $\boldsymbol{\pi}$ 所确定的0至2阶马尔可夫过程：
0阶投掷的状态转移矩阵：
\[\boldsymbol{\pi} = \frac{1}{6} \cdot \mathbf{1}_{6 \times 6}\]1阶投掷的状态转移矩阵：
\[\boldsymbol{\pi} = \begin{bmatrix} 0.5 & 0.25 & 0 & 0 & 0 & 0.25 \\ 0.25 & 0.5 & 0.25 & 0 & 0 & 0 \\ 0 & 0.25 & 0.5 & 0.25 & 0 & 0 \\ 0 & 0 & 0.25 & 0.5 & 0.25 & 0 \\ 0 & 0 & 0 & 0.25 & 0.5 & 0.25 \\ 0.25 & 0 & 0 & 0 & 0.25 & 0.5 \end{bmatrix}\]2阶投掷的状态转移矩阵：
对于任意历史状态 $(s_{t-2}, s_{t-1}) \in \mathcal{S}^2$：
\[\pi(X_t \mid X_{t-2}, X_{t-1}) = \begin{cases} [0.7, 0.2, 0.1] & \text{if } (0,0) \\ [0.1, 0.6, 0.3] & \text{if } (0,1) \\ [0.2, 0.2, 0.6] & \text{if } (0,2) \\ [0.3, 0.4, 0.3] & \text{if } (1,0) \\ [0.1, 0.8, 0.1] & \text{if } (1,1) \\ [0.0, 0.1, 0.9] & \text{if } (1,2) \\ [0.5, 0.5, 0.0] & \text{if } (2,0) \\ [0.2, 0.3, 0.5] & \text{if } (2,1) \\ [0.1, 0.1, 0.8] & \text{if } (2,2) \end{cases}\]检验结果如下：
0阶投掷的检验结果：
1阶投掷的检验结果：
2阶投掷的检验结果：
可见，基于MI和CMI的定阶检验方法能够有效地识别出马尔可夫链的阶数，在对应阶数处的信息量分布与背景分布呈现显著差异。
此过程还涉及Markov链自举重采样和多维变量概率密度估计等细节问题，此处按下不表。
参考文献
[1] S.D. Pethel, D.W. Hahs: Exact Test of Independence Using Mutual Information, 2014.