Lemma 2, p. 19 — for the ϵ-DeGroot process, ⟨µ^W, x^t⟩ is a martingale
ProvedNaiveLearn.OverMatch.lemma_2Consider the -DeGroot process, i.e. the random action process with probability-matching decision rule and belief recursion (1), on a network with weight matrix (row-stochastic, irreducible, ) and centrality measure (a probability vector with ). Let and . Then the centrality-weighted average belief
is a martingale with respect to the filtration generated by the action coins of the periods before .
This martingale is the basic tool of the analysis of the -DeGroot process: its limit identifies the probability of agreement on action .
Formalization Note The paper's filtration is generated by the beliefs ; the coin filtration used here contains it, so the statement is at least as strong (a martingale for a larger filtration, to which is adapted, is a martingale for the smaller one). Lean time is the paper's period .
import Mathlib import Definitions.Def_NaiveLearn_OverMatch_Model open MeasureTheory ProbabilityTheory Filter Topology
namespace NaiveLearn.OverMatch
/-- Lemma 2, p. 19: for the `ε`-DeGroot process (probability matching, `σ = id`) the centrality-
weighted average belief `⟨µ^W, x^t⟩ = Σ_i µ_i x_i^t` is a martingale. The filtration is generated
by the coins `U_0, …, U_{t−1}`, which contains `σ(x^0, …, x^t)`. -/
theorem lemma_2 {m : ℕ} (W : Matrix (Fin m) (Fin m) ℝ) (μ : Fin m → ℝ)
(hW : IsWeightMatrix W) (hμ : IsCentrality W μ) (ε : ℝ) (hε : ε ∈ Set.Ioc (0 : ℝ) 1)
(x1 : Fin m → ℝ) (hx1 : ∀ i, x1 i ∈ Set.Icc (0 : ℝ) 1) :
Martingale (fun t U => ∑ i, μ i * beliefAct id ε W x1 U t i) (coinFiltration m)
(coinLaw m) := by sorry
end NaiveLearn.OverMatch
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.