Source-linked AI summary
Product of Random Stochastic Matrices
Behrouz Touri, Angelia Nedich
TL;DR
The paper studies when products of random row-stochastic matrices converge. It connects those products to averaging dynamics, develops time-varying Lyapunov functions, and analyzes P∗ and balanced chains. The resulting stability theory extends classical rank-one convergence to inhomogeneous and independent random chains.
Problem
The paper examines the limiting behavior of products of random row-stochastic matrices and the conditions for their ergodicity and convergence.
Source: §1 · p. 2, §7 · p. 18Method
It studies associated averaging dynamics with time-varying Lyapunov functions, then uses P∗ chains and geometric properties of balanced chains to establish stability results.
Source: §1 · p. 2Results
Takeaways & Limitations
Studying the associated dynamics lets the paper use dynamical-systems tools and stability theory to draw conclusions about matrix-product limits.
Source: §3 · p. 4The analysis works exclusively with row-stochastic matrices.
Source: §2 · p. 3
Abstract
from arXiv · showhide
The paper deals with the convergence properties of the products of random (row-)stochastic matrices. The limiting behavior of such products is studied from a dynamical system point of view. In particular, by appropriately defining a dynamic associated with a given sequence of random (row-)stochastic matrices, we prove that the dynamics admits a class of time-varying Lyapunov functions, including a quadratic one. Then, we discuss a special class of stochastic matrices, a class $\Pstar$, which plays a central role in this work. We then introduce balanced chains and using some geometric properties of these chains, we characterize the stability of a subclass of balanced chains. As a special consequence of this stability result, we obtain an extension of a central result in the non-negative matrix theory stating that, for any aperiodic and irreducible row-stochastic matrix $A$, the limit $\lim_{k\to\infty}A^k$ exists and it is a rank one stochastic matrix. We show that a generalization of this result holds not only for sequences of stochastic matrices but also for independent random sequences of such matrices.
1 Introduction
The paper studies convergence of random stochastic-matrix products, extending earlier work on averaging dynamics and products of stochastic matrices. It develops a dynamical-systems approach with time-varying Lyapunov functions, then uses P∗ and balanced chains to establish stability results and extend classical rank-one convergence.
1 Introduction
- Averaging dynamics arise in distributed optimization, robotic-network control, and opinion dynamics, while prior stochastic-product studies include Markov-chain and distributed-averaging perspectives.The paper places its contribution alongside early sufficient conditions for rank-one convergence and later distributed-averaging work.Source: §1 · p. 1
- The work continues earlier study of convergence for random stochastic-matrix products that need not be identically distributed.Earlier work introduced infinite-flow properties, infinite-flow graphs, and ℓ1-approximation as concepts closely related to convergence.Source: §1 · p. 2
- The paper derives necessary and sufficient conditions for ergodicity and convergence of products of independent random stochastic matrices.Its dynamical-systems approach establishes time-varying Lyapunov functions, including a quadratic one and functions adjusted to any convex function.Source: §1 · p. 2
- Balanced chains are shown to be P∗ chains, linking their geometric properties to the paper’s stability result.Products from P∗ chains converge almost surely.Source: §1 · p. 2
- The stability result extends rank-one convergence from powers of an aperiodic, irreducible stochastic matrix to inhomogeneous and independent random chains.The classical result concerns the limit of A^k for an aperiodic, irreducible row-stochastic matrix A.Source: §1 · p. 2
2 Problem Setting
The setting is a chain of random row-stochastic matrices, with balance and strong aperiodicity among the conditions used for the main convergence result. For independent chains satisfying both conditions, products converge almost surely, and connectedness of the infinite flow graph yields rank-one limits.
2 Problem Setting
- The paper works exclusively with row-stochastic matrices and uses W(k:t0) for the product W(k)···W(t0+1).The product is defined as the identity when k=t0.Source: §2 · pp. 3–4
- Strong aperiodicity follows when every diagonal entry is bounded below by a positive constant, and this property also holds for the expected chain.A uniform almost-sure lower bound on the random chain’s diagonal entries is a sufficient condition.Source: §2 · p. 3
- For balanced chains, expected flow from every nontrivial set to its complement is at least an α-fraction of flow in the reverse direction, uniformly over time.The definition stipulates α > 0 and implies α ≤ 1.Source: §2 · p. 3
- The infinite flow graph of an independent random chain is almost surely deterministic and equals that of its expected chain.The theorem’s component-wise equality of limiting rows makes this graph relevant to the structure of the limit.Source: §2 · pp. 3–4
- Independent balanced, strongly aperiodic chains have products that converge almost surely, with equal limiting rows for indices in the same infinite-flow-graph component.If that graph is connected, the limit has rank one almost surely.Source: §2 · p. 4
- For a connected infinite flow graph, the limit is rank one, and an independent balanced, strongly aperiodic chain is almost surely strongly ergodic exactly when that graph is connected.With τ connected components, the limit has rank at most τ.Source: §2 · p. 4
3 Dynamic System Perspective
The paper studies stochastic-matrix products through the dynamics they drive, using stability concepts to relate the dynamics’ behavior to product convergence. It develops infinite-flow-graph results and time-varying Lyapunov functions, including a quadratic function.
3 Dynamic System Perspective
- The recursion x(k + 1) = W(k + 1)x(k) connects matrix products to dynamics: product convergence implies dynamics convergence, and coordinate agreement can be checked on basis-vector initial states.Studying the dynamics lets the authors use dynamical-systems tools to analyze product limits.Source: §3 · p. 4
3.1 Why the Infinite Flow Graph
- Within an infinite-flow-graph component, pairwise mutual ergodicity implies each index is ergodic, although mutual ergodicity alone does not generally imply individual ergodicity.The proof uses an ℓ1-approximation and the component’s block-diagonal structure.Source: §3.1 · p. 5
3.2 Time-varying Lyapunov Functions
- With an absolute probability process, every convex g yields a time-varying Lyapunov function whose conditional expectation is nonincreasing and whose values converge almost surely.The nonnegative Lyapunov values form a bounded supermartingale, for any initial point and convex g.Source: §3.2 · pp. 6–7
3.3 Time-varying Quadratic Lyapunov Function
- The decrease of E[Vg(x(k + 1), k + 1) | Fk] has a lower bound; the inequality is an equality almost surely when πT(k + 1)W(k + 1) = πT(k).Source: §3.3 · pp. 7–8
4 Class P∗
The class P∗ consists of adapted random chains with an absolute probability process uniformly bounded away from zero. For weakly aperiodic chains in this class, products converge almost surely, with limiting rows characterized by the infinite flow graph.
4 Class P∗
- The section’s central result applies to P∗ chains that satisfy weak aperiodicity.The class is introduced as a setting in which the paper’s main convergence claim holds under an aperiodicity condition.Source: §4 · pp. 9, 11
- P∗ requires an absolute probability process whose entries are uniformly bounded below by a positive scalar almost surely.The bound applies at every time and to every index.Source: §4 · p. 9
- P∗ is not limited to a narrow family: the paper states that it contains a broad family of deterministic and random chains.The next section establishes that strongly aperiodic balanced chains belong to P∗.Source: §4 · p. 9
- For a weakly aperiodic chain in P∗, the product limit exists almost surely, and two limiting rows agree exactly on the event that their indices share an infinite-flow component.The result holds for every starting time t0.Source: §4 · p. 11
5 Balanced Chains
Balanced chains include several previously studied classes and can be characterized using left-eigenvectors of expected matrices. The paper shows that strongly aperiodic balanced chains belong to P∗, connecting their structural properties to the convergence results for that class.
5 Balanced Chains
- Balanced bidirectional chains and chains with a common positive steady state are presented as examples of balanced-chain subclasses.The paper also identifies bounded bidirectional deterministic chains, including the Hegselman-Krause opinion model, as examples.Source: §5 · pp. 12–13
- A positive common steady state gives a balanced chain, with its balancedness coefficient bounded by the ratio of the smallest to largest steady-state entries.The lemma establishes the cross-set flow inequality using πmin/πmax.Source: §5 · p. 13
- For an independent random chain, uniformly positive stochastic left-eigenvectors of the expected matrices imply balancedness with coefficient α = p∗.The eigenvectors correspond to the unit eigenvalue at each time.Source: §5 · p. 13
5.1 Absolute Probability Sequence for Balanced Chains
- The section’s proof strategy first treats deterministic chains with uniformly bounded positive entries, then extends the result to deterministic and independent random chains.Geometric properties of the strongly aperiodic balanced-chain set support the deterministic extension.Source: §5.1 · p. 14
- With positive entries uniformly bounded below by γ, the positive-index sets in each product column grow monotonically and their minimum positive entries satisfy µj(k) ≥ γ^|Sj(k)|−1.This bound improves the cited earlier lower bound from γm^2−m+2 to γm−1.Source: §5.1 · pp. 14–15
- Any balanced and strongly aperiodic independent random chain belongs to P∗, linking balanced-chain conditions to the convergence results established for that class.The paper first establishes this membership for deterministic chains and then extends it to independent random chains.Source: §5.1 · pp. 16–17
6 Connection to Non-negative Matrix Theory
The section relates classical convergence of powers of an aperiodic irreducible stochastic matrix to convergence results for time-varying and random chains. It characterizes irreducibility through balancedness and connectivity of the infinite flow graph.
6 Connection to Non-negative Matrix Theory
- The classical result states that powers of an aperiodic irreducible stochastic matrix converge to a rank-one stochastic matrix.The paper presents its chain results as an extension of this result.Source: §6 · p. 17
- A stochastic matrix is irreducible if and only if its static chain is balanced and has a connected infinite flow graph.This equivalence supplies the structural link to the classical matrix result.Source: §6 · p. 17
- For a balanced, strongly aperiodic independent random chain with connected infinite flow graph, the product converges almost surely to a rank-one stochastic matrix.Without the infinite flow property, the limit has rank at most the number of connected components of the expected chain’s infinite flow graph.Source: §6 · p. 18
- For a balanced, strongly aperiodic deterministic chain, the product limit exists, and it is rank one exactly when the infinite flow graph is connected.This extends the convergence statement to inhomogeneous chains.Source: §6 · p. 18
7 Conclusion
The paper studies random stochastic-matrix products as dynamical systems and establishes time-varying Lyapunov functions and stability results. These results extend a classical convergence theorem to time-varying and independent random chains.
7 Conclusion
- The paper studies limiting behavior of random stochastic-matrix products from a dynamical-systems perspective.Source: §7 · p. 18
- It establishes a general stability result for products of random stochastic matrices and extends a classical convergence result for time-homogeneous irreducible and aperiodic Markov chains.Source: §7 · p. 18
- The paper introduces P∗ chains and balanced chains, and reports that many previously studied random chains belong to the balanced class.Source: §7 · p. 18