Non-ephemeral good nodes (Lemma 4.2): the probabilistic part #
avg_le_of_mul_le(anti-concentration of‖y⁽⁰⁾‖²): a quantityg ≤ 1of the initial signs withg ‖y⁽⁰⁾‖² ≤ a ‖y⁽⁰⁾‖² + K²has average at mosta + 1/√(n+1) + 2 K (1 + log n). Since‖y⁽⁰⁾‖² = S²/nwithS = ⟨σ, χ⟩a sum ofnindependent signs, this follows fromP(S = 0) ≤ 1/√(n+1)andE[1/|S|; S ≠ 0] ≤ 2 (1 + log n)/√(n+1).- Probabilities of a uniformly random dart: crossing the cut (
b/d), with tail (or head) in a setB(|B|/n, the graph being regular).
The sum ⟨σ, χ⟩ has the law of a sum of independent uniform signs.
Anti-concentration of ‖y⁽⁰⁾‖².
A uniformly random dart crosses the cut with probability b/d.
The tail of a uniformly random dart lies in B with probability |B|/n.
Arithmetic of the bound Yb #
Expectation bounds for one choice of the initial signs #
The cut coefficient moves little up to the start of the phase:
E ‖y⁽ᵗ¹⁾ - y⁽⁰⁾‖² ≤ 2 L₁ ‖y⁽⁰⁾‖² + 5 λ₂/λ₃ with L₁ = λ₂ t₁/n.
The rest component is small at the start of the phase:
E ‖z⁽ᵗ¹⁾‖² ≤ n (1 - λ₃/n)^{t₁} + 3 r ‖y⁽⁰⁾‖² + 10 r² with r = λ₂/λ₃.
From an arbitrary state x₁ (the start of the phase): the deviation r after k more
rounds satisfies E ‖r⁽ᵏ⁾‖² ≤ (2.5 L_k + 2 r) ‖y₁‖² + 2 ‖z₁‖², with L_k = λ₂ k/n.
The good event #
At the reference state itself the deviation is the rest component.
Many bad nodes at the start force a large rest component: |B| > ε n gives
‖z₁‖² > ε n θ.
The threshold θ = ε² ‖y⁽⁰⁾‖²/(4n) for the deviation.
Equations
- Averaging.Opportunistic.thr V₁ ε x₀ = ε ^ 2 * (↑(Fintype.card V) * Averaging.Opportunistic.cutCoef V₁ x₀ ^ 2) / (4 * ↑(Fintype.card V))
Instances For
The cut coefficient has moved by the start of the phase: 4 n (β₁ - β₀)² > ε² ‖y⁽⁰⁾‖².
Equations
- One or more equations did not get rendered due to their size.
Instances For
Deterministic core of Lemma 4.2: if the cut coefficient has not moved much by the start
of the phase (4 n (β₁ - β₀)² ≤ ε² ‖y⁽⁰⁾‖²), at most ε n nodes are bad at the start and at most
ε n rounds of the phase are bad, then at least (1 - 3ε) n nodes are ε-good at every round of
the phase.
One bad round: P(bad) ≤ b/d + 2 |B|/n.
The good event, for fixed initial signs (proof of Lemma 4.2): the probability that at
least (1 - 3ε) n nodes are ε-good throughout the phase [t₁, t₁ + M] is at least
1 - P(cut moved) - P(|B| > ε n) - (1/(ε n)) ∑_{k < M} (b/d + 2 E[1 - 1_moved; |B_k|/n]).
Bounds for one choice of the initial signs, in the form used by anti-concentration #
The cut coefficient moves by the start of the phase with probability g₁ satisfying
g₁ ‖y⁽⁰⁾‖² ≤ (8 L₁/ε²) ‖y⁽⁰⁾‖² + 20 r/ε².
Many bad nodes at the start: probability g₂ with
g₂ ‖y⁽⁰⁾‖² ≤ (12 r/ε³) ‖y⁽⁰⁾‖² + (4/ε³)(n (1 - λ₃/n)^{t₁} + 10 r²).
Bad rounds in the phase: g₃ ‖y⁽⁰⁾‖² ≤ (4/ε²)(6.25 L_k + 11 r) ‖y⁽⁰⁾‖² + (8/ε²)(n (1 - λ₃/n)^{t₁} + 10 r²), where g₃ is the expected fraction of bad nodes after
t₁ + k rounds, on the event that the cut coefficient has not moved.
Lemma 4.2 #
The final arithmetic of Lemma 4.2 #
The final arithmetic of Lemma 4.2 (c = 10⁶).
Averaging over the initial signs #
Lemma 4.2 with the constant c = 10⁶, for a phase [t₁, t₁ + M] with
6 (n/λ₃) log n ≤ t₁ ≤ 6 (n/λ₃) log n + 1 and t₁ + M ≤ 12 (n/λ₃) log n: with probability at
least 1 - ε, at least (1 - 3ε) n nodes are ε-good at every round of the phase.