Averaging whenever you meet: the expected matrix and the first moment #
One round of the averaging process is x⁽ᵗ⁾ = W_t x⁽ᵗ⁻¹⁾ with the random matrix W_t of
equation (1) of arXiv:1703.05045 (v3). Its expectation over a uniformly random edge is
W̄ = I - L / (2m) (equation (2), Observation A.2), L = D - A the Laplacian and m the number of
edges, a symmetric doubly stochastic matrix. Since the rounds are independent, the expected state
evolves linearly: E[x⁽ᵗ⁾ | x⁽⁰⁾ = x] = W̄ᵗ x (equation (15)). Since W_t is symmetric and
idempotent, the expected squared norm after one round is the quadratic form of W̄ (the identity
behind Lemma C.1).
These are the matrices of the random sequential model of Averaging.Sequential (AVG-1):
stepMatrix G d is Sequential.edgeMatrix d.fst d.snd, meanStepMatrix G is
Sequential.meanMatrix G, and the averaging process avgRun is Sequential.seqRun
(avgRun_eq_seqRun), so the statements below are those of AVG-1.
The random matrix W_t of one round on the active edge {d.fst, d.snd} (equation (1)):
1/2 on the diagonal at the two endpoints and at the two entries of the active edge, 1 on the
rest of the diagonal, 0 elsewhere. It is I - (e_u - e_v)(e_u - e_v)ᵀ / 2, the step matrix
Sequential.edgeMatrix of AVG-1.
Equations
Instances For
The expected matrix W̄ = I - L / (2m) of one round (equation (2)), where L = D - A is the
Laplacian of G and m its number of edges: Sequential.meanMatrix of AVG-1.
Instances For
One round as a matrix step #
One round of averaging is the multiplication by AVG-1's step matrix W_t.
The averaging process is AVG-1's sequential averaging x⁽ᵗ⁾ = W(t) ⋯ W(1) x⁽⁰⁾.
Main statements #
W_t x is one round of averaging on the active edge.
W_t is symmetric (proof of Lemma C.1).
W_t is idempotent (proof of Lemma C.1).
Observation A.2, equation (2): over a uniformly random edge, E[W_t] = I - L / (2m).
W̄ is symmetric (Section 3).
W̄ is doubly stochastic (Section 3).
Equation (2) applied to a state: the expected state after one round is W̄ x.
First-moment evolution, equation (15): E[x⁽ᵗ⁾ | x⁽⁰⁾ = x] = W̄ᵗ x over t i.i.d. uniform
rounds.
Second moment of one round (proof of Lemma C.1): E‖W x‖² = xᵀ W̄ x, since W is symmetric
and idempotent.