计算科学 - 马尔可夫链转移概率矩阵的高效计算 - 吾爱随笔录

马尔可夫链转移概率矩阵的高效计算

计算科学线性代数矩阵可能性带状矩阵

2021-12-07 03:31:17

考虑一个连续的马尔可夫链 $X=(X_t)$ 在有限状态空间上，让 $Q$ 是（给定的）转换率矩阵。该矩阵非常稀疏，仅在 3 个对角线上具有非零值（因此从每个状态，只能转换到 2 个其他状态）。

让 $P_t$ 是转移概率矩阵，所以 $P_t(j,k) =$ 概率 $(X_t=k|X_0=j)$ .

我的问题是：快速计算 $j$ 第行 $P_1$ ?

求解 Kolmogorov 正向方程给出 $P_t=e^{Qt}$ ，因此一种方法是在 matlab 中显式执行此计算：expm(Q)。但我认为也许有更好的方法，特别是考虑到 $Q$ 而且因为我只对一排感兴趣 $P_1$ . 我正在解决的问题的实际实例很小（例如 120 个状态），但我希望计算速度非常快。

2个回答

计算一个近似值 $P_1=e^Q$ 通常通过矩阵指数的某种多项式展开来完成。不采用泰勒展开式（它收敛太慢），但为了论证，让我假设你这样做并且你近似

P_{1} = e^{Q} \approx \sum_{k = 0}^{N} \frac{1}{k!} Q^{k} = I + Q + \frac{1}{2!} Q^{2} + \frac{1}{3!} Q^{3} + \dots = I + Q (I + \frac{1}{2} Q (I + \frac{1}{3} Q (\dots)))

$P_1 = e^Q \approx \sum_{k=0}^N \frac1{k!} Q^k = I+Q+\frac 1{2!} Q^2 + \frac 1{3!}Q^3 + \cdots = I+Q(I+\frac 12 Q(I+\frac 13 Q(\cdots)))$ 然后记住你得到了

j

$j$ 第行

P_{1}

$P_1$ 通过形成产品

e_{j}^{T} P_{1}

$e_j^T P_1$ 在哪里

e_{j}

$e_j$ 是个

j

$j$ 单位向量

(0, \dots 0, 1, 0, \dots, 0)^{T}

$(0, \ldots 0, 1, 0, \ldots, 0)^T$ 与一个在

j

$j$ 向量的第 th 位。您可以在上面的公式中使用它来计算

e_{j}^{T} P_{1} \approx= e_{j}^{T} + (e_{j}^{T} Q) (I + \frac{1}{2} Q (I + \frac{1}{3} Q (\dots)))

$e_j^T P_1 \approx = e_j^T+(e_j^T Q)(I+\frac 12 Q(I+\frac 13 Q(\cdots)))$ 如果你把这个乘积从左到右相乘，你会发现你所要做的就是形成一个向量（转置）与一个矩阵的乘积。换句话说，您实际上不需要任何矩阵矩阵产品，这些产品在您的情况下会很昂贵，因为您的矩阵

Q

$Q$ 是稀疏的，但权力

Q

$Q$ 会越来越稀疏。最后，使用这种方法，您所需要的只是

O (N)

$O(N)$ 向量矩阵乘积采取扩展至

N

$N$ 订单。

正如我所说，在实践中，人们不会采用泰勒展开，而是采用矩阵指数的其他多项式展开。但是，一般方法将保持不变：将其全部简化为一系列向量矩阵乘积。

在 Moler 和 van Loan 的论文“25 年后”部分（第 13 节，参见 Christian Clason 评论中的链接）中提到的一个软件包是 Roger Sidje 的Expokit，并附有解释该方法的论文。

对于大型稀疏矩阵，将类泰勒多项式应用于 Krylov 子空间，与纯泰勒级数近似相比，获得了具有更尖锐误差界限的矩阵向量运算的优势。

其它你可能感兴趣的问题

上一篇在计算科学领域，智能手机有什么有用的应用程序吗？下一篇PI 的蒙特卡洛近似