马尔科夫链删除节点的性质

本文所说的马尔科夫链特指流网络的马尔科夫链，即根据流矩阵F（其中第0个节点表示源，第N+1个节点表示列）经过行归一化而得到的马尔科夫链。其中第i行第j个元素表示粒子从i节点到j节点的跳转概率。其中第N+1行因为表示汇可以是全部为0的行向量。

我们设去除掉第N+1行和N+1列的马尔科夫矩阵为M，由于原始的马尔科夫矩阵满足行和为1，所以M矩阵满足：

[math]\displaystyle{ \sum_{j=1}^{N}m_{ij}\lt 1, i\in [0,N] }[/math]

我们定义基础矩阵（参见投入产出网）：

[math]\displaystyle{ U=I+M+M^2+\cdot\cdot\cdot=(I-M)^{-1} }[/math]

其中I为单位阵。进一步，设[math]\displaystyle{ M_{-d} }[/math]为将M矩阵的第d行全部置为0的矩阵，这样：

[math]\displaystyle{ M=M_{-d}+\Delta M }[/math] 模板:Align

其中：

[math]\displaystyle{ \Delta M=\left\{\begin{array}{ll} m_{i,j} & \mbox {if } i=d, \\ 0 & \mbox {if } i \neq d\end{array}\right. }[/math]

我们定义相应的U_-d

[math]\displaystyle{ U_{-d}=I+M_{-d}+M^2_{-d}+\cdot\cdot\cdot=(I-M_{-d})^{-1} }[/math]

根据这些定义，我们可以得到马尔科夫矩阵M，U的如下若干性质：

性质1

[math]\displaystyle{ MU=U-I }[/math]

证明：

根据U的定义

[math]\displaystyle{ I=(I-M)U=U-MU }[/math]

可得。

将矩阵写成具体元素的形式，有：

[math]\displaystyle{ \sum_k m_{ik}u_{kj}=u_{ij}-\delta_{ij} }[/math]

其中，

[math]\displaystyle{ \delta_{ij}=\left\{\begin{array}{ll} 1 & \mbox {if } i=j, \\ 0 & \mbox {if } i \neq j\end{array}\right. }[/math]

性质2

[math]\displaystyle{ (I-M)U=(I-M_{-d})U_{-d}=I }[/math]

易证

由性质2，我们可以将U和U_-d中的元素联系起来，具体地，我们有如下定理

定理1

[math]\displaystyle{ (U_{-d})_{ij}=u_{ij}-(U_{-d})_{id}u_{dj}=u_{ij}-\frac{u_{id}}{u_{dd}}u_{dj}-\frac{u_{id}}{u_{dd}}\delta_{dj} }[/math]

证明：

首先，由性质2，和公式(1)定义，我们有：

[math]\displaystyle{ U-MU=U-(M_{-d}+\Delta M)U=U_{-d}-M_{-d}U_{-d} }[/math]

于是，可以得到：

[math]\displaystyle{ U-U_{-d}=U_{-d}\Delta M U }[/math]

又根据[math]\displaystyle{ \Delta M }[/math]的定义，将[math]\displaystyle{ \Delta M U }[/math]展开，可以得到：

[math]\displaystyle{ U_{-d}(\Delta M U)_{ij}=(U_{-d})_{id}\sum_k m_{dk}u_{kj}=(U_{-d})_{id}(u_{dj}-\delta_{dj}) }[/math]

于是，我们有：

[math]\displaystyle{ u_{ij}-(U_{-d})_{ij}=(U_{-d})_{id}(u_{dj}-\delta_{dj}) }[/math] 模板:Align

在上式中，如果令j=d，则得到：

[math]\displaystyle{ u_{id}-(U_{-d})_{id}=(U_{-d})_{id}(u_{dd}-1) }[/math]

所以：

[math]\displaystyle{ (U_{-d})_{id}=\frac{u_{id}}{u_{dd}} }[/math]

代回到(2)，有：

[math]\displaystyle{ u_{ij}-(U_{-d})_{ij}=\frac{u_{id}}{u_{dd}}(u_{dj}-\delta_{dj}) }[/math]

整理，即得到：

[math]\displaystyle{ (U_{-d})_{ij}=u_{ij}-\frac{u_{id}}{u_{dd}}u_{dj}-\frac{u_{id}}{u_{dd}}\delta_{dj} }[/math]

推论1

由该定理可以得到很多推论，例如第一个推论为：

[math]\displaystyle{ (U_{-j}^2)_{ij}=\frac{(U^2)_{ij}}{u_{jj}}-\frac{u_{ij}}{u_{jj}^2}(U^2)_{jj}+\frac{u_{ij}}{u_{jj}} }[/math]

证明：

将U²展开成矩阵的元素，并将定理1中的公式代入即得。

推论2

[math]\displaystyle{ \frac{1}{u_{ij}}\left[(MU^2)_{ij}-u_{jj}(M_{-j}U^2_{-j})_{ij}\right]=\frac{(MU^2)_{jj}}{u_{jj}} }[/math]

证明：

利用[math]\displaystyle{ MU=U^2-U }[/math]以及[math]\displaystyle{ M_{-j}U_{-j}^2=U_{-j}^2-U_{-j} }[/math]，代入推论1以及定理1，即可得证。