Wolfowitz (1963) — DOI:10.1090/S0002-9939-1963-0154756-3
Key takeaways
A 2-page note proving that infinite products of stochastic matrices from a finite set converge to a rank-1 matrix (all rows equal, i.e., consensus), provided every matrix in the set is indecomposable (irreducible) and aperiodic, and each matrix appears infinitely often in the sequence. This gives a clean, checkable sufficient condition for convergence of products of time-varying stochastic matrices — the mathematical core needed by all subsequent consensus and gossip convergence proofs.
- Main Theorem (Wolfowitz 1963). Let {P_1, …, P_m} be a finite collection of n×n indecomposable aperiodic stochastic matrices. For any infinite sequence (i_1, i_2, …) over {1,…,m} in which each index k appears infinitely often, the infinite right-to-left product Q_t = P_{i_t} · P_{i_{t-1}} ··· P_{i_1} converges as t→∞ to a rank-1 stochastic matrix Q = 1·v^T, where v is a probability vector (dependent on the sequence). All rows of Q_t converge to the same limit v. Holds when: Finite set of matrices; all indecomposable and aperiodic; each appears infinitely often. The limit v may depend on the sequence — consensus value is not universal.
- Contraction via Dobrushin coefficient (quantitative consequence). For each indecomposable aperiodic stochastic matrix P, there exists k_P such that P^{k_P} is a scrambling matrix (has a positive column). The Dobrushin coefficient δ(A) = (1/2) max_{i,j} Σ_k |A_{ik} - A_{jk}| satisfies δ(P^{k_P}) < 1. Products of t such matrices contract row differences at rate δ^{⌊t/k_P⌋}, giving geometric convergence speed. Holds when: k_P depends on the individual matrix; for T steps with k_P ≤ T, contraction is geometric.
What the evidence does not cover
- Finite matrix set is essential — results do not generalize to infinite or continuously-varying matrix families without additional uniformity conditions.
- Convergence rate depends on the worst-case Dobrushin coefficient in the product, which may be hard to bound for large sparse matrices.
- The limit vector v depends on the sequence of matrices — no universal consensus value is guaranteed unless matrices are doubly stochastic.
- Purely about averaging consensus — does not cover optimization, gradient noise, or non-linear dynamics.
- The result is asymptotic; no finite-time convergence guarantee without explicit contraction bounds.
Standing in the anthology
Read — the reading is NOTE-092. Arrived in the imported batch, which brought in the consensus, synchronization and flocking literature that the decentralized-training results rest on.
The reading placed this in the Annals of Mathematical Statistics 34(4), with a DOI that resolves to nothing. It is Proceedings of the American Mathematical Society 14(5), and the identifier here is CrossRef’s.