Documentation

Epidemics.SmallWorldSubcritical

Subcritical SWG(n, c/n): all clusters are small (EPI-6) #

[BCDPTZ22] Lemma C.1 (claim 2 of Theorem 2.1): below the threshold p* = swgThreshold c, every connected component of the percolated SWG(n, c/n) has O(log n) nodes, w.h.p.

By expect_prob_swg_eq the percolated SWG(n, q) is the percolation of the complete graph with independent coins, of probability p on the cycle edges and p q = p c / n on the other pairs. Its clusters are explored breadth-first (Explore), giving every discovered node the weight 1 if it was discovered through a cycle edge and 1 + p₀ otherwise (swgWeight), where p₀ = p* - ε. A node discovered through a cycle edge has at most one undiscovered cycle neighbour, any other node at most two, and every node has at most n other undiscovered neighbours, each reached by a bridge with probability p c / n. With δ = 1 - p₀ - c p₀ (1 + p₀) > 0 (the subcritical condition, lt_swgThreshold_iff), the expected weight discovered from a node of weight w is therefore at most (1 - δ / 2) w (swg_step): this is the two-type Galton–Watson comparison behind the paper's variable W = Y + ∑_{j ≤ 2Y} L_j, with the weights a left eigenvector of the mean matrix. The supermartingale tail bound Explore.prob_cluster_gt_le and a union bound over the n nodes conclude, with β = 64 / δ² and failure probability 2 / n.

The union bound #

theorem Epidemics.prob_components_le_of_tail' {V : Type u_1} {Ω : Type u_2} [Fintype V] [Fintype Ω] (P : Dynamics.Distribution Ω) (H : Ω → SimpleGraph V) {L β : ℝ} (hL : 0 ≤ L) (htail : ∀ (s : V), (P.prob fun (ω : Ω) => ⌊L⌋₊ < ((H ω).connectedComponentMk s).supp.ncard) ≤ β) :
1 - ↑(Fintype.card V) * β ≤ P.prob fun (ω : Ω) => ∀ (K : (H ω).ConnectedComponent), ↑K.supp.ncard ≤ L

Union bound over the components, for any random graph: if the cluster of every vertex has more than ⌊L⌋₊ vertices with probability at most β, then all components have at most L vertices with probability at least 1 - n β.

The weights and the one-step bound #

noncomputable def Epidemics.swgWeight (n : ℕ) (p₀ : ℝ) (e : Sym2 (Fin n)) :

The weight of a node discovered through the pair e: 1 through a cycle edge, 1 + p₀ through a bridge.

Equations
Instances For
    theorem Epidemics.swgWeight_bounds {n : ℕ} {p₀ : ℝ} (h0 : 0 ≤ p₀) (h1 : p₀ ≤ 1) (e : Sym2 (Fin n)) :
    1 ≤ swgWeight n p₀ e ∧ swgWeight n p₀ e ≤ 2
    theorem Epidemics.swg_step {n : ℕ} {p p₀ q c lam : ℝ} (hp0 : 0 ≤ p) (hpp : p ≤ p₀) (hq0 : 0 ≤ q) (hqn : q * ↑n = c) (hC : p₀ + c * p₀ * (1 + p₀) ≤ lam) (hB : 2 * p₀ + c * p₀ * (1 + p₀) ≤ lam * (1 + p₀)) (s : Fin n) (σ : Explore.State (Fin n)) (hσ : Explore.Inv s (1 + p₀) σ) (hp : σ.proc < σ.order.length) :
    ∑ y ∈ Explore.fresh ⊤ σ σ.order[σ.proc], swgRate n p q s(σ.order[σ.proc], y) * swgWeight n p₀ s(σ.order[σ.proc], y) ≤ lam * σ.wt σ.order[σ.proc]

    One step of the exploration of the percolated SWG(n, q): if p ≤ p₀, q n = c and λ dominates the two rows of the mean matrix (p₀ + c p₀ (1 + p₀) ≤ λ for a node discovered through a cycle edge, 2 p₀ + c p₀ (1 + p₀) ≤ λ (1 + p₀) for the root and a node discovered through a bridge), then the expected weight discovered from the current node is at most λ times its weight.

    The union-bound arithmetic #

    theorem Epidemics.swg_tail_arith {n : ℕ} {δ : ℝ} (hδ0 : 0 < δ) (hδ1 : δ ≤ 1) (hn : 2 ≤ n) :
    ↑n * Real.exp (-(δ / 8 * ((1 - (1 + δ / 4) * (1 - δ / 2)) * ↑⌊64 / δ ^ 2 * Real.log ↑n⌋₊ * 1 - 2))) ≤ 2 / ↑n

    For n ≥ 2 and 0 < δ ≤ 1, the tail of Explore.prob_cluster_gt_le at θ = δ / 8, κ = 1 + δ / 4, λ = 1 - δ / 2, wmin = 1, wmax = 2 and t = ⌊(64 / δ²) log n⌋₊ is at most 2 / n².

    Lemma C.1 #

    theorem Epidemics.swg_components_small {n : ℕ} {c p₀ : ℝ} (hp₀0 : 0 ≤ p₀) (hp₀1 : p₀ ≤ 1) (hδ : 0 < 1 - p₀ - c * p₀ * (1 + p₀)) (hc : 0 ≤ c) (hn : 2 ≤ n) {q : ℝ} (hq0 : 0 ≤ q) (hq1 : q ≤ 1) (hqn : q * ↑n = c) {p : ℝ} (hp0 : 0 ≤ p) (hp1 : p ≤ 1) (hpp : p ≤ p₀) :
    1 - 2 / ↑n ≤ (coins q hq0 hq1).expect fun (b : Sym2 (Fin n) → Bool) => (coins p hp0 hp1).prob fun (ω : Sym2 (Fin n) → Bool) => ∀ (K : (perc (swg n b) ω).ConnectedComponent), ↑K.supp.ncard ≤ 64 / (1 - p₀ - c * p₀ * (1 + p₀)) ^ 2 * Real.log ↑n

    Lemma C.1 of [BCDPTZ22] with explicit constants: let c > 0, 0 < p₀ < 1 with δ = 1 - p₀ - c p₀ (1 + p₀) > 0 (that is, p₀ < p*), and n ≥ 2. For q n = c and every p ≤ p₀, with probability at least 1 - 2 / n over the graph swg n b (b ~ coins q) and the percolation ω ~ coins p, every connected component of perc (swg n b) ω has at most (64 / δ²) log n nodes.