Documentation

ThreeMajority.ManyOpinionsDropping

The dropping stage (BCNPT16, Lemmas 3.4 and 3.5; roadmap MAJ-12 (a)) #

Becchetti, Clementi, Natale, Pasquale, Trevisan, Stabilizing consensus with many opinions, SODA 2016, arXiv:1508.06782 (BCNPT16 below), Section 3. Once a colour a is below n/j − 16 √(j n log n) agents in a configuration with at most j colours, Lemma 2.1 makes it shrink geometrically: its gap to the average n/j grows by a factor 1 + 1/(4j) per round, and below n/(2j) the support itself shrinks by a factor 1 − 1/(2j).

One-round estimates (Chernoff upper tails, avg_colourCount_stepCol_ge): below n/(2j) the support shrinks by 1 − 1/(4j) (avg_colourCount_stepCol_ge_shrink), between n/(2j) and n/j the gap to n/j grows by 1 + 1/(4j) (avg_colourCount_stepCol_ge_gap). Lemma 3.4 follows them along one moving target stage1Level (stage1_step, Dynamics.expList_escape); Lemma 3.5 iterates the contraction of min(c_a, n/(2j)) (expList_min_colourCount_le, BCNPT16, Appendix B) and applies Markov's inequality.

Both assume C j³ log n ≤ n, implied by the paper's j ≤ n^{1/3 − ε} for large n. The proof of Lemma 3.4 needs a minor correction: from the paper's threshold n/j − √(j n log n) the one-round Chernoff bound (Appendix B, Equation (7)) only gives failure probability n^{-1/12}, still at least n^{-1/10} during the first j/10 rounds, so the iterated union bound exceeds 1 as soon as j ≥ 20 n^{1/10}, and the same happens near the floor j² log n. With the threshold n/j − 16 √(j n log n) and the floor C j² log n for a large C the failure is at most n^{-5} per round.

theorem ThreeMajority.avg_colourCount_stepCol_le_half {n : ℕ} [NeZero n] {y : Fin n → Fin n} {a : Fin n} {j : ℕ} (hj : 1 ≤ j) (hy : numColours y ≤ j) {b : ℝ} (hb0 : 0 ≤ b) (hb : b ≤ ↑n / (2 * ↑j)) (hya : ↑(colourCount y a) ≤ b) :
(avg fun (r : Tgt3 n) => ↑(colourCount (stepCol y r) a)) ≤ (1 - 1 / (2 * ↑j)) * b

From at most j colours and c_a ≤ b ≤ n/(2j), the expected new support of a is at most (1 − 1/(2j)) b (Lemma 2.1).

theorem ThreeMajority.avg_colourCount_stepCol_ge_shrink {n : ℕ} [NeZero n] {y : Fin n → Fin n} {a : Fin n} {j : ℕ} (hj : 1 ≤ j) (hy : numColours y ≤ j) {b : ℝ} (hb0 : 0 < b) (hb : b ≤ ↑n / (2 * ↑j)) (hya : ↑(colourCount y a) ≤ b) :
(avg fun (r : Tgt3 n) => if b * (1 - 1 / (4 * ↑j)) ≤ ↑(colourCount (stepCol y r) a) then 1 else 0) ≤ Real.exp (-(b / (32 * ↑j ^ 2)))

One round below n/(2j) (Chernoff upper tail): from at most j colours and c_a ≤ b ≤ n/(2j), the new support of a reaches b (1 − 1/(4j)) with probability at most exp(−b/(32 j²)).

theorem ThreeMajority.avg_min_colourCount_stepCol_le {n : ℕ} [NeZero n] {y : Fin n → Fin n} {a : Fin n} {j : ℕ} (hj : 1 ≤ j) (hy : numColours y ≤ j) :
(avg fun (r : Tgt3 n) => min (↑(colourCount (stepCol y r) a)) (↑n / (2 * ↑j))) ≤ (1 - 1 / (2 * ↑j)) * min (↑(colourCount y a)) (↑n / (2 * ↑j)) + ↑n / (4 * ↑j ^ 2) * if ↑n / (2 * ↑j) < ↑(colourCount y a) then 1 else 0

The potential ψ = min(c_a, n/(2j)) of Lemma 3.5 contracts by 1 − 1/(2j) per round, up to the event that c_a is above n/(2j).

theorem ThreeMajority.expList_colourCount_gt_half_le {n : ℕ} [NeZero n] {x : Fin n → Fin n} {a : Fin n} {j : ℕ} (hx : numColours x ≤ j) (hxa : ↑(colourCount x a) ≤ ↑n / (2 * ↑j)) {ε : ℝ} (hε : 0 ≤ ε) (hesc : ∀ (y : Fin n → Fin n), numColours y ≤ j → ↑(colourCount y a) ≤ ↑n / (2 * ↑j) → (avg fun (r : Tgt3 n) => if ↑n / (2 * ↑j) < ↑(colourCount (stepCol y r) a) then 1 else 0) ≤ ε) (s : ℕ) :
(expList (Tgt3 n) s fun (l : List (Tgt3 n)) => if ↑n / (2 * ↑j) < ↑(colourCount (runCol x l) a) then 1 else 0) ≤ ↑s * ε

Union bound over rounds: from c_a ≤ n/(2j) and at most j colours, if every round from such a state takes c_a above n/(2j) with probability at most ε, then after s rounds c_a > n/(2j) with probability at most s ε.

theorem ThreeMajority.expList_min_colourCount_le {n : ℕ} [NeZero n] {x : Fin n → Fin n} {a : Fin n} {j : ℕ} (hj : 1 ≤ j) (hx : numColours x ≤ j) (hxa : ↑(colourCount x a) ≤ ↑n / (2 * ↑j)) {ε : ℝ} (hε : 0 ≤ ε) (hesc : ∀ (y : Fin n → Fin n), numColours y ≤ j → ↑(colourCount y a) ≤ ↑n / (2 * ↑j) → (avg fun (r : Tgt3 n) => if ↑n / (2 * ↑j) < ↑(colourCount (stepCol y r) a) then 1 else 0) ≤ ε) (s : ℕ) :
(expList (Tgt3 n) s fun (l : List (Tgt3 n)) => min (↑(colourCount (runCol x l) a)) (↑n / (2 * ↑j))) ≤ (1 - 1 / (2 * ↑j)) ^ s * (↑n / (2 * ↑j)) + ↑n / (4 * ↑j ^ 2) * ε * ↑s ^ 2

The recursion of Lemma 3.5 (BCNPT16, Appendix B): 𝔼 ψ(x_s) ≤ (1 − 1/(2j))^s n/(2j) + (n/(4j²)) ε s².

theorem ThreeMajority.avg_colourCount_stepCol_ge_gap {n : ℕ} [NeZero n] {y : Fin n → Fin n} {a : Fin n} {j : ℕ} (hj : 1 ≤ j) (hy : numColours y ≤ j) {b : ℝ} (hb : ↑n / (2 * ↑j) < b) (hg : 0 < ↑n / ↑j - b) (hya : ↑(colourCount y a) ≤ b) :
(avg fun (r : Tgt3 n) => if b - (↑n / ↑j - b) / (4 * ↑j) ≤ ↑(colourCount (stepCol y r) a) then 1 else 0) ≤ Real.exp (-((↑n / ↑j - b) ^ 2 / (32 * ↑j * ↑n)))

One round between n/(2j) and n/j (Chernoff upper tail): from at most j colours and c_a ≤ b with n/(2j) < b < n/j, the gap g = n/j − b grows by a factor 1 + 1/(4j) except with probability at most exp(−g²/(32 j n)): the new support of a reaches b − g/(4j) with at most that probability (the mean is at most b − g/(2j)).

noncomputable def ThreeMajority.stage1Level (n j : ℕ) (m K : ℝ) (sA s : ℕ) :

The target levels of the proof of Lemma 3.4 (BCNPT16, Appendix B, with the corrections listed in FORMALIZATION_DIFFERENCES.md): max(n/j − m (1 + 1/(4j))^s, (n/(2j)) (1 − 1/(4j))^(s − s_A), K). The first term is the gap-growth block (until c_a ≤ n/(2j)), the second the geometric decrease from n/(2j) (after round s_A), and K the floor.

Equations
Instances For
    theorem ThreeMajority.stage1_step {n : ℕ} [NeZero n] {y : Fin n → Fin n} {a : Fin n} {j : ℕ} (hj : 1 ≤ j) (hy : numColours y ≤ j) {m K : ℝ} {sA : ℕ} (hm : 0 < m) (hmL : 64 * ↑j * ↑n * Real.log ↑n ≤ m ^ 2) (hK : 64 * ↑j ^ 2 * Real.log ↑n ≤ K) (hK0 : 0 < K) (hKn : K ≤ ↑n / (2 * ↑j)) (hsA : ∀ (s : ℕ), sA ≤ s → ↑n / ↑j ≤ m * (1 + 1 / (4 * ↑j)) ^ s) (s : ℕ) (hya : ↑(colourCount y a) ≤ stage1Level n j m K sA s) :
    (avg fun (r : Tgt3 n) => if stage1Level n j m K sA (s + 1) < ↑(colourCount (stepCol y r) a) then 1 else 0) ≤ Real.exp (-(2 * Real.log ↑n))

    One round along the schedule of Lemma 3.4: from at most j colours and c_a below the level of round s, the new support of a exceeds the level of round s + 1 with probability at most 1/n² (exp(−2 log n)). Above n/(2j) the level is n/j − m (1 + 1/(4j))^s and the gap grows (avg_colourCount_stepCol_ge_gap); below, it shrinks by 1 − 1/(4j) down to the floor K ≥ 64 j² log n (avg_colourCount_stepCol_ge_shrink).

    theorem ThreeMajority.dropping_stage1 :
    ∃ (C : ℝ), ∀ (n j : ℕ) (x : Fin n → Fin n) (a : Fin n), 2 ≤ j → C * ↑j ^ 3 * Real.log ↑n ≤ ↑n → numColours x ≤ j → ↑(colourCount x a) ≤ ↑n / ↑j - 16 * √(↑j * ↑n * Real.log ↑n) → ∀ (t : ℕ), C * ↑j * Real.log ↑n ≤ ↑t → t ≤ n → (expList (Tgt3 n) t fun (l : List (Tgt3 n)) => if C * ↑j ^ 2 * Real.log ↑n < ↑(colourCount (runCol x l) a) then 1 else 0) ≤ 1 / ↑n

    Lemma 3.4 (BCNPT16, dropping stage 1): there is C such that, for j ≥ 2 with C j³ log n ≤ n, from every configuration x with at most j colours and every colour a with at most n/j − 16 √(j n log n) agents, at every time t with C j log n ≤ t ≤ n colour a has more than C j² log n agents with probability at most 1/n.

    theorem ThreeMajority.dropping_stage2 :
    ∃ (C : ℝ), ∀ (n j : ℕ) (x : Fin n → Fin n) (a : Fin n), 2 ≤ j → C * ↑j ^ 3 * Real.log ↑n ≤ ↑n → numColours x ≤ j → ↑(colourCount x a) ≤ ↑n / (2 * ↑j) → ∀ (t : ℕ), C * ↑j * Real.log ↑n ≤ ↑t → 1 / 2 ≤ expList (Tgt3 n) t fun (l : List (Tgt3 n)) => if colourCount (runCol x l) a = 0 then 1 else 0

    Lemma 3.5 (BCNPT16, dropping stage 2): there is C such that, for j ≥ 2 with C j³ log n ≤ n, from every configuration x with at most j colours and every colour a with at most n/(2j) agents, colour a has died after any t ≥ C j log n rounds with probability at least 1/2.