⚡ electrical engineering

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

This paper investigates the convergence rates of infinite products of stochastic matrices within convergent sets by utilizing submultiplicative seminorms, demonstrating that while individual matrices are not always contractions in a single seminorm, finite products of matrices from any compact convergent set eventually become contractions, thereby establishing bounds on convergence speed and highlighting limitations of this method for certain matrix classes.

Original authors: Ron Ofir, A. Stephen Morse

Published 2026-07-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ron Ofir, A. Stephen Morse

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a group of friends trying to agree on a single decision, like picking a movie to watch. They keep talking to each other in rounds. In the world of mathematics, this "talking" is modeled by stochastic matrices (think of them as rulebooks for how information flows between people).

The paper by Ron Ofir and A. Stephen Morse asks two big questions about this process:

Will they ever actually agree? (Does the infinite conversation converge to a single answer?)
How fast will they agree? (Is it a quick agreement or a slow, dragging debate?)

Here is a breakdown of their findings using simple analogies.

The "Speedometer" Problem

Mathematicians have a tool called a seminorm. You can think of this as a speedometer or a thermometer for the group's disagreement.

If the reading is less than 1, the group is "shrinking" their disagreement. They are getting closer to an agreement.
If the reading is 1 or higher, they might stay stuck in an argument forever.

For some specific types of groups (mathematicians call these "scrambling matrices" or "doubly stochastic matrices"), there is a universal speedometer. No matter which specific rulebook (matrix) the group uses, if they are in this category, the speedometer always reads less than 1. This means we can easily predict they will agree, and we can calculate exactly how fast.

The Big Discovery: One Size Does Not Fit All

The authors investigated a larger, more complex group of friends (called set R and set K). These groups have rules like "everyone must listen to at least one person" or "everyone has a positive opinion of themselves." We know these groups will eventually agree.

However, the paper proves a surprising negative result:
There is no single universal speedometer that works for every member of these larger groups.

The Analogy: Imagine trying to measure the speed of every car in a massive city using just one specific type of radar gun. For sports cars, it works perfectly. But for this larger group of vehicles (trucks, bicycles, and sports cars), the radar gun fails. Sometimes it says "slow" when the car is actually fast, or it breaks down entirely.
The Consequence: Because there is no single tool that says "everyone is shrinking their disagreement," we cannot easily calculate the speed of convergence for these general groups using this specific method. The paper proves that for the group with "positive diagonals and a rooted graph" (a specific type of connected network), you simply cannot find one mathematical ruler that measures all of them as "shrinking."

The "Teamwork" Solution: Wait for a Few Rounds

If one tool doesn't work for a single step, maybe it works for a team of steps?

The paper offers a second, positive discovery. Even if a single matrix (a single round of conversation) doesn't look like a "shrinking" force on its own, if you take a small group of them (say, $k$ matrices) and multiply them together, the result will be a shrinking force.

The Analogy: Imagine a single step in a dance might not move you toward the center of the room. But if you take three specific steps in a row, you are guaranteed to be closer to the center.
The Result: The authors prove that for any compact (finite/bounded) group of these matrices, there is a magic number $k$ . If you look at any sequence of $k$ matrices multiplied together, they will act as a contraction (they will shrink the disagreement).
Why this matters: This means that even if we can't measure the speed of a single step, we can measure the speed of a "chunk" of steps. This allows mathematicians to still bound the convergence rate, just by looking at slightly longer timeframes.

Summary of the Paper's Claims

The Bad News: For some very common types of consensus networks (specifically those with positive diagonals and a rooted graph), you cannot find a single mathematical tool (submultiplicative seminorm) that proves every single matrix in the set is "shrinking" the disagreement. Therefore, you can't use that specific tool to determine the convergence rate for the whole group.
The Good News: Even if individual steps don't shrink the disagreement, a finite number of steps ( $k$ ) taken together always do.
The Open Question: We know this "magic number" $k$ exists, but we don't yet know if there is a universal formula for $k$ that works for every possible type of seminorm, or if there are weird cases where you might need an infinitely long chain of steps to see the shrinking effect.

In short: The paper tells us that while we can't always use a "one-size-fits-all" ruler to measure how fast a group agrees, we can always find a "group ruler" that works if we look at a few rounds of conversation at a time.

Technical Summary: On Determining the Convergence Rate of an Infinite Product of Stochastic Matrices

Problem Statement
The paper addresses the analysis of infinite products of stochastic matrices, a fundamental component in consensus protocols for distributed control, estimation, and optimization. While the convergence of such products to a rank-one matrix is well-established for specific "convergent sets" (e.g., scrambling matrices, Sarymsakov matrices), determining the rate of convergence remains challenging. Specifically, the authors investigate whether submultiplicative consensus seminorms can be used to uniformly bound the convergence rate for all matrices within a given convergent set. A key question is whether there exists a single seminorm in which every matrix of a convergent set acts as a contraction (i.e., has a seminorm value strictly less than 1), thereby guaranteeing exponential convergence.

Methodology
The authors employ the framework of consensus seminorms, defined on the subspace $M_{n \times n}$ of matrices with equal row sums. A consensus seminorm $|\cdot|$ satisfies $|M|=0$ if and only if $M = \mathbf{1}c$ (a rank-one matrix). The analysis relies on:

Submultiplicativity: The property $|M_1 M_2| \leq |M_1||M_2|$ , which links the seminorm value to the convergence rate.
Joint Spectral Semiradius: A novel adaptation of the joint spectral radius, defined using a consensus seminorm rather than a standard matrix norm, to characterize the asymptotic behavior of infinite products.
Topological Arguments: Utilizing the density of specific matrix sets (such as positive stochastic matrices) within the space of all stochastic matrices to derive contradictions regarding the existence of uniform contraction seminorms.
Hajnal's Property: Leveraging a known result that the product of a non-scrambling matrix with a specific stochastic matrix can be non-convergent.

Key Contributions and Results

1. Non-Existence of Uniform Contraction Seminorms for General Convergent Sets
The paper refines previous results to prove that not all convergent sets admit a single submultiplicative consensus seminorm in which all matrices are contractions.

Theorem 1: For $n > 2$ , there is no submultiplicative consensus seminorm $|\cdot|$ such that $|S| < 1$ for all $S$ in the set $R$ (stochastic matrices with positive diagonals and a rooted graph) or the set $K$ (Sarymsakov matrices).
Theorem 3: If a convergent set $C$ is dense in the set of all stochastic matrices $S_{n \times n}$ , and there exists a seminorm where all $S \in C$ are contractions, then $C$ must be a subset of the scrambling matrices.
Implication: Since $R$ and $K$ are dense in $S_{n \times n}$ but contain non-scrambling matrices, no single seminorm can bound the convergence rate for all matrices in these sets. This contrasts with the set of scrambling matrices ( $S$ ) and doubly stochastic matrices with weakly connected graphs ( $D$ ), where such seminorms (e.g., the coefficient of ergodicity or the second largest singular value) do exist.

2. Finite Product Contraction Property
The paper establishes that while individual matrices in a compact convergent set may not be contractions in a given seminorm, finite products of them eventually become contractions.

Corollary 2: For every compact convergent set $C$ and every submultiplicative consensus seminorm, there exists a finite integer $k$ such that the product of any $k$ matrices from $C$ is a contraction (i.e., $|S_k \cdots S_1| < 1$ ).
This result generalizes the known property for scrambling matrices (where a finite product length guarantees scrambling) to general consensus seminorms.

3. Joint Spectral Semiradius and Convergence Rates
The authors introduce the joint spectral semiradius $\sigma(C)$ , defined as the limit of the supremum of the $t$ -th root of the seminorm of products of length $t$ .

Theorem 4: A compact set $C$ is convergent if and only if $\sigma(C) < 1$ . Furthermore, if $\sigma(C) < 1$ , the convergence rate is exponential, bounded by $\delta^t$ for any $\delta > \sigma(C)$ .
This provides a theoretical mechanism to bound convergence rates even when individual matrices are not contractions, provided the joint spectral semiradius is less than one.

Significance and Claims
The paper claims to clarify the limitations of using submultiplicative seminorms for bounding convergence rates in distributed consensus.

It demonstrates that the "nice" property of having a single contraction seminorm is not universal; it fails for important classes like $R$ and $K$ when $n > 2$ .
It highlights that the ability to determine convergence rates via a single seminorm is closely tied to the topological density of the matrix set and the scrambling property.
The paper posits that while individual matrices may not be contractions, the "joint" behavior (captured by the joint spectral semiradius) ensures that finite products eventually contract, offering a pathway to rate bounds for general convergent sets.
The authors conclude by noting open questions: specifically, whether the finite product contraction property (Corollary 2) holds with a $k$ bounded by a function of dimension $n$ for all seminorms, or if there exist seminorms where such a bound does not exist.

The "Speedometer" Problem

The Big Discovery: One Size Does Not Fit All

The "Teamwork" Solution: Wait for a Few Rounds

Summary of the Paper's Claims

Technical Summary: On Determining the Convergence Rate of an Infinite Product of Stochastic Matrices

More like this