EE6223-P2-4-离散时间平均系统

引入

在掌握了矩阵理论和图论的基础工具后，我们现在要将视角转回到第一章曾介绍过的“平均模型”。第一章中的三个例子（社会学中的意见形成、传感器网络中的数据融合、机器人编队控制）虽然应用场景大相径庭，但在数学本质上，它们都可以被抽象为一个经典的离散时间动态系统。

回顾第一章中的状态转移式子：

$$x(k + 1) = Ax(k)$$

• $x(k)$：代表系统在时刻 $k$ 的状态向量。比如网络中各个节点的温度读数，或者多智能体系统中各个机器人的位置。

• $A$：是状态转移矩阵。它是行随机矩阵 (row-stochastic matrix)。

既然每个节点都在做局部平均，那么随着时间推移（$k \to \infty$），整个系统最终会演变成什么样？这就是系统的渐近行为 (asymptotic behavior)。这一章我们将基于 Perron-Frobenius 理论和代数图论来给出全面的收敛性结论。核心观点是：网络的拓扑结构决定了系统的宏观功能

我们主要关注以下几个维度：

1. 达成一致 (Emergence of consensus)： 如果网络对应的矩阵是素矩阵 (primitive matrices)，或者它是可约的但只有一个“汇点” (single sink，即全局唯一的吸收连通分支)，那么所有节点的状态最终会收敛到同一个值。
2. 渐近分歧 (Asymptotic disagreement)： 如果网络存在多个“汇点” (multiple sinks)，意味着网络中有几个互不妥协的小团体，那么系统最终无法达成全局一致，而是会收敛到不同的状态（形成聚类或分歧）。
3. 替代证明方法： 除了图论，我们还会介绍通过特定的“遍历性系数 (ergodicity coefficients)”来证明系统收敛性的等效方法。
4. 经典模型： 我们会具体分析几种常见的行随机矩阵模型，例如等邻居模型 (Equal-neighbor) 和常用于马尔可夫链的 Metropolis-Hastings 模型。
5. 中心性 (Centrality)： 最后，结合网络科学，我们会探讨在达成一致的过程中，网络中的哪些节点拥有最大的“话语权”或影响力。

渐进共识的平均系统

引入

例子1:无线传感器网络 (WSN)

首先来看一个例子：有权有向图 $G_{\text{wsn}}$，有 4 个传感器节点。节点都有自环（代表保留自身过去的状态）。

它的邻接矩阵是：

$$A_{wsn} = \begin{bmatrix} \frac{1}{2} & \frac{1}{2} & 0 & 0 \\ \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\ 0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ 0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \end{bmatrix}$$

收敛性分析：为什么会稳定？

图论条件：观察图 $G_{\text{wsn}}$，它是强连通的 (Strongly connected)（任意两个节点之间都有路径）并且是非周期的 (Aperiodic)（因为存在自环）。

由图论条件推导出，邻接矩阵 $A_{\text{wsn}}$ 是本原矩阵 (Primitive matrix)。

核心定理 (Perron-Frobenius Theorem)：对于本原的行随机矩阵，它有一个极其重要的性质——特征值 1 是简单且严格占优的（其他所有特征值的模都严格小于 1）。

因为除了 1 之外的特征值在不断相乘（取幂）的过程中都会衰减趋近于 0，所以矩阵的极限 $\lim_{k \to \infty} A_{\text{wsn}}^k$ 会收敛到一个秩为 1 的矩阵 $\mathbb{1}_4 w^\top$：

$$\lim_{k \to \infty} A_{\text{wsn}}^k=\mathbb{1}_4 w^\top$$

$w$ 是对应于特征值 1 的左主特征向量 (Left dominant eigenvector)。

收敛到哪里？

渐近一致 (Asymptotic consensus)：我们将极限矩阵代入状态方程求极限，发现所有节点最终的值都会变成一个相同的标量：$w^\top x(0)$。这就是一致性状态。

$$\lim_{k \to \infty} x(k) = \lim_{k \to \infty} A_{\text{wsn}}^k x(0) = (\mathbf{1}_4 w^\top) x(0) = (w^\top x(0)) \mathbf{1}_4 = \begin{bmatrix} w^\top x(0) \\ \vdots \\ w^\top x(0) \end{bmatrix}$$ $$w^\top x(0)=\frac{1}{6}x_1(0) + \frac{1}{3}x_2(0) + \frac{1}{4}x_3(0) + \frac{1}{4}x_4(0)$$

从这个式子可以看出，对于收敛的最终值，各节点的初始状态在最终结果中所占的“话语权”是不一样的。节点 2 的权重最大 (1/3)。

物理直觉：为什么节点 2 影响最大？如果看图 $G_{\text{wsn}}$，你会发现节点 2 向其他节点输出了大量信息，且权重很高，它在网络中处于相对中心的“影响力”位置。因为矩阵仅仅是行随机，而不是列随机，所以网络不能保证能量/权重的绝对守恒，最终只能达到“渐近一致”，而无法达到精确的“平均一致”。

例子2:完美对称带来“平均一致性”

当网络结构像图像下图$G_{\text{pursuit}}$那样完美对称时，会发生什么？

$$A_{pursuit}= \begin{bmatrix} \frac{1}{2} & \frac{1}{2} & \cdots & 0 & 0 \\ 0 & \frac{1}{2} & \ddots & \vdots & 0 \\ \vdots & \ddots & \ddots & \ddots & \vdots \\ 0 & \ddots & \ddots & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & 0 & \cdots & 0 & \frac{1}{2} \end{bmatrix}$$

双随机矩阵 (Doubly Stochastic Matrix)：图 $G_{\text{pursuit}}$ 是权重平衡 (Weight-balanced) 的。反映在矩阵 $A_{\text{pursuit}}$ 上，你可以观察到它不仅每一行的和为 1（行随机），每一列的和也为 1（列随机）。

因为矩阵是列随机的，定理表明其对应于特征值 1 的左特征向量 $w$ 变成了元素全相等的向量。

$$\lim_{k \to \infty} x(k) = \text{average}(x(0))\mathbb{1}_n$$

所有的节点最终不仅会达成共识，而且它们收敛到的那个值，精确等于所有人初始状态的算术平均值。

例子3:领导者与追随者网络

前两个例子都有一个严苛的前提：图是强连通的。但如果不强连通呢？系统还能达成一致吗？

作为第三个例子，我们考虑一个可约的行随机矩阵，其相关的有向图不是强连通的。

这张图的凝聚图如下：

可以看到，对于${1,2,3,5,7,8,9,10}$，从任意一个节点出发，都存在一条有向路径可以最终抵达。该有向图具有一个全局可达节点的非周期子图，只要满足上述“全局可达”的条件，矩阵的特征值 1 依然是简单且严格占优的。这就从数学上保证了系统最终一定会收敛，不会震荡发散。

还可以看到，对于节点4和6，它的下一个状态只从超级节点0寻求建议，它是一个“追随者”。而超级节点0完全不从他们俩那边寻求建议，它是一个“顽固节点”或“领导者”。这种矩阵被命名为不可分矩阵 (Indecomposable)。

我们再使用一个简化一点的例子：节点1存在权重为1的自环，节点2存在1/2权重的自环，权重1/2的路径指向节点1。它的平均算法类似于如下：

$$x_1(k+1) = x_1(k)$$ $$x_2(k+1) = \frac{1}{2}x_1(k) + \frac{1}{2}x_2(k)$$

随着时间推移，节点 2 最终会被节点 1 完全同化，两者达成一致。但此时的“共识值”是由领导者 $x_1$ 100% 决定的，追随者 $x_2$ 的初始状态被完全遗忘了。

总结

总结一下这三个例子：

• 强连通 + 行随机 = 达成共识（意见领袖主导）。
• 强连通 + 双随机 (Weight-balanced) = 达成平均共识（绝对民主）。
• 非强连通但有全局可达根节点 (Indecomposable) = 达成共识（领导者/源头主导，追随者附和）。

行随机矩阵实现渐近一致性的条件

假设 $A$ 是一个具有 全局可达非周期强联通的子机构 的行随机矩阵，$G$ 是它对应的有向图。下列陈述等价：

1. 矩阵 $A$ 必须有一个简单的特征值 $1$（即单根），并且其他所有特征值 $\mu$ 都必须严格落在单位圆内（$|\mu| < 1$）。
2. 当时间 $k$ 趋向于无穷大时，状态转移矩阵 $A^k$ 会收敛成一个非常特殊的矩阵 $\mathbf{1}_n w^\top$。其中 $w$ 是一个非负向量，且总和为 1。
3. 图 $G$ 包含一个全局可达节点，并且由这些全局可达节点组成的子图是非周期的。

如果任何一条得到满足，则矩阵 A 被称为不可分解矩阵（indecomposable），进一步满足：

• $w \geq 0$ 是 $A$ 的左主特征向量（left dominant eigenvector），且当且仅当节点 $i$ 全局可达时，$w_i > 0$
• $x(k+1) = A x(k)$ 其解满足： $\lim_{k \to \infty} x(k) = (w^T x(0)) 1_n$
• 特例，双随机矩阵：如果矩阵 $A$ 不仅是行随机，还是双随机的（列和也为 1），那么 $w = \frac{1}{n}\mathbf{1}_n$。大家权重平分，最终结果就是所有初始值的算术平均。这在拓扑上通常要求图是强连通且权重平衡的。

定理的证明：

1.如果一个系统最终能收敛（2），那么它的网络图里必然存在全局可达的非周期子图（3）。

• 既然系统收敛，即 $\lim_{k\to\infty} A^k = \mathbf{1}_n w^\top$，并且我们知道权重向量 $w$ 的和为 1，那么 $w$ 里必然至少有一个元素大于 0（假设是第 $j$ 个元素 $w_j > 0$）。
• 这就导致极限矩阵的第 $j$ 列全是正数。
• 这意味着什么？意味着只要经过足够长的时间 $K$，矩阵 $A^K$ 的第 $j$ 列全是正数。翻译成图论语言就是：从网络中的任意一个节点出发，都存在一条长度为 $K$ 的路径可以到达节点 $j$。
• 这就是“全局可达”最硬核的数学证明！同时对角线元素收敛到正数，也证明了子图的非周期性。

2.假设图里有全局可达的节点（汇点/领导者）（3）成立，证明必须有一个简单的特征值 $1$（1）和状态转移矩阵 $A^k$ 会收敛成一个非常特殊的矩阵 $\mathbf{1}_n w^\top$（2）

为了方便计算，老师做了一个置换（Permutation）。把所有“被大家请教的领导者”（共 $n_1$ 个）排在前面，把所有“只问别人不被问的追随者”（共 $n_2$ 个）排在后面。

排好座位后，状态转移矩阵 $A$ 就变成了一个下分块三角形矩阵：

$$A = \begin{bmatrix} A_{11} & 0 \\ A_{21} & A_{22} \end{bmatrix}$$

• 领导者群体的更新： $x_1(k+1) = A_{11}x_1(k)$
• 追随者群体的更新： $x_2(k+1) = A_{21}x_1(k) + A_{22}x_2(k)$

领导者 $A_{11}$ 为什么能达成共识？

因为 $A_{11}$ 对应的就是那个“全局可达的非周期强连通子图”。在代数上，这种矩阵被称为素矩阵（Primitive Matrix）。它一定会自己完美收敛到一个共识状态 $\lim_{k\to\infty} A_{11}^k = \mathbf{1}_{n_1} w_1^\top$。

因为追随者必然要向领导者寻求建议（即 $A_{21} \neq 0$），而 $A$ 矩阵每行的总和必须是 1（行随机）。既然分了一部分权重给 $A_{21}$，那么 $A_{22}$ 这一块的每一行加起来就严格小于 1 了！

这个矩阵就是之前提到的行次随机矩阵（Row-substochastic matrix）。它的谱半径（最大特征值的绝对值） $\rho(A_{22}) < 1$。因为追随者自身的能量会耗散（$\rho(A_{22}) < 1$），所以追随者的最终状态完全被领导者 $x_1$ 牵着鼻子走。

$$\lim_{k \to \infty} \begin{bmatrix} A_{11} & 0 \\ A_{21} & A_{22} \end{bmatrix}^k = \mathbb{1}_n \begin{bmatrix} w_1 \\ 0_{n_2} \end{bmatrix}^{\top}$$

对于权重向量，领导者部分是 $w_1$，追随者部分是 $0$。

渐进分歧的平均系统

如果一个网络中没有全局可达的节点（globally reachable nodes），也就是说信息无法传递给所有人，那么这个网络最终就会“分裂”。在图论中，这就意味着它的缩合图（Condensation digraph）有多个“汇点”（Sinks）。

引入案例：Sampson修道院网络

这是一个一个著名的社会学真实数据集。在这个修道院的18个修道士中，他们的社交关系形成了一个有向图。经过化简（缩合），我们发现这个网络里出现了两个 Sinks（Sink 1 和 Sink 2）。

这就是两个固执的小团体。他们内部聊得很火热，但绝不听对方的话。可想而知，随着时间推移，这两拨人肯定会各自形成自己的统一意见，整个就会出现“渐近不一致”（两种不同的声音并存）。

渐进分歧的数学性质

假设矩阵 $A$ 是一个行随机矩阵，它对应的网络有 $n_s \ge 2$ 个汇点。以下三个陈述是等价的：

1. (A1) 矩阵特征值 1 的代数重数等于 $n_s$（有几个小团体，就有几个特征值 1），其他特征值的绝对值都小于 1。
2. (A2) 矩阵 $A$ 是半收敛的（说明系统最终会稳定下来，不会无限震荡）。
3. (A3) 每一个小团体（Sink）内部都是非周期的（aperiodic）。

如果上述条件满足，那么系统会有 $n_s$ 个左特征向量 $w^p$。

• 当且仅当节点 $i$ 属于小团体 $p$，$ w_i^p > 0, 1_n^Tw_p=1$。这说明：只有小团体内部的人，才会对这个小团体的最终意见产生实质性影响。
• 给定迭代方程 $x(k+1) = A x(k)$，初始条件为 $x(0)$，其解满足：

$$\lim_{k \to \infty} x_i(k) = \begin{cases} (w^p)^\top x(0), & \text{若节点 $i$ 属于汇点 (sink) $p$}\\ \sum_{p=1}^{n_s} z_{i,p} \left( (w^p)^\top x(0) \right), & \text{否则} \end{cases}$$

其中 $z_{i,p}, \, p \in \{1, \ldots, n_s\}$ 为凸组合系数 (convex combination coefficients)，并且当且仅当存在从节点 $i$ 到汇点 $p$ 的有向路径 时，$z_{i,p} > 0$。

解释：

$$\lim_{k \to \infty} x_i(k) = (w^p)^\top x(0) $$的物理意义是：如果节点 $i$ 属于第 $p$ 个汇点，那么它的最终状态只取决于**这个汇点内部成员的初始状态 $x(0)$**。它完全不受网络中其他汇点的影响。 $$ \lim_{k \to \infty} x_i(k) = \sum_{p=1}^{n_s} z_{i,p} \left( (w^p)^\top x(0) \right) $$的物理意义是：括号里的 $(w^p)^\top x(0)$ 它是第 $p$ 个汇点的最终共识值。 式前面的求和号 $\sum$ 表示，节点 $i$ 的最终状态，是**所有 $n_s$ 个汇点最终状态的混合体**。 **凸组合系数 $z_{i,p}$：** 这是一个大于等于 0 且总和为 1 的权重值。它代表了**第 $p$ 个汇点对节点 $i$ 的“洗脑/影响程度”**。 ## 一个例子来证明性质 $x_1$ 和 $x_2$ 是两个 Sink（两大门派），$x_3$ 是一个连接到它俩的普通节点（吃瓜群众）。  它的邻接矩阵是：$$

A =
\begin{bmatrix}
A_{11} & 0 & 0 \\
0 & A_{22} & 0 \\
A_{31} & A_{32} & A_{33}
\end{bmatrix}

$$这是块下三角矩阵，$A_{11}$ 和 $A_{22}$ 各自独立（它们那一行只有自己，表示它们只听自己的）。后一行的 $x_3$ 则包含了 $A_{31}, A_{32}, A_{33}$，表示 $x_3$ 会同时听取 $x_1$、$x_2$ 甚至自己过去的状态。 ### 计算两大门派$x_1,x_2$$$

x_1(k+1) = A_{11}x_1(k),

x_2(k+1) = A_{22}x_2(k),

x_3(k+1) = A_{31}x_1(k) + A_{32}x_2(k) + A_{33}x_3(k)

$$$x_1$ 最终变成了 $w_1^T x_1(0)$，$x_2$ 最终变成了 $w_2^T x_2(0)$。$$

\lim_{k \to \infty} x_1 (k) = (w_1^{\mathrm{T}} x_1(0)) \mathbf{1}_{n_1},
\quad
\lim_{k \to \infty} x_2(k) = (w_2^{\mathrm{T}} x_2(0)) \mathbf{1}_{n_2}

$$### 计算追随者$x_3$ $x_1$ 和 $x_2$ 作为汇点（Sinks），它们各自内部达到了共识。那么夹在中间的 $x_3$ 最终的状态到底怎么算？ 关注矩阵 $A_{33}$，它代表了节点 $x_3$ 对自身历史状态的依赖。因为 $x_3$ 是一个瞬态节点（最终会被别人同化），它的谱半径 $\rho(A_{33}) < 1$。这意味着 $x_3$ 无法“自给自足”地维持自己的初始意见，它自身的固执程度在迭代中会逐渐衰减。正因为如此，矩阵 $(I_{n_3} - A_{33})$ 是可逆的（非奇异的）。 我们对 $x_3$ 的下列状态方程两边同时取 $k \to \infty$ 的极限。$$

x_3(k+1) = A_{31}x_1(k) + A_{32}x_2(k) + A_{33}x_3(k)

$$因为系统最终会稳定，$x_3(k+1)$ 和 $x_3(k)$ 都会趋近于同一个极限值 $\lim x_3(k)$。$$

\lim_{k \to \infty} x_3(k+1) = \lim_{k \to \infty} x_3(k)

$$也就是$\lim_{k \to \infty} x_3(k+1) = \lim_{k \to \infty} \left( A_{31}x_1(k) + A_{32}x_2(k) + A_{33}x_3(k) \right)$可以写成：$$

\lim_{k \to \infty} x_3(k) = A_{31}\lim_{k \to \infty}x_1(k) + A_{32}\lim_{k \to \infty}x_2(k) + A_{33}\lim_{k \to \infty}x_3(k)

$$移项：$$

\lim_{k \to \infty} x_3(k) - A_{33}\lim_{k \to \infty}x_3(k) = A_{31}\lim_{k \to \infty}x_1(k) + A_{32}\lim_{k \to \infty}x_2(k)

(I_{n_3} - A_{33}) \lim_{k \to \infty} x_3(k) = A_{31}\lim_{k \to \infty}x_1(k) + A_{32}\lim_{k \to \infty}x_2(k)

$$再次移项：$$

\lim_{k \to \infty} x_3(k) = (I_{n_3} - A_{33})^{-1} \left( A_{31}\lim_{k \to \infty}x_1(k) + A_{32}\lim_{k \to \infty}x_2(k) \right)

$$这就证明了$\sum_{p=1}^{n_s} z_{i,p} \left( (w^p)^\top x(0) \right)$中的$(w^p)^\top x(0)$ 由于A是行随机的,因此有：$$

A_{31}\mathbf{1}_{n_1} + A_{32}\mathbf{1}_{n_2} + A_{33}\mathbf{1}_{n_3} = \mathbf{1}_{n_3}

$$把包含 $A_{33}$ 的项移到右边，提取公因式得到 $(I_{n_3} - A_{33})\mathbb{1}_{n_3}$。然后再把 $(I_{n_3} - A_{33})^{-1}$ 乘过去，就得到了 ：$$

\mathbb{1}_{n_3} = (I_{n_3} - A_{33})^{-1}A_{31}\mathbb{1}_{n_1} + (I_{n_3} - A_{33})^{-1}A_{32}\mathbb{1}_{n_2}

$$
这就证明了凸组合系数 $z_{i,p}$是一个大于等于 0 且总和为 1 的权重值。

注意：收敛 (Convergence) 绝对不等于 共识 (Consensus)！ 在这个多汇点网络中，所有节点的状态最终都停止了跳动（收敛了），但大家并没有统一意见（没达成共识）。汇点之外的节点，其最终命运完全被汇点所“绑架”。

总结