薄荷：创建页面，内容为“本文所说的马尔科夫链特指流网络的马尔科夫链，即根据流矩阵F（其中第0个节点表示源，第N+1个节点表示列）经过行归一…”

2020-10-15T16:22:36Z

创建页面，内容为“本文所说的马尔科夫链特指流网络的马尔科夫链，即根据流矩阵F（其中第0个节点表示源，第N+1个节点表示列）经过行归一…”

新页面

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

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

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

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

<math>
U=I+M+M^2+\cdot\cdot\cdot=(I-M)^{-1}
</math>

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

<math>
M=M_{-d}+\Delta M
</math>
{{align|right|'''Equation (1)'''}}

其中：

<math>
\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>
U_{-d}=I+M_{-d}+M^2_{-d}+\cdot\cdot\cdot=(I-M_{-d})^{-1}
</math>

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

===性质1===

<math>
MU=U-I
</math>

证明：

根据U的定义

<math>
I=(I-M)U=U-MU
</math>

可得。

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

<math>
\sum_k m_{ik}u_{kj}=u_{ij}-\delta_{ij}
</math>

其中，

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

===性质2===

<math>
(I-M)U=(I-M_{-d})U_{-d}=I
</math>

易证

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

===定理1===

<math>
(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>
U-MU=U-(M_{-d}+\Delta M)U=U_{-d}-M_{-d}U_{-d}
</math>

于是，可以得到：

<math>
U-U_{-d}=U_{-d}\Delta M U
</math>

又根据<math>\Delta M</math>的定义，将<math>\Delta M U</math>展开，可以得到：

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

于是，我们有：

<math>
u_{ij}-(U_{-d})_{ij}=(U_{-d})_{id}(u_{dj}-\delta_{dj})
</math>
{{align|right|'''Equation (2)'''}}

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

<math>
u_{id}-(U_{-d})_{id}=(U_{-d})_{id}(u_{dd}-1)
</math>

所以：

<math>
(U_{-d})_{id}=\frac{u_{id}}{u_{dd}}
</math>

代回到(2)，有：

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

整理，即得到：

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

====推论1====

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

<math>
(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>
\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>MU=U^2-U</math>以及<math>M_{-j}U_{-j}^2=U_{-j}^2-U_{-j}</math>，代入推论1以及定理1，即可得证。

[[category:流网络]]
[[category:旧词条迁移]]

马尔科夫链删除节点的性质 - 版本历史

薄荷：创建页面，内容为“本文所说的马尔科夫链特指流网络的马尔科夫链，即根据流矩阵F（其中第0个节点表示源，第N+1个节点表示列）经过行归一…”