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.
avg_abs_blockSum_le_mul:P(|S₁| ≤ ε |S₂|) ≤ ε + 1/√(n/2 + 1)(independence and the central binomial bound); likewise with the roles of the communities exchanged.avg_blockSum_mul_neg:P(S₁ S₂ < 0) ≥ 1/2 - 1/√(n/2 + 1).
The sum of the initial signs on a set of nodes.
Equations
- Averaging.Opportunistic.blockSum U σ = ∑ v ∈ U, Averaging.Opportunistic.signVec σ v
Instances For
theorem
Averaging.Opportunistic.avg_split_block
{V : Type u_1}
[Fintype V]
[DecidableEq V]
(U : Finset V)
(F : ℝ → ℝ → ℝ)
:
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)
:
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)
:
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)
:
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 → ℤˣ)
:
‖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 ≤ ε)
:
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 ≤ ε)
:
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)
:
Opposite community averages: P(S₁ S₂ < 0) ≥ 1/2 - 1/√(n/2 + 1).