Documentation

ThreeMajority.ManyOpinionsTails

One-round tails of 3-Majority with many colours (roadmap MAJ-12 (a)) #

Tools for the one-round estimates of BCNPT16 (Becchetti, Clementi, Natale, Pasquale, Trevisan, Stabilizing consensus with many opinions, SODA 2016, arXiv:1508.06782), Section 3 and Appendix B, for the model stepCol of ThreeMajority.AnyStartModel.

theorem ThreeMajority.mul_sqrt_le_div {n j : ℕ} {D : ℝ} (hD : 0 ≤ D) (hj : 0 < ↑j) (h : D ^ 2 * ↑j ^ 3 * Real.log ↑n ≤ ↑n) :
D * √(↑j * ↑n * Real.log ↑n) ≤ ↑n / ↑j

From D² j³ log n ≤ n: D √(j n log n) ≤ n/j.

theorem ThreeMajority.exp_neg_nat_mul_log {n : ℕ} (hn : 0 < n) (k : ℕ) :
Real.exp (-(↑k * Real.log ↑n)) = 1 / ↑n ^ k

exp (−k log n) = 1/n^k.

theorem ThreeMajority.log_ge_of_two_le {n : ℕ} (hn : 2 ≤ n) :
0.6931471803 ≤ Real.log ↑n

log n ≥ log 2 for n ≥ 2.

theorem ThreeMajority.ite_exists_le_sum {α : Type u_1} (s : Finset α) (P : α → Prop) [DecidablePred P] [Decidable (∃ a ∈ s, P a)] :
(if ∃ a ∈ s, P a then 1 else 0) ≤ ∑ a ∈ s, if P a then 1 else 0

The union bound, pointwise.

theorem ThreeMajority.colourCount_eq_zero_of_notMem {n : ℕ} {σ : Type u_1} [DecidableEq σ] {c : Fin n → σ} {a : σ} (ha : a ∉ Finset.image c Finset.univ) :
theorem ThreeMajority.notMem_image_of_colourCount_eq_zero {n : ℕ} {σ : Type u_1} [DecidableEq σ] {c : Fin n → σ} {a : σ} (h : colourCount c a = 0) :
theorem ThreeMajority.colourCount_runCol_eq_zero {n : ℕ} {σ : Type u_1} [DecidableEq σ] {c : Fin n → σ} {a : σ} (h : colourCount c a = 0) (l : List (Tgt3 n)) :
colourCount (runCol c l) a = 0

A dead colour stays dead.

theorem ThreeMajority.sum_colourCount_of_image_subset {n : ℕ} {σ : Type u_1} [DecidableEq σ] {c : Fin n → σ} {J : Finset σ} (h : Finset.image c Finset.univ ⊆ J) :
∑ b ∈ J, ↑(colourCount c b) = ↑n

The supports of the colours of any superset of the remaining colours add up to n.

theorem ThreeMajority.sum_colourCount_univ {n : ℕ} {σ : Type u_1} [DecidableEq σ] [Fintype σ] (c : Fin n → σ) :
∑ b : σ, ↑(colourCount c b) = ↑n
theorem ThreeMajority.colourCount_le_of_forall_lt {n : ℕ} {σ : Type u_1} [DecidableEq σ] {c : Fin n → σ} {m : ℝ} (hm : 0 ≤ m) (hj1 : 1 ≤ numColours c) (h : ∀ b ∈ Finset.image c Finset.univ, ↑n / ↑(numColours c) - m < ↑(colourCount c b)) (b : σ) :
↑(colourCount c b) ≤ ↑n / ↑(numColours c) + (↑(numColours c) - 1) * m

If every colour of c (j colours) has more than n/j − m agents, every colour has at most n/j + (j − 1) m agents.

theorem ThreeMajority.sum_sq_div_le {n : ℕ} {σ : Type u_1} [DecidableEq σ] [Fintype σ] {c : Fin n → σ} {M : ℝ} (hn : 0 < ↑n) (hM : ∀ (b : σ), ↑(colourCount c b) ≤ M) :
∑ b : σ, (↑(colourCount c b) / ↑n) ^ 2 ≤ M / ↑n

∑_b (c_b/n)² ≤ M/n when every support is at most M.

theorem ThreeMajority.inf'_colourCount_le {n : ℕ} {σ : Type u_1} [DecidableEq σ] {c : Fin n → σ} {J : Finset σ} (hJ : J.Nonempty) (h : Finset.image c Finset.univ ⊆ J) :
(J.inf' hJ fun (a : σ) => ↑(colourCount c a)) ≤ ↑n / ↑J.card - 1 / (2 * ↑J.card) * ∑ a ∈ J, |↑(colourCount c a) - ↑n / ↑J.card|

The smallest of the supports of the colours of J ⊇ image c is at most n/|J| − (1/(2|J|)) ∑_{a ∈ J} |c_a − n/|J||.

theorem ThreeMajority.sum_avg_adoptInd {n : ℕ} {σ : Type u_1} [DecidableEq σ] [NeZero n] (c : Fin n → σ) (a : σ) :
∑ v : Fin n, avg (adoptInd c a v) = avg fun (r : Tgt3 n) => ↑(colourCount (stepCol c r) a)

The expected new support of a is the sum of the agents' adoption probabilities.

theorem ThreeMajority.le_avg_colourCount_stepCol {n : ℕ} {σ : Type u_1} [DecidableEq σ] [NeZero n] [Finite σ] (c : Fin n → σ) (a : σ) {M : ℝ} (hM : ∀ (b : σ), ↑(colourCount c b) ≤ M) :
↑(colourCount c a) * (1 + ↑(colourCount c a) / ↑n - M / ↑n) ≤ avg fun (r : Tgt3 n) => ↑(colourCount (stepCol c r) a)

Lower bound on the expected new support (Lemma 2.1 with c_b ≤ M for all b): 𝔼[C_a'] ≥ c_a (1 + c_a/n − M/n).

theorem ThreeMajority.avg_colourCount_stepCol_le_of_le {n : ℕ} {σ : Type u_1} [DecidableEq σ] [NeZero n] [Finite σ] (c : Fin n → σ) (a : σ) {j : ℕ} {b : ℝ} (hj : numColours c ≤ j) (hb : ↑(colourCount c a) ≤ b) :
(avg fun (r : Tgt3 n) => ↑(colourCount (stepCol c r) a)) ≤ b * (1 + b / ↑n - 1 / ↑j)

Upper bound of Lemma 2.1 at a level b ≥ c_a, with at most j colours: 𝔼[C_a'] ≤ b (1 + b/n − 1/j).

theorem ThreeMajority.le_avg_colourCount_stepCol_of_forall_lt {n : ℕ} {σ : Type u_1} [DecidableEq σ] [NeZero n] [Finite σ] {x : Fin n → σ} {m : ℝ} (hm : 0 ≤ m) (hj2 : 2 ≤ numColours x) (hjm : 8 * ↑(numColours x) * m ≤ ↑n) (hall : ∀ b ∈ Finset.image x Finset.univ, ↑n / ↑(numColours x) - m < ↑(colourCount x b)) {a : σ} (ha : a ∈ Finset.image x Finset.univ) :
↑n / ↑(numColours x) - 2 * m ≤ avg fun (r : Tgt3 n) => ↑(colourCount (stepCol x r) a)

Under the hypotheses of Equation (6) (every colour of x, with j ≥ 2 colours, has more than n/j − m agents, 8 j m ≤ n), every colour of x has expected new support at least n/j − 2m: the supports are at most M = n/j + (j − 1) m, so ∑_b (c_b/n)² ≤ M/n, and c ↦ c (1 + c/n − M/n) is increasing, with value at least n/j − 2m at c = n/j − m.

theorem ThreeMajority.avg_colourCount_stepCol_ge {n : ℕ} {σ : Type u_1} [DecidableEq σ] [NeZero n] (c : Fin n → σ) (a : σ) {μ k : ℝ} (hμ0 : 0 < μ) (hμk : μ < k) (hmean : (avg fun (r : Tgt3 n) => ↑(colourCount (stepCol c r) a)) ≤ μ) :
(avg fun (r : Tgt3 n) => if k ≤ ↑(colourCount (stepCol c r) a) then 1 else 0) ≤ Real.exp (-((k - μ) ^ 2 / (k + μ)))

Chernoff upper tail for the new support of a colour, at a threshold k: if the mean is at most μ with 0 < μ < k, then P(C_a' ≥ k) ≤ exp(−(k − μ)²/(k + μ)).

theorem ThreeMajority.avg_colourCount_stepCol_le_tail {n : ℕ} {σ : Type u_1} [DecidableEq σ] [NeZero n] (c : Fin n → σ) (a : σ) {μ k : ℝ} (hk0 : 0 < k) (hkμ : k < μ) (hmean : μ ≤ avg fun (r : Tgt3 n) => ↑(colourCount (stepCol c r) a)) :
(avg fun (r : Tgt3 n) => if ↑(colourCount (stepCol c r) a) ≤ k then 1 else 0) ≤ Real.exp (-((μ - k) ^ 2 / (2 * μ)))

Chernoff lower tail for the new support of a colour, at a threshold k: if the mean is at least μ with 0 < k < μ, then P(C_a' ≤ k) ≤ exp(−(μ − k)²/(2μ)).

theorem ThreeMajority.avg_abs_colourCount_stepCol_sub_ge {n : ℕ} {σ : Type u_1} [DecidableEq σ] [NeZero n] (c : Fin n → σ) (a : σ) (θ : ℝ) (hσ : 1 ≤ ∑ v : Fin n, Dynamics.variance (adoptInd c a v)) :
9 / 256 * √(∑ v : Fin n, Dynamics.variance (adoptInd c a v)) ≤ avg fun (r : Tgt3 n) => |↑(colourCount (stepCol c r) a) - θ|

Anti-concentration of the new support of a colour (replaces the Central Limit Theorem of BCNPT16, Equation (4)): if the agents' variances add up to σ² ≥ 1, the new support is at mean absolute distance at least (9/256) σ from any fixed value θ. If the mean is at distance at least σ/4 from θ, this is Jensen's inequality; otherwise, on the Paley–Zygmund event σ² ≤ 4 S² (probability at least 9/64) the centered sum S is at least σ/2 in absolute value.

theorem ThreeMajority.sum_variance_adoptInd_ge {n : ℕ} {σ : Type u_1} [DecidableEq σ] [NeZero n] [Finite σ] {x : Fin n → σ} {u : ℝ} (hu : 0 ≤ u) (hj2 : 2 ≤ numColours x) (hju : ↑(numColours x) * u ≤ 1 / 250) (hall : ∀ b ∈ Finset.image x Finset.univ, ↑n / ↑(numColours x) - ↑n * u < ↑(colourCount x b)) {a : σ} (ha : a ∈ Finset.image x Finset.univ) :
↑n / (4 * ↑(numColours x)) ≤ ∑ v : Fin n, Dynamics.variance (adoptInd x a v)

Variance near the uniform configuration (for BCNPT16, Equation (4)): if every colour of x (j ≥ 2 colours) has more than n/j − n u agents with j u ≤ 1/250, the agents' variances for the new support of each colour add up to at least n/(4j). The adoption probability p = X (1 + X − ‖x‖²) (X = c_a/n) lies between (1 − 1/250)²/j and (1/2 + 1/250)(1 + 1/250), and the variance is n p (1 − p).