Averaging in the random sequential model: definitions

Definitions for the expected-matrix identities of roadmap AVG-1: Becchetti, Clementi, Natale, Consensus Dynamics: An Overview, SIGACT News 51(1), 2020 (the Survey), Section 7.2, equations (2)–(5), after Boyd, Ghosh, Prabhakar, Shah, Randomized gossip algorithms, IEEE Trans. Inf. Theory 52(6), 2006 (BGPS06). In each step one edge is selected and its two endpoints replace their values by their average (Averaging(δ) of Definition 31 with δ = 1/2, the case of Section 7.2).

• edgeMatrix: the matrix W = I - (e_i - e_j)(e_i - e_j)ᵀ / 2 of one step on the edge (i, j) (equation (2));
• seqRun: the state x⁽ᵗ⁾ = W(t) ⋯ W(1) x⁽⁰⁾ after a sequence of selected oriented edges (equation (3));
• kernelMatrix, gossipMeanMatrix: the stochastic matrix P of a transition kernel and the right-hand side I - D̄/(2n) + (P + Pᵀ)/(2n) of equation (4);
• meanMatrix: the expected step matrix W̄ = I - L/(2m) when one oriented edge is selected uniformly at random (the random sequential model of the Survey, Section 2).

noncomputable def Averaging.Sequential.edgeMatrix {V : Type u_1} [DecidableEq V] (i j : V) : Matrix V V ℝ

Equation (2): the matrix W = I - (e_i - e_j)(e_i - e_j)ᵀ / 2 of one step of averaging in which the edge (i, j) is selected, e_h the h-th canonical vector.

Equations

• Averaging.Sequential.edgeMatrix i j = 1 - (1 / 2) • Matrix.vecMulVec (Pi.single i 1 - Pi.single j 1) (Pi.single i 1 - Pi.single j 1)

noncomputable def Averaging.Sequential.kernelMatrix {V : Type u_1} [Fintype V] (K : Dynamics.Kernel V) : Matrix V V ℝ

The stochastic matrix Pᵢⱼ = (K i).weight j of a transition kernel K.

Equations

• Averaging.Sequential.kernelMatrix K = Matrix.of fun (i j : V) => (K i).weight j

noncomputable def Averaging.Sequential.gossipMeanMatrix {V : Type u_1} [Fintype V] [DecidableEq V] (K : Dynamics.Kernel V) : Matrix V V ℝ

The right-hand side of equation (4), I - D̄/(2n) + (P + Pᵀ)/(2n), for the stochastic matrix P of the kernel K, with n = |V| and D̄ the diagonal matrix with D̄ᵢᵢ = ∑ⱼ (Pᵢⱼ + Pⱼᵢ).

Equations

• One or more equations did not get rendered due to their size.

noncomputable def Averaging.Sequential.seqRun {V : Type u_1} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (x : V → ℝ) (l : List G.Dart) : V → ℝ

Equation (3): the state x⁽ᵗ⁾ = W(t) ⋯ W(1) x⁽⁰⁾ after the oriented edges l have been selected, the first step at the head of l (as in Dynamics.expList).

Equations

• Averaging.Sequential.seqRun G x l = List.foldl (fun (y : V → ℝ) (d : G.Dart) => (Averaging.Sequential.edgeMatrix d.toProd.1 d.toProd.2).mulVec y) x l

noncomputable def Averaging.Sequential.meanMatrix {V : Type u_1} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] : Matrix V V ℝ

The expected step matrix W̄ = I - L / (2m) when one oriented edge of G is selected uniformly at random, where L = D - A is the Laplacian and m the number of edges.

Equations

• Averaging.Sequential.meanMatrix G = 1 - (2 * ↑G.edgeFinset.card)⁻¹ • SimpleGraph.lapMatrix ℝ G