Documentation

ThreeMajority.ManyOpinionsBreaking

The symmetry-breaking stage (BCNPT16, Lemma 3.3; roadmap MAJ-12 (a)) #

Becchetti, Clementi, Natale, Pasquale, Trevisan, Stabilizing consensus with many opinions, SODA 2016, arXiv:1508.06782 (BCNPT16 below), Section 3. From a configuration with j colours, the smallest support c_π•ž drifts down by Ξ΄ √n / j^{3/2} per round (Equation (3)) as long as every colour has more than n/j βˆ’ 16 √(j n log n) agents, and one round overshoots below n/j βˆ’ 64 √(j n log n) with probability at most 1/nΒ² (Equation (6), Lemma B.1). The additive drift lemma (hitProb_additive_drift, Lemma 3.2) then gives Lemma 3.3: within O(jΒ² √(log n)) rounds, with probability at least 1/2, some colour falls to n/j βˆ’ 16 √(j n log n) agents or dies.

Equation (6) is a Chernoff lower tail at n/j βˆ’ 64 √(j n log n) with mean at least n/j βˆ’ 32 √(j n log n) (le_avg_colourCount_stepCol_of_forall_lt) and a union bound over the colours. Equation (3) has two cases: far from uniform, Lemma 2.1 for the smallest colour (Equation (5)); near uniform, the paper's Central Limit Theorem step (Equation (4)) is replaced by the pointwise bound min_a C_a' ≀ n/j βˆ’ (1/(2j)) βˆ‘_a |C_a' βˆ’ n/j| (inf'_colourCount_le) and the anti-concentration 𝔼|C_a' βˆ’ n/j| β‰₯ (9/256) Οƒ_a (avg_abs_colourCount_stepCol_sub_ge, Paley–Zygmund) with Οƒ_aΒ² β‰₯ n/(4j) (sum_variance_adoptInd_ge).

The paper assumes nothing on j in Lemma 3.3, but its proof uses c_π•ž β‰₯ n/(2j) whenever c_π•ž > n/j βˆ’ √(j n log n), which needs jΒ³ log n = O(n); the statements here assume C jΒ³ log n ≀ n (implied by the standing assumption j ≀ n^{1/3 βˆ’ Ξ΅} of Section 3 for large n). The threshold is 16 √(j n log n) instead of √(j n log n), for the dropping stage (Lemma 3.4, dropping_stage1).

def ThreeMajority.BrokenSymmetry {n : β„•} {Οƒ : Type u_1} [DecidableEq Οƒ] (j : β„•) (x : Fin n β†’ Οƒ) :

The exit condition of the symmetry-breaking stage for j colours (BCNPT16, Lemma 3.3, with the threshold 16 √(j n log n)): fewer than j colours remain, or at most j colours remain and one of them has between 1 and n/j βˆ’ 16 √(j n log n) agents.

Equations
  • One or more equations did not get rendered due to their size.
Instances For
    theorem ThreeMajority.brokenSymmetry_iff {n : β„•} {Οƒ : Type u_1} [DecidableEq Οƒ] (j : β„•) (x : Fin n β†’ Οƒ) :
    BrokenSymmetry j x ↔ numColours x < j ∨ numColours x ≀ j ∧ βˆƒ (a : Οƒ), 0 < colourCount x a ∧ ↑(colourCount x a) ≀ ↑n / ↑j - 16 * √(↑j * ↑n * Real.log ↑n)

    BrokenSymmetry unfolded. (Pinned, so that the definition is frozen together with the statements that use it.)

    A configuration of n β‰₯ 1 agents has a colour.

    theorem ThreeMajority.card_mul_inf'_colourCount_le {n : β„•} [NeZero n] (x : Fin n β†’ Fin n) :
    (↑(numColours x) * (Finset.image x Finset.univ).inf' β‹― fun (a : Fin n) => ↑(colourCount x a)) ≀ ↑n

    The smallest support among the colours of x, at most the average n / numColours x.

    noncomputable def ThreeMajority.breakPotential {n : β„•} [NeZero n] (j : β„•) (y : Fin n β†’ Fin n) :

    The potential of the symmetry-breaking stage for j colours.

    Equations
    Instances For
      theorem ThreeMajority.breakPotential_eq {n : β„•} [NeZero n] {j : β„•} (x : Fin n β†’ Fin n) (hx : numColours x = j) (y : Fin n β†’ Fin n) (hy : Finset.image y Finset.univ βŠ† Finset.image x Finset.univ) :
      breakPotential j y = ↑n / ↑j - (Finset.image x Finset.univ).inf' β‹― fun (a : Fin n) => ↑(colourCount y a)

      After rounds from x with j colours, the potential is n/j minus the smallest support among the colours of x (dead colours count 0).

      theorem ThreeMajority.not_brokenSymmetry {n j : β„•} {x : Fin n β†’ Fin n} (hI : numColours x ≀ j) (hB : Β¬BrokenSymmetry j x) :
      numColours x = j ∧ βˆ€ a ∈ Finset.image x Finset.univ, ↑n / ↑j - 16 * √(↑j * ↑n * Real.log ↑n) < ↑(colourCount x a)

      Outside BrokenSymmetry j, a configuration with at most j colours has exactly j colours, all above the threshold.

      theorem ThreeMajority.min_count_drift :
      βˆƒ (Ξ΄ : ℝ) (C : ℝ), 0 < Ξ΄ ∧ βˆ€ (n : β„•) (x : Fin n β†’ Fin n), 2 ≀ numColours x β†’ C * ↑(numColours x) ^ 3 * Real.log ↑n ≀ ↑n β†’ (βˆ€ a ∈ Finset.image x Finset.univ, ↑n / ↑(numColours x) - 16 * √(↑(numColours x) * ↑n * Real.log ↑n) < ↑(colourCount x a)) β†’ βˆ€ (h : (Finset.image x Finset.univ).Nonempty), (avg fun (r : Tgt3 n) => (Finset.image x Finset.univ).inf' h fun (a : Fin n) => ↑(colourCount (stepCol x r) a)) ≀ ((Finset.image x Finset.univ).inf' h fun (a : Fin n) => ↑(colourCount x a)) - Ξ΄ * βˆšβ†‘n / (↑(numColours x) * βˆšβ†‘(numColours x))

      Equation (3) (BCNPT16, proof of Lemma 3.3, Hypothesis 1 of Lemma 3.2): there are constants Ξ΄ > 0 and C such that, for every configuration x with j β‰₯ 2 colours, C jΒ³ log n ≀ n and every colour above n/j βˆ’ 16 √(j n log n) agents, the smallest support among the colours of x decreases in expectation by at least Ξ΄ √n / j^{3/2} in one round (a colour that dies counts with support 0).

      theorem ThreeMajority.min_count_overshoot :
      βˆƒ (C : ℝ), βˆ€ (n : β„•) (x : Fin n β†’ Fin n), 2 ≀ numColours x β†’ C * ↑(numColours x) ^ 3 * Real.log ↑n ≀ ↑n β†’ (βˆ€ a ∈ Finset.image x Finset.univ, ↑n / ↑(numColours x) - 16 * √(↑(numColours x) * ↑n * Real.log ↑n) < ↑(colourCount x a)) β†’ (avg fun (r : Tgt3 n) => if βˆƒ a ∈ Finset.image x Finset.univ, ↑(colourCount (stepCol x r) a) < ↑n / ↑(numColours x) - 64 * √(↑(numColours x) * ↑n * Real.log ↑n) then 1 else 0) ≀ 1 / ↑n ^ 2

      Equation (6) (BCNPT16, proof of Lemma 3.3, Hypothesis 2 of Lemma 3.2; Lemma B.1), in one-step form: there is C such that, for every configuration x with j β‰₯ 2 colours, C jΒ³ log n ≀ n and every colour above n/j βˆ’ 16 √(j n log n) agents, after one round some colour of x is below n/j βˆ’ 64 √(j n log n) agents with probability at most 1/nΒ².

      theorem ThreeMajority.symmetry_breaking :
      βˆƒ (C : ℝ), βˆ€ (n : β„•) [inst : NeZero n] (c : Fin n β†’ Fin n), 2 ≀ numColours c β†’ C * ↑(numColours c) ^ 3 * Real.log ↑n ≀ ↑n β†’ βˆ€ (t : β„•), C * ↑(numColours c) ^ 2 * √(Real.log ↑n) ≀ ↑t β†’ 1 / 2 ≀ (Dynamics.Kernel.ofStep stepCol).hitProb (BrokenSymmetry (numColours c)) t c

      Lemma 3.3 (BCNPT16, symmetry-breaking stage): there is C such that, from every configuration c with j β‰₯ 2 colours and C jΒ³ log n ≀ n, 3-Majority reaches BrokenSymmetry j (some colour falls to n/j βˆ’ 16 √(j n log n) agents, or dies) within any t β‰₯ C jΒ² √(log n) rounds with probability at least 1/2.