Documentation

Averaging.OpportunisticSignEvents

The initial community averages (Lemma A.1 and the sign events) #

With uniform initial signs σ, let S₁ = ∑_{v ∈ V₁} σ_v and S₂ = ∑_{v ∉ V₁} σ_v, two independent sums of n/2 signs. The initial average of community h is μ_h = 2 S_h/n = x_∥ + y⁽⁰⁾ on that community (projOne_add_projCut_signVec), and ‖y⁽⁰⁾‖² = (S₁ - S₂)²/n.

noncomputable def Averaging.Opportunistic.blockSum {V : Type u_1} (U : Finset V) (σ : V → ℤˣ) :

The sum of the initial signs on a set of nodes.

Equations
Instances For
    theorem Averaging.Opportunistic.sum_subtype_eq {V : Type u_1} (U : Finset V) [Fintype ↥U] (σ : V → ℤˣ) :
    ∑ i : ↥U, signVec (fun (i : ↥U) => σ ↑i) i = blockSum U σ
    theorem Averaging.Opportunistic.sum_subtype_compl_eq {V : Type u_1} [Fintype V] [DecidableEq V] (U : Finset V) [Fintype { v : V // v ∉ U }] (σ : V → ℤˣ) :
    ∑ i : { v : V // v ∉ U }, signVec (fun (i : { v : V // v ∉ U }) => σ ↑i) i = blockSum Uᶜ σ
    theorem Averaging.Opportunistic.avg_split_block {V : Type u_1} [Fintype V] [DecidableEq V] (U : Finset V) (F : ℝ → ℝ → ℝ) :
    (Dynamics.avg fun (σ : V → ℤˣ) => F (blockSum U σ) (blockSum Uᶜ σ)) = Dynamics.avg fun (τ₁ : ↥U → ℤˣ) => Dynamics.avg fun (τ₂ : { v : V // v ∉ U } → ℤˣ) => F (∑ i : ↥U, signVec τ₁ i) (∑ j : { v : V // v ∉ U }, signVec τ₂ j)

    Independence of the two blocks of signs, through their sums.

    theorem Averaging.Opportunistic.IsClusteredRegular.card_subtype {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) :
    ↑(Fintype.card ↥V₁) = ↑(Fintype.card V) / 2
    theorem Averaging.Opportunistic.IsClusteredRegular.card_subtype_compl {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) :
    ↑(Fintype.card { v : V // v ∉ V₁ }) = ↑(Fintype.card V) / 2
    theorem Averaging.Opportunistic.IsClusteredRegular.sum_signVec_split {V : Type u_1} [Fintype V] [DecidableEq V] (V₁ : Finset V) (σ : V → ℤˣ) :
    ∑ v : V, signVec σ v = blockSum V₁ σ + blockSum V₁ᶜ σ
    theorem Averaging.Opportunistic.IsClusteredRegular.sum_cutVec_mul_split {V : Type u_1} [Fintype V] [DecidableEq V] {V₁ : Finset V} (σ : V → ℤˣ) :
    ∑ v : V, cutVec V₁ v * signVec σ v = blockSum V₁ σ - blockSum V₁ᶜ σ
    theorem Averaging.Opportunistic.IsClusteredRegular.projOne_add_projCut_signVec {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) (σ : V → ℤˣ) (v : V) :
    projOne (signVec σ) v + projCut V₁ (signVec σ) v = if v ∈ V₁ then 2 * blockSum V₁ σ / ↑(Fintype.card V) else 2 * blockSum V₁ᶜ σ / ↑(Fintype.card V)

    x_∥ + y⁽⁰⁾ = 2 S_h/n on community h.

    theorem Averaging.Opportunistic.IsClusteredRegular.sum_sq_projCut_signVec {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) (σ : V → ℤˣ) :
    ∑ w : V, projCut V₁ (signVec σ) w ^ 2 = (blockSum V₁ σ - blockSum V₁ᶜ σ) ^ 2 / ↑(Fintype.card V)

    ‖y⁽⁰⁾‖² = (S₁ - S₂)²/n.

    theorem Averaging.Opportunistic.IsClusteredRegular.avg_abs_blockSum_le_mul {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) {ε : ℝ} (hε : 0 ≤ ε) :
    (Dynamics.avg fun (σ : V → ℤˣ) => if |blockSum V₁ σ| ≤ ε * |blockSum V₁ᶜ σ| then 1 else 0) ≤ ε + 1 / √(↑(Fintype.card V) / 2 + 1)

    Lemma A.1, small initial average: P(|S₁| ≤ ε |S₂|) ≤ ε + 1/√(n/2 + 1).

    theorem Averaging.Opportunistic.IsClusteredRegular.avg_abs_blockSum_compl_le_mul {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) {ε : ℝ} (hε : 0 ≤ ε) :
    (Dynamics.avg fun (σ : V → ℤˣ) => if |blockSum V₁ᶜ σ| ≤ ε * |blockSum V₁ σ| then 1 else 0) ≤ ε + 1 / √(↑(Fintype.card V) / 2 + 1)

    The same with the communities exchanged: P(|S₂| ≤ ε |S₁|) ≤ ε + 1/√(n/2 + 1).

    theorem Averaging.Opportunistic.IsClusteredRegular.avg_blockSum_mul_neg {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {V₁ : Finset V} {d b : ℕ} (hG : IsClusteredRegular G V₁ d b) :
    1 / 2 - 1 / √(↑(Fintype.card V) / 2 + 1) ≤ Dynamics.avg fun (σ : V → ℤˣ) => if blockSum V₁ σ * blockSum V₁ᶜ σ < 0 then 1 else 0

    Opposite community averages: P(S₁ S₂ < 0) ≥ 1/2 - 1/√(n/2 + 1).