Documentation

Plurality.AnyStart

Two opinions from any configuration #

Binary 3-Majority reaches consensus from any configuration, including the perfectly balanced one, within O(log n) rounds with high probability (Becchetti, Clementi, Natale, Consensus dynamics: an overview, SIGACT News 2020, §4 Case 3, where the argument is given for the binary median dynamics of Doerr, Goldberg, Minder, Sauerwald, Scheideler, SPAA 2011).

The gap s = |I| - (n - |I|) evolves in two stages.

noncomputable def Plurality.gap {n : ℕ} (I : Finset (Fin n)) :

The gap |I| - (n - |I|) between the nodes holding opinion 1 (the set I) and the others.

Equations
Instances For
    noncomputable def Plurality.binKernel (n : ℕ) [NeZero n] :

    Binary 3-Majority as a finite Markov kernel on the set of nodes holding opinion 1.

    Equations
    Instances For

      The gap and the complement symmetry #

      theorem Plurality.card_le_n {n : ℕ} (I : Finset (Fin n)) :
      ↑I.card ≤ ↑n
      theorem Plurality.abs_gap_le {n : ℕ} (I : Finset (Fin n)) :
      |gap I| ≤ ↑n
      theorem Plurality.gap_compl {n : ℕ} (I : Finset (Fin n)) :

      Exchanging the two opinions commutes with a round.

      theorem Plurality.prob_binKernel_compl {n : ℕ} [NeZero n] (P : Finset (Fin n) → Prop) (I : Finset (Fin n)) :
      (binKernel n Iᶜ).prob P = (binKernel n I).prob fun (J : Finset (Fin n)) => P Jᶜ
      theorem Plurality.gap_step {n : ℕ} (I : Finset (Fin n)) (r : ThreeMajority.Tgt3 n) :
      gap (ThreeMajority.step I r) = 2 * ∑ v : Fin n, ThreeMajority.Y_maj I v (r v) - ↑n

      gap (step I r) = 2 ∑ᵥ Yᵥ - n for the independent {0,1} contributions Yᵥ of the nodes.

      The mean of the next gap #

      theorem Plurality.avg_Y_maj {n : ℕ} [NeZero n] (I : Finset (Fin n)) (v : Fin n) :
      Dynamics.avg (ThreeMajority.Y_maj I v) = 3 * (↑I.card / ↑n) ^ 2 - 2 * (↑I.card / ↑n) ^ 3

      The probability p = 3x² - 2x³ that a node adopts opinion 1, with x = |I|/n.

      theorem Plurality.two_mul_sum_avg_sub {n : ℕ} [NeZero n] (I : Finset (Fin n)) :
      2 * ∑ v : Fin n, Dynamics.avg (ThreeMajority.Y_maj I v) - ↑n = gap I * (3 / 2 - (gap I / ↑n) ^ 2 / 2)

      The mean of the next gap is n (2p - 1) = s (3/2 - s²/(2n²)) for the gap s.

      theorem Plurality.abs_mean_le {n : ℕ} [NeZero n] (I : Finset (Fin n)) :
      |2 * ∑ v : Fin n, Dynamics.avg (ThreeMajority.Y_maj I v) - ↑n| ≤ 3 / 2 * |gap I|

      The mean of the next gap is at most 3|s|/2 in absolute value.

      theorem Plurality.mean_ge {n : ℕ} [NeZero n] (I : Finset (Fin n)) (h0 : 0 ≤ gap I) (h1 : gap I ≤ ↑n / 2) :
      11 / 8 * gap I ≤ 2 * ∑ v : Fin n, Dynamics.avg (ThreeMajority.Y_maj I v) - ↑n

      For 0 ≤ s ≤ n/2 the mean of the next gap is at least 11 s/8.

      theorem Plurality.jump_near_balance {n : ℕ} [NeZero n] (hn : 5 ≤ n) (I : Finset (Fin n)) (hI : |gap I| ≤ 4 * √↑n / 25) :
      9 / 64 ≤ (binKernel n I).prob fun (J : Finset (Fin n)) => √↑n / 5 ≤ |gap J|

      A √n jump near balance (the variance of one round). If the gap is at most 4√n/25 in absolute value and n ≥ 5, then after one round it is at least √n/5 in absolute value with probability at least 9/64.

      theorem Plurality.growth_far {n : ℕ} [NeZero n] (I : Finset (Fin n)) (h0 : 0 ≤ gap I) (h1 : gap I ≤ ↑n / 2) {lam : ℝ} (hlam : 0 ≤ lam) :
      1 - Real.exp (-(2 * lam ^ 2 / ↑n)) ≤ (binKernel n I).prob fun (J : Finset (Fin n)) => 11 / 8 * gap I - 2 * lam < gap J

      Growth above √n (the drift of one round, with Hoeffding's inequality). If 0 ≤ s ≤ n/2 for the gap s, then for every λ ≥ 0 the next gap exceeds 11 s/8 - 2λ except with probability at most exp (-2λ²/n).

      Symmetry breaking: the hypotheses of the hitting-time bound #

      noncomputable def Plurality.gapUnits {n : ℕ} (I : Finset (Fin n)) :

      The absolute gap in units of √n / 100, rounded down: the observable X to which the hitting-time bound is applied.

      Equations
      Instances For
        theorem Plurality.unit_pos {n : ℕ} [NeZero n] :
        0 < √↑n / 100
        theorem Plurality.gapUnits_mul_le {n : ℕ} [NeZero n] (I : Finset (Fin n)) :
        ↑(gapUnits I) * (√↑n / 100) ≤ |gap I|
        theorem Plurality.lt_gapUnits_add_one {n : ℕ} [NeZero n] (I : Finset (Fin n)) :
        |gap I| < (↑(gapUnits I) + 1) * (√↑n / 100)
        theorem Plurality.le_gapUnits {n : ℕ} [NeZero n] {k : ℕ} {I : Finset (Fin n)} (h : ↑k * (√↑n / 100) ≤ |gap I|) :
        theorem Plurality.sqrt_ge_of_log {n : ℕ} (hL : 40 ≤ Real.log ↑n) :
        0 < ↑n ∧ 20 * Real.log ↑n + 1 ≤ √↑n

        For log n ≥ 40: n > 0 and √n ≥ 20 log n + 1, from √n = e^{(log n)/2} ≥ (log n)⁴/384.

        theorem Plurality.units_near {n : ℕ} [NeZero n] (hL : 40 ≤ Real.log ↑n) (I : Finset (Fin n)) (hI : gapUnits I < 16) :
        9 / 64 ≤ (binKernel n I).prob fun (J : Finset (Fin n)) => 20 ≤ gapUnits J

        Near balance (1 ≤ X < 16, where the gap is below 4√n/25): with probability at least 9/64 the next gap is at least √n/5, so X jumps to at least 20 ≥ 5X/4.

        theorem Plurality.units_far {n : ℕ} [NeZero n] (hL : 40 ≤ Real.log ↑n) (I : Finset (Fin n)) (hg : 0 ≤ gap I) (h16 : 16 ≤ gapUnits I) (hI : ↑(gapUnits I) < 1000 * Real.log ↑n) :
        1 - Real.exp (-(1 / 320000 * ↑(gapUnits I))) ≤ (binKernel n I).prob fun (J : Finset (Fin n)) => 5 / 4 * ↑(gapUnits I) ≤ ↑(gapUnits J)

        Above √n (16 ≤ X < 1000 log n, gap ≥ 0): by growth_far with λ = X √n / 3200, X grows to at least 5X/4 except with probability exp (-X²/5120000) ≤ exp (-X/320000).

        theorem Plurality.units_grow {n : ℕ} [NeZero n] (hL : 40 ≤ Real.log ↑n) (I : Finset (Fin n)) (hI : ↑(gapUnits I) < 1000 * Real.log ↑n) :
        1 - Real.exp (-(1 / 320000 * ↑(gapUnits I))) ≤ (binKernel n I).prob fun (J : Finset (Fin n)) => min (5 / 4 * ↑(gapUnits I)) ↑n ≤ ↑(gapUnits J)

        The growth hypothesis of the hitting-time bound: below the target, X grows to at least min (5X/4) n with probability at least 1 - exp (-X/320000).

        theorem Plurality.majority3_symmetry_breaking :
        ∃ (C : ℝ), 0 < C ∧ ∀ (n : ℕ) [inst : NeZero n], 40 ≤ Real.log ↑n → ∀ (I₀ : Finset (Fin n)) (t : ℕ), C * Real.log ↑n ≤ ↑t → 1 - 1 / ↑n ≤ (binKernel n).hitProb (fun (I : Finset (Fin n)) => 22 * √(3 * ↑n * Real.log ↑n) ≤ |gap I|) t I₀

        Symmetry breaking. There is C > 0 such that, for log n ≥ 40, from any configuration I₀ the gap reaches 22 √(3 n log n) in absolute value within any t ≥ C log n rounds with probability at least 1 - 1/n.

        Consensus absorbs; the vanishing-bias stage as a kernel event #

        theorem Plurality.consensus_absorbing {n : ℕ} [NeZero n] (I : Finset (Fin n)) (hI : I = Finset.univ ∨ I = ∅) :
        ((binKernel n I).prob fun (J : Finset (Fin n)) => J = Finset.univ ∨ J = ∅) = 1

        Consensus on either opinion is absorbing.

        The occupation probability of consensus, as an expectation over rounds.

        theorem Plurality.event_consensus_of_gap {n : ℕ} [NeZero n] (hL : 40 ≤ Real.log ↑n) (I : Finset (Fin n)) (hI : 22 * √(3 * ↑n * Real.log ↑n) ≤ |gap I|) :
        1 - 429 * Real.log ↑n / ↑n ≤ (binKernel n).event (fun (J : Finset (Fin n)) => J = Finset.univ ∨ J = ∅) (10 * phases n 3) I

        The vanishing-bias stage (majority3_vanishing_bias, applied to I or to its complement): from a gap at least 22 √(3 n log n) in absolute value, consensus holds after 10 · phases n 3 ≤ 390 log n rounds with probability at least 1 - 429 log n / n.

        theorem Plurality.majority3_any_start :
        ∃ (C : ℝ), 0 < C ∧ ∀ (n : ℕ), 40 ≤ Real.log ↑n → ∀ (I₀ : Finset (Fin n)) (T : ℕ), C * Real.log ↑n ≤ ↑T → 1 - C * Real.log ↑n / ↑n ≤ Dynamics.expList (ThreeMajority.Tgt3 n) T fun (l : List (ThreeMajority.Tgt3 n)) => if ThreeMajority.run I₀ l = Finset.univ ∨ ThreeMajority.run I₀ l = ∅ then 1 else 0

        Binary 3-Majority from any configuration. There is C > 0 such that, for log n ≥ 40, from any configuration I₀ (in particular from a perfectly balanced one), all nodes hold the same opinion after any T ≥ C log n rounds with probability at least 1 - C log n / n.

        theorem Plurality.majority3_any_start_whp :
        ∃ (C : ℝ), 0 < C ∧ ∀ (n : ℕ), C ≤ Real.log ↑n → ∀ (I₀ : Finset (Fin n)) (T : ℕ), C * Real.log ↑n ≤ ↑T → 1 - 1 / ↑n ≤ Dynamics.expList (ThreeMajority.Tgt3 n) T fun (l : List (ThreeMajority.Tgt3 n)) => if ThreeMajority.run I₀ l = Finset.univ ∨ ThreeMajority.run I₀ l = ∅ then 1 else 0

        Binary 3-Majority from any configuration, with high probability. There is C > 0 such that, for log n ≥ C, from any configuration I₀ all nodes hold the same opinion after any T ≥ C log n rounds with probability at least 1 - 1/n. It runs majority3_any_start twice: each block fails with probability at most ε = C₀ log n / n from every configuration, and consensus absorbs, so both fail with probability at most ε² ≤ 1/n.