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

来自集智百科 - 伊辛模型
跳到导航 跳到搜索

本文所说的马尔科夫链特指流网络的马尔科夫链,即根据流矩阵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]


证明:

将U2展开成矩阵的元素,并将定理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,即可得证。