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

来自集智百科
跳转到: 导航搜索

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

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


\sum_{j=1}^{N}m_{ij}<1, i\in [0,N]

我们定义基础矩阵(参见投入产出网):


U=I+M+M^2+\cdot\cdot\cdot=(I-M)^{-1}

其中I为单位阵。进一步,设M_{-d}为将M矩阵的第d行全部置为0的矩阵,这样:


M=M_{-d}+\Delta M

Equation (1)



其中:


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

我们定义相应的U-d


U_{-d}=I+M_{-d}+M^2_{-d}+\cdot\cdot\cdot=(I-M_{-d})^{-1}

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

目录

性质1


MU=U-I

证明:

根据U的定义


I=(I-M)U=U-MU

可得。

将矩阵写成具体元素的形式,有:


\sum_k m_{ik}u_{kj}=u_{ij}-\delta_{ij}

其中,


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

性质2


(I-M)U=(I-M_{-d})U_{-d}=I

易证

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

定理1


(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}

证明:

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


U-MU=U-(M_{-d}+\Delta M)U=U_{-d}-M_{-d}U_{-d}

于是,可以得到:


U-U_{-d}=U_{-d}\Delta M U

又根据\Delta M的定义,将\Delta M U展开,可以得到:


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

于是,我们有:


u_{ij}-(U_{-d})_{ij}=(U_{-d})_{id}(u_{dj}-\delta_{dj})

Equation (2)


在上式中,如果令j=d,则得到:


u_{id}-(U_{-d})_{id}=(U_{-d})_{id}(u_{dd}-1)

所以:


(U_{-d})_{id}=\frac{u_{id}}{u_{dd}}

代回到(2),有:


u_{ij}-(U_{-d})_{ij}=\frac{u_{id}}{u_{dd}}(u_{dj}-\delta_{dj})

整理,即得到:


(U_{-d})_{ij}=u_{ij}-\frac{u_{id}}{u_{dd}}u_{dj}-\frac{u_{id}}{u_{dd}}\delta_{dj}

推论1

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


(U_{-j}^2)_{ij}=\frac{(U^2)_{ij}}{u_{jj}}-\frac{u_{ij}}{u_{jj}^2}(U^2)_{jj}+\frac{u_{ij}}{u_{jj}}


证明:

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

推论2


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


证明:

利用MU=U^2-U以及M_{-j}U_{-j}^2=U_{-j}^2-U_{-j},代入推论1以及定理1,即可得证。

个人工具
名字空间
操作
导航
工具箱