AFLFast笔记

1. 马尔可夫模型

1.1 转移概率矩阵 $ P = (p_{ij})$

• $P$ 是一个 $N×N$ 的随机矩阵，每个元素都是非负的，每行之和为 1。
• $p_{ij}$ 表示链从状态 $i$ 转移到状态 $j$ 的条件概率，即 $P(X_{t+1} = j \mid X_t = i)$。

1.2 时间齐次马尔可夫链

如果转移概率矩阵$P$ 不依赖于时间 $n$，即每次链处于状态 $i$ 时跳到状态 $j$ 的概率都是相同的，那么这个马尔可夫链是时间齐次的。

如果一个马尔可夫链是时间均匀的，那么存在一个概率分布 $\pi$，称为该链的平稳分布。$\pi$ 满足以下:

$$
0 \leq \pi_j \leq 1, \sum_{i\in S} \pi_i = 1, \pi_j = \sum_{i\in S} \pi_i p_{ij}
$$

即 $\pi$ 是链的平稳状态分布，且与初始状态无关，这里，$S$ 表示状态空间，$p_{ij}$ 是从状态 $i$ 转移到状态 $j$ 的概率。

简而言之，平稳分布 $\pi$ 具有一个重要特性：一旦马尔可夫链达到这个分布，它将在后续的转移中保持这个分布，且这个最终分布与初始状态无关，

以下是一个计算平稳分布的简单案例:

# 定义转移概率矩阵
P = [[0.5, 0.3, 0.2],
     [0.1, 0.6, 0.3],
     [0.2, 0.1, 0.7]]

# 初始化 π 为等概率分布
pi = [1/3, 1/3, 1/3]

epsilon = 1e-6
while True:
    new_pi = [0, 0, 0]
    for j in range(3):
        for i in range(3):
            new_pi[j] += pi[i] * P[i][j]
    if sum(abs(new_pi[i] - pi[i]) for i in range(3)) <= 0:
        break
    pi = new_pi

print("第一次平稳状态分布 π =", pi)


pi = [0, 1, 0]

while True:
    new_pi = [0, 0, 0]
    for j in range(3):
        for i in range(3):
            new_pi[j] += pi[i] * P[i][j]
    if sum(abs(new_pi[i] - pi[i]) for i in range(3)) <= 0:
        break
    pi = new_pi

print("第二次平稳状态分布 π =", pi)

输出如下：

第一次平稳状态分布 π = [0.2432432432432431, 0.29729729729729704, 0.4594594594594591]
第二次平稳状态分布 π = [0.24324324324324312, 0.2972972972972971, 0.4594594594594592]

这个代码示例中，首先定义了一个 3x3 的转移概率矩阵，然后使用两种不同的初始分布（[1/3, 1/3, 1/3] 和 [0, 1, 0]）来计算平稳分布，可以初步看到，无论初始分布如何，最终都收敛到相同的平稳分布。

1.3 通过特征值分解证明

首先，回顾一下特征值和特征向量的定义：

对于一个 $n×n$ 的矩阵$A$，如果存在一个非零向量 $v$ 和一个标量$λ$，使得：
$$
Av = λv
$$
则 $λ$ 被称为$A$的特征值，$v$被称为对应于$λ$的特征向量。

根据Perron-Frobenius定理，对于一个具有非负元素的方阵A：

如果一个$n×n$的矩阵$P$有$n$个线性独立的特征向量，则$P$是可对角化的，即

$$
P = Q\Lambda Q^{-1}
$$

其中，$Q$是由$P$的$n$个线性独立特征向量作为列向量组成的矩阵，$Λ$是一个对角矩阵，其对角线上的元素是对应的特征值。

假设$P$的特征值为 $λ_1, λ_2, …, λ_n$，对应的特征向量为$v_1, v_2, …, v_n$，其中：
$$
Q = \begin{bmatrix}
{v}_1 & {v}_2 & \cdots & {v}_n
\end{bmatrix}
$$

$$
\Lambda = \begin{bmatrix}
\lambda_1 & 0 & \cdots & 0 \newline
0 & \lambda_2 & \cdots & 0 \newline
\vdots & \vdots & \ddots & \vdots \newline
0 & 0 & \cdots & \lambda_n
\end{bmatrix}
$$

其中，根据特征向量的定义，下面两个的式子显然成立：
$$
PQ = P \begin{bmatrix} {v}_1 & {v}_2 & \cdots & {v}_n \end{bmatrix} = \begin{bmatrix} P{v}_1 & P{v}_2 & \cdots & P{v}_n \end {bmatrix} = \begin{bmatrix} \lambda_1{v}_1 & \lambda_2{v}_2 & \cdots & \lambda_n{v}_n \end {bmatrix} \newline
$$
$$
Q\Lambda = \begin{bmatrix} {v}_1 & {v}_2 & \cdots & {v}_n \end{bmatrix} \begin{bmatrix} \lambda_1 & 0 & \cdots & 0 \newline 0 & \lambda_2 & \cdots & 0 \newline \vdots & \vdots & \ddots & \vdots \newline 0 & 0 & \cdots & \lambda_n \end{bmatrix} = \begin{bmatrix} \lambda_1{v}_1 & \lambda_2{v}_2 & \cdots & \lambda_n{v}_n \end {bmatrix}
$$
即：
$$
PQ = Q\Lambda \newline
P = Q\Lambda Q^{-1}
$$
那么：
$$
P^N = (Q\Lambda Q^{-1})^N = QΛ^NQ^{-1} \newline
$$
$$
\Lambda^N = \begin{bmatrix} \lambda_1^N & 0 & \cdots & 0 \newline 0 & \lambda_2^N & \cdots & 0 \newline \vdots & \vdots & \ddots & \vdots \newline 0 & 0 & \cdots & \lambda_n^N\end{bmatrix}
$$