On Determining the Convergence Rate of an Infinite Product of Stochastic Matrices

技术摘要：关于随机矩阵无穷乘积收敛速率的确定

问题陈述
本文研究了随机矩阵无穷乘积的分析问题，这是分布式控制、估计和优化中共识协议（consensus protocols）的一个基本组成部分。虽然对于特定的“收敛集”（如 scrambling 矩阵、Sarymsakov 矩阵），此类乘积收敛到秩为一的矩阵这一事实已得到充分证实，但确定其收敛速率仍然具有挑战性。具体而言，作者调查了是否可以使用次乘性共识半范数（submultiplicative consensus seminorms）来统一界定给定收敛集中所有矩阵的收敛速率。一个关键问题是：是否存在一个单一的半范数，使得该收敛集中的每个矩阵在该半范数下都是收缩的（即半范数值严格小于 1），从而保证指数级收敛。

方法论
作者采用了共识半范数（consensus seminorms）的框架，该范数定义在具有相等行和的矩阵空间 $M_{n \times n}$ 上。一个共识半范数 $|\cdot|$ 满足当 $M = \mathbf{1}c$（即秩为一的矩阵）时 $|M|=0$。其分析依赖于：

1. 次乘性（Submultiplicativity）： 性质 $|M_1 M_2| \leq |M_1||M_2|$，它将半范数值与收敛速率联系起来。
2. 联合谱半半径（Joint Spectral Semiradius）： 一种对联合谱半径的新型适配，通过使用共敛半范数而非标准矩阵范数来刻画无穷乘积的渐近行为。
3. 拓扑论证： 利用特定矩阵集（如正随机矩阵）在所有随机矩阵空间中的稠密性，来推导关于存在统一收缩半范数的矛盾结论。
4. Hajnal 性质： 利用已知结果，即非 scrambling 矩阵与特定随机矩阵的乘积可能不收敛。

主要贡献与结果

1. 通用收敛集不存在统一收缩半范数
本文通过完善先前的研究结果，证明并非所有的收敛集都允许存在一个单一的次乘性共敛半范数，使得其中所有矩阵均为收缩矩阵。

• 定理 1： 对于 $n > 2$，不存在次乘性共敛半范数 $|\cdot|$ 使得集合 $R$（具有正对角线且具有根图的随机矩阵）或集合 $K$（Sarymsakov 矩阵）中的所有 $S$ 满足 $|S| < 1$。
• 定理 3： 如果收敛集 $C$ 在所有随机矩阵 $S_{n \times n}$ 中是稠密的，且存在一个半范数使得所有 $S \in C$ 都是收缩的，那么 $C$ 必须是 scrambling 矩阵的子集。
• 启示： 由于 $R$ 和 $K$ 在 $S_{n \times n}$ 中是稠密的但包含非 scrambling 矩阵，因此没有任何单一的半范数可以界定这些集合中所有矩阵的收敛速率。这与 scrambling 矩阵集合 ($S$) 以及具有弱连通图的双随机矩阵集合 ($D$) 形成对比，后者确实存在此类半范数（例如，遍历系数或第二大奇异值）。

2. 有限乘积收缩性质
本文确立了虽然紧致收敛集中的单个矩阵在给定半范数下可能不是收缩的，但它们的有限乘积最终会变为收缩的。

• 推论 2： 对于每个紧致收敛集 $C$ 和每个次乘性共敛半范数，存在一个有限整数 $k$，使得来自 $C$ 的任意 $k$ 个矩阵的乘积是收缩的（即 $|S_k \cdots S_1| < 1$）。
• 这一结果将已知关于 scrambling 矩阵的性质（即有限乘积长度保证了 scrambling 性质）推广到了更一般的共敛半范数。

3. 联合谱半半径与收敛速率
作者引入了联合谱半半径 $\sigma(C)$，其定义为长度为 $t$ 的乘积的半范数的 $t$ 次方根的上确界之极限。

• 定理 4： 一个紧致集 $C$ 是收敛的，当且仅当 $\sigma(C) < 1$。此外，如果 $\sigma(C) < 1$，则收敛速率是指数级的，由 $\delta^t$ 界定，其中 $\delta > \sigma(C)$。
• 这提供了一种理论机制，即使单个矩阵不是收缩的，只要联合谱半半径小于 1，就可以界定收敛速率。

意义与主张
本文声称澄清了使用次乘性半范数来界定分布式共识中收敛速率的局限性。

• 它表明，拥有单一收缩半范数的“优良”性质并非普适的；对于 $n > 2$ 时的 $R$ 和 $K$ 等重要类别，这一性质失效。
• 它强调了利用单一半范数确定收敛速率的能力，与矩阵集的拓扑密度以及 scrambling 性质密切相关。
• 本文指出，虽然单个矩阵可能不是收缩的，但“联合”行为（由联合谱半半径捕捉）确保了有限乘积最终会收缩，从而为一般收敛集提供了速率界定的途径。
• 作者最后指出了一些开放性问题：特别是，对于所有半范数，有限乘积收缩性质（推论 2）中的 $k$ 是否可以由维度 $n$ 的函数来界定，或者是否存在某些半范数使得这种界限不存在。