Documentation

ThreeMajority.AnyStartMain

3-Majority from any configuration (BCEKMN17, Theorem 4; roadmap MAJ-6, part (b)) #

Theorem 4 of Berenbrink, Clementi, Elsässer, Kling, Mallmann-Trenn, Natale (PODC 2017, arXiv:1702.04921): from any configuration, 3-Majority reaches consensus w.h.p. within O(n^{3/4} log^{7/8} n) rounds. The proof has two phases.

theorem ThreeMajority.expList_lt_eq_one_sub {α : Type u_1} [Fintype α] [Nonempty α] (T k : ℕ) (F : List α → ℕ) :
(expList α T fun (l : List α) => if k < F l then 1 else 0) = 1 - expList α T fun (l : List α) => if F l ≤ k then 1 else 0

The probability of k < F is one minus that of F ≤ k.

theorem ThreeMajority.threeMaj_reduce_whp {n : ℕ} {σ : Type u_1} [Finite σ] [DecidableEq σ] (hn : 2 ≤ n) (c : Fin n → σ) {k : ℕ} (hk : 1 ≤ k) {T : ℕ} (hT : 24 * (↑n / ↑k) * Real.log ↑n ≤ ↑T) :
(expList (Tgt3 n) T fun (l : List (Tgt3 n)) => if k < numColours (runCol c l) then 1 else 0) ≤ 1 / ↑n

Phase 1 of Theorem 4 (BCEKMN17, Section 3, from Lemmas 2 and 3): from any configuration, 3-Majority has at most k colours after any T ≥ 24 (n/k) log n rounds, with probability at least 1 − 1/n.

Theorem 8 of BCEKMN17 (Theorem 3.1 of Becchetti, Clementi, Natale, Pasquale, Trevisan, SODA 2016), for one ε, as a hypothesis: there are constants C, N such that for n ≥ N, from any configuration of colours in [n] with k ≤ n^{1/3 − ε} colours, 3-Majority reaches consensus within any T ≥ C (k² log^{1/2} n + k log n)(k + log n) rounds, with probability at least 1 − 1/n. It holds for every ε > 0 (bcnpt16Phase2_of_pos, in ManyOpinionsMain.lean).

Equations
  • One or more equations did not get rendered due to their size.
Instances For
    theorem ThreeMajority.threeMaj_anyStart_consensus (h : Bcnpt16Phase2 (1 / 24)) :
    ∃ (C : ℝ) (N : ℝ), ∀ (n : ℕ), N ≤ ↑n → ∀ (c : Fin n → Fin n) (T : ℕ), C * ↑n ^ (3 / 4) * Real.log ↑n ^ (7 / 8) ≤ ↑T → (expList (Tgt3 n) T fun (l : List (Tgt3 n)) => if numColours (runCol c l) ≤ 1 then 0 else 1) ≤ 2 / ↑n

    Theorem 4 (BCEKMN17): from any configuration of colours in [n], 3-Majority reaches consensus within any T ≥ C n^{3/4} log^{7/8} n rounds with probability at least 1 − 2/n, for n ≥ N. The cited Phase 2 result (Theorem 8, for ε = 1/24) is a hypothesis here; threeMaj_anyStart_consensus_unconditional (in ManyOpinionsMain.lean) discharges it.