Averaging in the random sequential model: the expected step matrix

Section 7.2 of Becchetti, Clementi, Natale, Consensus Dynamics: An Overview, SIGACT News 51(1), 2020 (the Survey), equations (2)–(5), after Boyd, Ghosh, Prabhakar, Shah, Randomized gossip algorithms, IEEE Trans. Inf. Theory 52(6), 2006 (BGPS06).

One step on the edge (i, j) multiplies the state by W = I - (e_i - e_j)(e_i - e_j)ᵀ / 2 (equation (2)), a doubly stochastic symmetric projection. Equation (4) is the expectation of W when a uniformly random node i contacts a node j drawn from row i of a stochastic matrix P (the model of BGPS06): 𝔼[W] = I - D̄/(2n) + (P + Pᵀ)/(2n). In the Survey's random sequential model one oriented edge is selected uniformly at random; then 𝔼[W] = I - L/(2m). On a regular graph both read (1 - 1/n) I + P/n with P = D⁻¹A (equation (5)). Since WᵀW = W, the second moment is 𝔼[WᵀW] = 𝔼[W] (BGPS06), and since the steps are independent, 𝔼[x⁽ᵗ⁾] = W̄ᵗ x⁽⁰⁾ (Survey, Section 7.3.2).

theorem Averaging.Sequential.edgeMatrix_mulVec {V : Type u_1} [Fintype V] [DecidableEq V] (i j : V) (x : V → ℝ) : (edgeMatrix i j).mulVec x = fun (w : V) => if w = i ∨ w = j then (x i + x j) / 2 else x w

One step on the edge (i, j) replaces the values of both endpoints by their average and leaves the other values unchanged (Survey, Section 7.2, before equation (2)).

theorem Averaging.Sequential.edgeMatrix_mem_doublyStochastic {V : Type u_1} [Fintype V] [DecidableEq V] (i j : V) : edgeMatrix i j ∈ doublyStochastic ℝ V

Each W(t) is doubly stochastic (Survey, Section 7.2, remark ii after equation (3)).

theorem Averaging.Sequential.transpose_edgeMatrix_mul_self {V : Type u_1} [Fintype V] [DecidableEq V] (i j : V) : (edgeMatrix i j).transpose * edgeMatrix i j = edgeMatrix i j

W = I - (e_i - e_j)(e_i - e_j)ᵀ / 2 is a symmetric projection, WᵀW = W (BGPS06, Section IV; the source of the second-moment identity).

theorem Averaging.Sequential.avg_expect_edgeMatrix {V : Type u_1} [Fintype V] [DecidableEq V] (K : Dynamics.Kernel V) (a b : V) : (Dynamics.avg fun (i : V) => (K i).expect fun (j : V) => edgeMatrix i j a b) = gossipMeanMatrix K a b

Equation (4) (Survey; BGPS06). If a uniformly random node i selects the edge (i, j) with j drawn from the kernel K (row i of the stochastic matrix P), the expected step matrix is 𝔼[W] = I - D̄/(2n) + (P + Pᵀ)/(2n), D̄ᵢᵢ = ∑ⱼ (Pᵢⱼ + Pⱼᵢ). Stated entrywise.

theorem Averaging.Sequential.gossipMeanMatrix_of_isRegular {V : Type u_1} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (K : Dynamics.Kernel V) (hK : kernelMatrix K = walkMatrix G) {d : ℕ} (hreg : G.IsRegularOfDegree d) : gossipMeanMatrix K = (1 - (↑(Fintype.card V))⁻¹) • 1 + (↑(Fintype.card V))⁻¹ • walkMatrix G

Equation (5) (Survey). On a regular graph, equation (4) for the random walk P = D⁻¹A (a uniformly random node contacts a uniformly random neighbour) reads 𝔼[W] = (1 - 1/n) I + P / n.

theorem Averaging.Sequential.avg_edgeMatrix {V : Type u_1} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] [Nonempty G.Dart] (a b : V) : (Dynamics.avg fun (d : G.Dart) => edgeMatrix d.toProd.1 d.toProd.2 a b) = meanMatrix G a b

The expected step matrix of the random sequential model (Survey, Section 7.2): if one oriented edge is selected uniformly at random, 𝔼[W] = I - L / (2m). Stated entrywise.

theorem Averaging.Sequential.meanMatrix_of_isRegular {V : Type u_1} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] {d : ℕ} (hreg : G.IsRegularOfDegree d) (hd : 0 < d) : meanMatrix G = (1 - (↑(Fintype.card V))⁻¹) • 1 + (↑(Fintype.card V))⁻¹ • walkMatrix G

Equation (5) for the random sequential model: on a d-regular graph with d > 0, I - L / (2m) = (1 - 1/n) I + P / n.

theorem Averaging.Sequential.avg_transpose_edgeMatrix_mul_self {V : Type u_1} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] [Nonempty G.Dart] (a b : V) : (Dynamics.avg fun (d : G.Dart) => ((edgeMatrix d.toProd.1 d.toProd.2).transpose * edgeMatrix d.toProd.1 d.toProd.2) a b) = meanMatrix G a b

The second-moment identity 𝔼[WᵀW] = 𝔼[W] = I - L / (2m) (BGPS06, Section IV) for a uniformly random oriented edge. Stated entrywise.

theorem Averaging.Sequential.avg_sum_sq_edgeMatrix_mulVec {V : Type u_1} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] [Nonempty G.Dart] (x : V → ℝ) : (Dynamics.avg fun (d : G.Dart) => ∑ v : V, (edgeMatrix d.toProd.1 d.toProd.2).mulVec x v ^ 2) = x ⬝ᵥ (meanMatrix G).mulVec x

The second-moment identity on a state: 𝔼 ‖W x‖² = xᵀ W̄ x for a uniformly random oriented edge.

theorem Averaging.Sequential.expList_seqRun {V : Type u_1} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] [Nonempty G.Dart] (x : V → ℝ) (t : ℕ) (v : V) : (Dynamics.expList G.Dart t fun (l : List G.Dart) => seqRun G x l v) = (meanMatrix G ^ t).mulVec x v

First-moment evolution (Survey, Section 7.3.2): over t independent uniformly random oriented edges, 𝔼[x⁽ᵗ⁾] = W̄ᵗ x⁽⁰⁾.