On Ergodicity, Infinite Flow and Consensus in Random Models

1 Introduction

• Ergodicity is used to investigate consensus because ergodicity always guarantees consensus.The paper frames this relationship as motivation for studying conditions that ensure ergodicity.Source: §1 · p. 1
• Infinite flow can be interpreted as infinite information exchange over time between groups of agents across a network cut.The paper presents this as an alternative approach to studying the relation between ergodicity and consensus.Source: §1 · p. 1
• The paper studies fundamental properties of ergodicity, consensus, and infinite flow across general, independent, and i.i.d. random models.It also classifies three feedback-property types and examines the roles of feedback and a common steady state in expectation.Source: §1 · pp. 1–2
• For independent models with feedback and a common steady state in expectation, ergodicity is equivalent to infinite flow, including for the model’s expected chain.The theorem also equates ergodicity of the random model and its expected model.Source: §1 · p. 2
• The new infinite-flow phenomenon provides a way to study ergodicity and consensus in random models with independent, time-varying distributions.Earlier cited work assumed i.i.d. or stationary models, which imply time-invariant distributions.Source: §1 · pp. 1–2

2 Problem Formulation and Terminology

• The system evolves by applying the random matrix W(k) to the state at each time step.The model is considered on stochastic matrices, and each state vector lies in R^m.Source: §2 · p. 3
• The study seeks conditions for almost-sure consensus and examines ergodicity because consensus is closely related to it.The section also uses infinite flow as a further property of the chain.Source: §2 · pp. 3–4
• Infinite flow requires the total weight crossing every nontrivial cut between a subset of agents and its complement to diverge over time.The cut flow sums matrix weights in both directions; it can be interpreted as information exchange between the two groups.Source: §2 · p. 4
• Ergodicity requires products of the chain, from any starting time, to map each basis vector asymptotically to a multiple of the all-ones vector.By contrast, consensus requires trajectories from every initial state to converge to a common value across agents.Source: §2 · p. 4
• Ergodicity implies consensus, but consensus can occur without ergodicity, as an initial averaging step followed by identity matrices demonstrates.The section defines consensus, ergodicity, and infinite-flow events and their almost-sure model-level counterparts.Source: §2 · p. 4

3.1 Basic Relations

• For every random model, ergodicity implies consensus and infinite flow, while infinite flow is sufficient for ergodicity only for a specified class of models.Theorem 1 establishes necessity; the section reserves sufficiency for the class addressed later in Theorem 6.Source: §3.1 · pp. 5–6
• For an independent model, consensus can occur with probability p > 0 even though the infinite-flow and ergodicity events are empty, so consensus need not be contained in either event.Source: §3.1 · p. 8
• For i.i.d. models, ergodicity and consensus are almost surely equal, extending an earlier result that assumed positive diagonal entries almost surely.The cited earlier result is in.Source: §3.1 · pp. 8–9

3.2 0-1 Laws

• For independent models, ergodicity and infinite flow are 0-1 events, but consensus need not be; for i.i.d. models, consensus is also a 0-1 event.For i.i.d. models, this follows from the almost-sure equality of ergodicity and consensus.Source: §3.2 · pp. 9–10
• An i.i.d. uniform sequence of permutation matrices has almost-sure infinite flow but never reaches consensus.The expected matrix is (1/m)ee^T, but each realized matrix is a permutation matrix.Source: §3.2 · p. 10

3.3 Random Model and Its Expected Model

• For independent models, infinite flow holds exactly when the expected model has infinite flow; if E = F almost surely, ergodicity also matches ergodicity of the expected model.The latter equivalence requires the stated E = F almost-sure condition.Source: §3.3 · pp. 10–11
• In an independent model, consensus or ergodicity implies the corresponding property for the expected model, but there is no general converse without additional assumptions.The section gives an equivalence for ergodicity only under E = F almost surely.Source: §3.3 · p. 11

4.1 Feedback Properties

• Strong feedback implies feedback, which implies weak feedback; the paper distinguishes weak feedback from feedback with a deterministic example.The example lacks feedback but has weak feedback with γ = 1/4.Source: §4.1 · p. 12
• A model’s feedback property implies that its expected model has strong feedback, while lower-bound conditions on expected entries can imply feedback or weak feedback.The expected-model feedback constant is stated as γ m in the passage.Source: §4.1 · p. 12

4.2 Steady State in Expectation

• A common steady state in expectation is a stochastic vector π satisfying π^T E[W(k)] = π^T for every time k.Source: §4.2 · p. 13
• Under independence and a common steady state in expectation, the weighted averages π^T x(k) converge almost surely for any initial state.The paper identifies these weighted averages as a bounded martingale.Source: §4.2 · p. 13
• The limiting random vector λπ is stochastic and has expectation π.The limit points of the state sequence lie in a random hyperplane defined by λπ, though the supplied passage does not show the full expression.Source: §4.2 · p. 14
• With a common steady state in expectation, the weighted spread V(x(k)) converges almost surely and forms a supermartingale.The passage identifies V(x) as measuring the weighted spread of the entries around π^T x.Source: §4.2 · pp. 13, 14, 16

5.1 Preliminary Result

• The preliminary argument orders initial state entries, tracks cumulative flow across ordered cuts, and uses these quantities to bound pairwise state separation.It defines cut sets S_l and times t_l, then introduces index sets a_ij(k) to estimate the separation between entries.Source: §5.1 · pp. 18–19

5.2 Sufficient Conditions for Ergodicity

• Either infinite flow or expected infinite flow suffices for ergodicity under a common positive expected steady state and weak feedback.The states converge almost surely to a common value, λ^Tπx(0).Source: §5.2 · pp. 21–22

5.3 Necessary and Sufficient Conditions for Ergodicity

• Under independence, a common positive steady state in expectation, and weak feedback, ergodicity, infinite flow, expected-model infinite flow, and expected-model ergodicity are equivalent.The theorem also yields a deterministic criterion for deterministic chains: the cumulative cut flow must be infinite for every nontrivial set.Source: §5.3 · p. 23
• Under the theorem's assumptions, the deterministic chain is ergodic exactly when cumulative flow across every nontrivial cut is infinite.Ergodicity under these assumptions also implies consensus.Source: §5.3 · p. 23
• For the extended gossip algorithm on time-varying networks, almost-sure consensus follows when cumulative interaction probability across every nontrivial cut is infinite.For a static interaction-probability graph, this condition is equivalent to graph connectivity.Source: §5.3 · p. 24

• The infinite flow theorem gives necessary and sufficient conditions for ergodicity of independent random models and relates the infinite-flow, ergodicity, and consensus events.Source: §6 · pp. 24–25
• The theorem captures conditions for convergence of gossip and broadcast schemes and connects system connectivity with sufficient information flow studied in deterministic settings.Source: §6 · p. 25
• The framework extends to an initial state x(0) that is random and independent of the matrix chain.Source: §6 · p. 25