Documentation

ThreeMajority.AnyStartVoter

Voter reduces the number of colours fast (BCEKMN17, Lemma 3) #

The Voter process is dual to coalescing random walks (Lemma 4). On the complete graph with self-loops, one step of the coalescing walks moves the set Z of occupied nodes to its image walkStep Z y = y '' Z under one uniform round y : Fin n → Fin n, and two walks coalesce when they move to the same node. This duality is restated here rather than imported, since this package does not depend on the voter package.

def ThreeMajority.walkStep {n : ℕ} (Z : Finset (Fin n)) (y : Fin n → Fin n) :

One step of coalescing random walks on the complete graph with self-loops: the walks at the nodes of Z move along the round y, and walks on the same node coalesce.

Equations
Instances For
    theorem ThreeMajority.image_voterRun_subset {n : ℕ} {σ : Type u_1} [DecidableEq σ] (c : Fin n → σ) (l : List (Fin n → Fin n)) :
    Finset.image (voterRun c l) Finset.univ ⊆ Finset.image c (List.foldr (fun (y : Fin n → Fin n) (Z : Finset (Fin n)) => walkStep Z y) Finset.univ l)

    The colours of Voter after the rounds l are colours of the nodes still occupied by the walks started on all nodes and moved by the rounds in reverse order.

    theorem ThreeMajority.numColours_voterRun_le {n : ℕ} {σ : Type u_1} [DecidableEq σ] (c : Fin n → σ) (l : List (Fin n → Fin n)) :
    numColours (voterRun c l) ≤ (List.foldr (fun (y : Fin n → Fin n) (Z : Finset (Fin n)) => walkStep Z y) Finset.univ l).card

    Lemma 4 (BCEKMN17), the inequality T^k_V ≤ T^k_C, pathwise: the number of colours of Voter after the rounds l is at most the number of coalescing walks, started on all nodes, after the same rounds applied in reverse order (List.foldr applies the last round first).

    theorem ThreeMajority.voter_dual {n : ℕ} [NeZero n] {σ : Type u_1} [DecidableEq σ] (c : Fin n → σ) (k T : ℕ) :
    (expList (Fin n → Fin n) T fun (l : List (Fin n → Fin n)) => if k < numColours (voterRun c l) then 1 else 0) ≤ (Dynamics.Kernel.ofStep walkStep).event (fun (Z : Finset (Fin n)) => k < Z.card) T Finset.univ

    Equation (6) (BCEKMN17), as the inequality used: after T rounds, Voter has more than k colours with at most the probability that more than k of the n coalescing walks remain.

    theorem ThreeMajority.bonferroni_le_one_sub_pow {q : ℝ} (hq1 : q ≤ 1) (x : ℕ) :
    1 - ↑x * q + ↑x * (↑x - 1) / 2 * q ^ 2 - ↑x * (↑x - 1) * (↑x - 2) / 6 * q ^ 3 ≤ (1 - q) ^ x

    The degree-three Bonferroni inequality (1 - q)^x ≥ 1 - xq + C(x,2) q² - C(x,3) q³.

    theorem ThreeMajority.card_walkStep_eq_sum {n : ℕ} (Z : Finset (Fin n)) (y : Fin n → Fin n) :
    ↑(walkStep Z y).card = ∑ u : Fin n, (1 - ∏ z ∈ Z, if y z ≠ u then 1 else 0)

    The number of walks after a step, as a sum over nodes of occupation indicators.

    theorem ThreeMajority.avg_prod_ne {n : ℕ} [NeZero n] (Z : Finset (Fin n)) (u : Fin n) :
    (avg fun (y : Fin n → Fin n) => ∏ z ∈ Z, if y z ≠ u then 1 else 0) = (1 - 1 / ↑n) ^ Z.card

    A fixed node is missed by x independent uniform walkers with probability (1 - 1/n)^x.

    theorem ThreeMajority.avg_card_walkStep {n : ℕ} [NeZero n] (Z : Finset (Fin n)) :
    (avg fun (y : Fin n → Fin n) => ↑(walkStep Z y).card) = ↑n * (1 - (1 - 1 / ↑n) ^ Z.card)

    The expected number of occupied nodes after one step from x walks is n (1 - (1 - 1/n)^x).

    theorem ThreeMajority.walk_drift {n : ℕ} (Z : Finset (Fin n)) :
    (avg fun (y : Fin n → Fin n) => ↑(walkStep Z y).card) ≤ ↑Z.card - ↑Z.card * (↑Z.card - 1) / (3 * ↑n)

    The expected number of coalescing walks after one step, from x = |Z| walks, is at most x − x(x−1)/(3n) (exactly n(1 − (1 − 1/n)^x), the expected number of occupied nodes). This is the drift of Equation (7) of BCEKMN17, in a form valid for every x.

    theorem ThreeMajority.walk_drift_paper {n : ℕ} (Z : Finset (Fin n)) (hZ : 2 ≤ Z.card) :
    (avg fun (y : Fin n → Fin n) => ↑(walkStep Z y).card) ≤ ↑Z.card - ↑Z.card ^ 2 / (10 * ↑n)

    Equation (7) (BCEKMN17): E[X_{t+1} | X_t = x] ≤ x − x²/(10n) for x ≥ 2.

    theorem ThreeMajority.walk_drift_le_tangent {N : ℝ} (hN : 0 ≤ N) (m x : ℝ) :
    x - x * (x - 1) / (3 * N) ≤ m - m * (m - 1) / (3 * N) + (1 - (2 * m - 1) / (3 * N)) * (x - m)

    The concave drift bound x − x(x−1)/(3N) lies below its tangent line at m.

    theorem ThreeMajority.walk_drift_mono {N x y : ℝ} (hN : 1 ≤ N) (hxy : x ≤ y) (hy : y ≤ N + 1) :
    x - x * (x - 1) / (3 * N) ≤ y - y * (y - 1) / (3 * N)

    The drift bound x − x(x−1)/(3N) is nondecreasing on [0, N + 1].

    theorem ThreeMajority.walk_iterate_succ_le {n : ℕ} [NeZero n] (Z : Finset (Fin n)) (t : ℕ) {m : ℝ} (hm : (Dynamics.Kernel.ofStep walkStep).iterate t (fun (W : Finset (Fin n)) => ↑W.card) Z = m) :
    (Dynamics.Kernel.ofStep walkStep).iterate (t + 1) (fun (W : Finset (Fin n)) => ↑W.card) Z ≤ m - m * (m - 1) / (3 * ↑n)

    One more step of the walks: E[X_{t+1}] ≤ m − m(m−1)/(3n) for m = E[X_t], by walk_drift and the concavity of the bound.

    theorem ThreeMajority.walk_expect_le {n : ℕ} [NeZero n] (Z : Finset (Fin n)) {t : ℕ} (ht : 1 ≤ t) :
    (Dynamics.Kernel.ofStep walkStep).iterate t (fun (W : Finset (Fin n)) => ↑W.card) Z ≤ 1 + 3 * ↑n / ↑t

    The expected number of coalescing walks after t ≥ 1 steps, from any initial set, is at most 1 + 3n/t. This replaces the bound E[T^k_C] ≤ 20 n/k of BCEKMN17 (Equations (18), (19), from the variable drift theorem, Theorem 7) in the proof of Lemma 3.

    theorem ThreeMajority.walk_iterate_mono_of_closed {n : ℕ} [NeZero n] {P : Finset (Fin n) → Prop} (hP : ∀ (W : Finset (Fin n)) (y : Fin n → Fin n), P W → P (walkStep W y)) {f g : Finset (Fin n) → ℝ} (hfg : ∀ (W : Finset (Fin n)), P W → f W ≤ g W) (t : ℕ) {W : Finset (Fin n)} (hW : P W) :

    Expectations along the walks compare on a set of configurations that the walks cannot leave.

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

    Lemma 3 (BCEKMN17): from any configuration, Voter has at most k colours after any T ≥ 24 (n/k) log n rounds, with probability at least 1 − 1/n.