Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2, pp. 8–9 β€” on graph sequences admitting a strong coupling, the typical stationary opinion converges in conditional law to the root opinion 𝓑* of the local limit

Proved
DirectedOpinion.Typical.theorem_2

by mikedeng1 Β· Oct 14, 2026 Β· Mathlib 0df444a (Lean v4.33.1)

local-weak-convergenceopinion-dynamicsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1random-graphsstationary-distributiontypical-behavior

Consider the random directed graph sequence G(Vn,En;An)G(V_n,E_n;\mathscr A_n)G(Vn​,En​;An​) with the signals and initial opinions of the setting, and suppose that it admits a strong coupling (Definition 4) with a marked directed graph G(X)\mathcal G(\boldsymbol{\mathcal X})G(X). Assume d>0d>0d>0 and that the conditional law Ξ½(β‹…)\nu(\cdot)Ξ½(β‹…) of the external signals given the vertex marks satisfies

d1(Ξ½(x),Ξ½(x~))≀Kρ(x,x~)forΒ allΒ x,x~∈Sd_1(\nu(\mathbf x),\nu(\tilde{\mathbf x}))\le K\rho(\mathbf x,\tilde{\mathbf x})\qquad\text{for all }\mathbf x,\tilde{\mathbf x}\in\mathcal Sd1​(Ξ½(x),Ξ½(x~))≀Kρ(x,x~)forΒ allΒ x,x~∈S

for some constant K<∞K<\inftyK<∞; assume the same of the kernel Ξ½0\nu_0Ξ½0​ of the initial opinions. Let InI_nIn​ be uniformly chosen in VnV_nVn​. Then there are laws LkL_kLk​ on Rk+1\mathbb R^{k+1}Rk+1, kβ‰₯0k\ge0kβ‰₯0, and Lβˆ—L^*Lβˆ— on R\mathbb RR, none depending on nnn, such that, writing (R(0),…,R(k))∼Lk(\mathcal R^{(0)},\dots,\mathcal R^{(k)})\sim L_k(R(0),…,R(k))∼Lk​ and Rβˆ—βˆΌLβˆ—\mathcal R^*\sim L^*Rβˆ—βˆΌLβˆ—:

  1. for every kβ‰₯0k\ge0kβ‰₯0,
d1(L((RIn(r))0≀r≀k∣An), Lk)β†’P0and1nβˆ‘i=1nf(Ri(k))β†’PE[f(R(k))]d_1\Bigl(\mathcal L\bigl((R^{(r)}_{I_n})_{0\le r\le k}\mid\mathscr A_n\bigr),\,L_k\Bigr)\xrightarrow{P}0\quad\text{and}\quad\frac1n\sum_{i=1}^nf(R_i^{(k)})\xrightarrow{P}E\bigl[f(\mathcal R^{(k)})\bigr]d1​(L((RIn​(r)​)0≀r≀kβ€‹βˆ£An​),Lk​)P​0andn1​i=1βˆ‘n​f(Ri(k)​)P​E[f(R(k))]

for every continuous f:[βˆ’1,1]β†’Rf:[-1,1]\to\mathbb Rf:[βˆ’1,1]β†’R, where d1d_1d1​ uses the sup distance on Rk+1\mathbb R^{k+1}Rk+1; 2. for the stationary vector R=βˆ‘rβ‰₯0Ξ”Λ‰rW(r)R=\sum_{r\ge0}\bar\Delta^rW^{(r)}R=βˆ‘rβ‰₯0​ΔˉrW(r) of each graph,

d1(L(RIn∣An), Lβˆ—)β†’P0and1nβˆ‘i=1nf(Ri)β†’PE[f(Rβˆ—)]d_1\bigl(\mathcal L(R_{I_n}\mid\mathscr A_n),\,L^*\bigr)\xrightarrow{P}0\quad\text{and}\quad\frac1n\sum_{i=1}^nf(R_i)\xrightarrow{P}E\bigl[f(\mathcal R^*)\bigr]d1​(L(RInβ€‹β€‹βˆ£An​),Lβˆ—)P​0andn1​i=1βˆ‘n​f(Ri​)P​E[f(Rβˆ—)]

for every continuous f:[βˆ’1,1]β†’Rf:[-1,1]\to\mathbb Rf:[βˆ’1,1]β†’R; 3. R(k)β‡’Rβˆ—\mathcal R^{(k)}\Rightarrow\mathcal R^*R(k)β‡’Rβˆ— at a geometric rate:

d1(law R(k), Lβˆ—)≀(1βˆ’d)k(2d+2)forΒ everyΒ kβ‰₯0.d_1\bigl(\mathrm{law}\,\mathcal R^{(k)},\,L^*\bigr)\le(1-d)^k\Bigl(\frac2d+2\Bigr)\qquad\text{for every }k\ge0 .d1​(lawR(k),Lβˆ—)≀(1βˆ’d)k(d2​+2)forΒ everyΒ kβ‰₯0.

Items 1 and 2 are the paper's statements that max⁑r≀kE[∣RIn(r)βˆ’R(r)∣∣An]β†’P0\max_{r\le k}E[|R^{(r)}_{I_n}-\mathcal R^{(r)}|\mid\mathscr A_n]\xrightarrow{P}0maxr≀k​E[∣RIn​(r)β€‹βˆ’R(r)∣∣An​]P​0 and E[∣RInβˆ’Rβˆ—βˆ£βˆ£An]β†’P0E[|R_{I_n}-\mathcal R^*|\mid\mathscr A_n]\xrightarrow{P}0E[∣RInβ€‹β€‹βˆ’Rβˆ—βˆ£βˆ£An​]P​0 for random variables whose law does not depend on An\mathscr A_nAn​. Rβˆ—\mathcal R^*Rβˆ— is the "typical" stationary opinion of a large graph: the root opinion of the local limit. By (3), 1nβˆ‘i1(Ri∈A)\frac1n\sum_i\mathbb 1(R_i\in A)n1β€‹βˆ‘i​1(Riβ€‹βˆˆA) is the conditional law of RInR_{I_n}RIn​​ given the graph, so item 2 says that the empirical distribution of stationary opinions does not depend, asymptotically, on the realization of the graph.

Formalization Note

  1. Law form. "There exist R(r)\mathcal R^{(r)}R(r), Rβˆ—\mathcal R^*Rβˆ— whose law does not depend on An\mathscr A_nAn​ with E[βˆ£β‹…βˆ£βˆ£An]β†’P0E[|\cdot|\mid\mathscr A_n]\xrightarrow{P}0E[βˆ£β‹…βˆ£βˆ£An​]P​0" is stated as convergence in probability of the d1d_1d1​ distance between the regular conditional law given An\mathscr A_nAn​ and a fixed law. The two are equivalent: a coupling bounds d1d_1d1​, and conversely a conditionally optimal coupling exists.
  2. Stationary vector. "A vector RRR having the stationary distribution" is the paper's own choice R=βˆ‘rΞ”Λ‰rW(r)R=\sum_r\bar\Delta^rW^{(r)}R=βˆ‘r​ΔˉrW(r) (p. 27), whose law is the stationary law by Theorem 1.
  3. Initial opinions (disclosed addition). The page requires only that R(0)R^{(0)}R(0) be conditionally independent of the signals. Item 1 at r=0r=0r=0 is false for an arbitrary R(0)R^{(0)}R(0) (e.g. R(0)≑(βˆ’1)nR^{(0)}\equiv(-1)^nR(0)≑(βˆ’1)n), and the proof (p. 26) copies R(0)R^{(0)}R(0) from the graph onto the limit. The statement therefore assumes Ri(0)=Ο†(Xi,Vi)R_i^{(0)}=\varphi(\mathbf X_i,V_i)Ri(0)​=Ο†(Xi​,Vi​) with ViV_iVi​ i.i.d. uniform and x↦law φ(x,V)\mathbf x\mapsto\mathrm{law}\,\varphi(\mathbf x,V)x↦lawΟ†(x,V) d1d_1d1​-Lipschitz with the same KKK. This covers the paper's simulations and constant initial vectors. Items 2 and 3 do not involve the initial opinions of the graph.
  4. Rate. The page says only "at a geometric rate"; the constant (1βˆ’d)k(2/d+2)(1-d)^k(2/d+2)(1βˆ’d)k(2/d+2) is the one its proof gives through Theorem 1 on G(X)\mathcal G(\boldsymbol{\mathcal X})G(X) (pp. 23, 28), and d1d_1d1​ is the metric used for weak convergence on [βˆ’1,1][-1,1][βˆ’1,1].
  5. fff is any function continuous on [βˆ’1,1][-1,1][βˆ’1,1]; all opinions lie in [βˆ’1,1][-1,1][βˆ’1,1]. The mmm-th graph of the sequence has m+1m+1m+1 vertices; the limit nβ†’βˆžn\to\inftynβ†’βˆž is unaffected.
  6. Disjoint in-components (added). The strong coupling of the setting requires the depth-kkk in-components of the two uniform vertices to be disjoint on the coupling event, which the proof (p. 25) uses and Definition 4 does not state; without it the empirical-average claims are false (a graph whose vertices all listen to one hub, whose signals then shift every opinion by a common random amount). See the Setting.
Preamble
import Mathlib
import Definitions.Def_DirectedOpinion_Typical_GraphSeq
Formal statement
namespace DirectedOpinion.Typical

open MeasureTheory ProbabilityTheory Set Filter Topology

/-- Theorem 2, pp. 8–9, in law form. Under a strong coupling with a limit graph of law `ΞΌlim`,
with `d > 0`, a signal kernel `Ξ½(x) = law ΞΆ(x, U)` that is `d₁`-Lipschitz in the mark with
constant `K`, and initial opinions `R_i^(0) = Ο†(X_i, V_i)` whose kernel is `d₁`-Lipschitz with the
same `K`, there are laws `L_k` on `ℝ^{k+1}` (`k β‰₯ 0`) and `L*` on `ℝ`, not depending on `m`, with:
1. for every `k`: the `d₁` distance (sup cost) between the conditional law given `π’œ_m` of
   `(R_{I_m}^(0), …, R_{I_m}^(k))` and `L_k` tends to `0` in probability, and for every `f`
   continuous on `[βˆ’1, 1]`, `(1/n) Ξ£_i f(R_i^(k)) β†’ ∫ f(y_k) dL_k(y)` in probability;
2. for the stationary vector `R = Ξ£_r Ξ”Μ„^r W^(r)`: the `d₁` distance between the conditional law
   given `π’œ_m` of `R_{I_m}` and `L*` tends to `0` in probability, and for every `f` continuous on
   `[βˆ’1, 1]`, `(1/n) Ξ£_i f(R_i) β†’ ∫ f dL*` in probability;
3. the time-`k` marginal of `L_k` converges to `L*` at a geometric rate:
   `d₁(L_k ∘ y_k⁻¹, L*) ≀ (1 βˆ’ d)^k (2/d + 2)`. -/
theorem theorem_2 {Ξ© A : Type*} [MeasurableSpace Ξ©] [MetricSpace A] [MeasurableSpace A]
    [BorelSpace A] [PolishSpace A] (P : Measure Ξ©) [IsProbabilityMeasure P] (S : GraphSeq Ξ© A)
    (𝓖 : β„• β†’ MeasurableSpace Ξ©) (ΞΆ Ο† : Mark A β†’ ℝ β†’ ℝ) (c d K : ℝ)
    (ΞΌlim : Measure (LimGraph A)) (hS : GraphSeqModel P S 𝓖 ΞΆ Ο† c d)
    (hSC : StrongCoupling P S 𝓖 ΞΌlim) (hd : 0 < d) (hK : KernelLipschitz ΞΆ K)
    (hK0 : KernelLipschitz Ο† K) :
    βˆƒ (L : (k : β„•) β†’ ProbabilityMeasure (Fin (k + 1) β†’ ℝ)) (Lstar : ProbabilityMeasure ℝ),
      (βˆ€ k : β„•,
        (βˆ€ Ξ· : ℝ, 0 < Ξ· β†’
          Tendsto (fun m => P {Ο‰ | ENNReal.ofReal Ξ· ≀
              W1vec (trajCondLaw P S ΞΆ Ο† c d m k Ο‰) (L k : Measure (Fin (k + 1) β†’ ℝ))})
            atTop (𝓝 0)) ∧
        βˆ€ f : ℝ β†’ ℝ, ContinuousOn f (Icc (-1 : ℝ) 1) β†’
          TendstoInMeasure P (fun m Ο‰ => empAvg f (S.R ΞΆ Ο† c d m k Ο‰)) atTop
            (fun _ => ∫ y, f (y (Fin.last k)) βˆ‚(L k : Measure (Fin (k + 1) β†’ ℝ)))) ∧
      ((βˆ€ Ξ· : ℝ, 0 < Ξ· β†’
          Tendsto (fun m => P {Ο‰ | ENNReal.ofReal Ξ· ≀
              W1 (statCondLaw P S ΞΆ c d m Ο‰) (Lstar : Measure ℝ)})
            atTop (𝓝 0)) ∧
        βˆ€ f : ℝ β†’ ℝ, ContinuousOn f (Icc (-1 : ℝ) 1) β†’
          TendstoInMeasure P (fun m Ο‰ => empAvg f (S.Rstat ΞΆ c d m Ο‰)) atTop
            (fun _ => ∫ y, f y βˆ‚(Lstar : Measure ℝ))) ∧
      βˆ€ k : β„•,
        W1 ((L k : Measure (Fin (k + 1) β†’ ℝ)).map (fun y => y (Fin.last k))) (Lstar : Measure ℝ) ≀
          ENNReal.ofReal ((1 - d) ^ k * (2 / d + 2)) := by sorry

end DirectedOpinion.Typical
Source
Fraiman, Lin and Olvera-Cravioto, Opinion dynamics on directed complex networks, arXiv:2209.00969v2, pp. 8–9, Theorem 2
Human review
  • Endorsed by Shuze Chen Β· Oct 14, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 Β· Oct 14, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
Β© 2026 Prove2Me