Documentation

Epidemics.SmallWorldCollapse

The percolated SWG(n, q) as one percolation of the complete graph (EPI-6) #

Bond percolation with parameter p on SWG(n, q) ([BCDPTZ22] Definition 1.1) involves two independent families of coins: the bridge coins b ~ coins q and the percolation coins ω ~ coins p. A pair {u, v} is an edge of the percolation graph perc (swg n b) ω if and only if ω {u, v} is open and {u, v} is a cycle edge or a bridge. The resulting coins ω {u, v} ∧ (cycle edge ∨ b {u, v}) are again independent, open with probability p on the cycle edges and p q on the other pairs (swgRate), and the percolation graph is the percolation of the complete graph with these coins (perc_swg_eq). Hence every event about the percolation graph has the same probability under the two-stage law and under the collapsed law (expect_prob_swg_eq). This is the independence used in the exploration of [BCDPTZ22] Appendix C ("Ŷ is distributed as Bin(|S_t|, pc/n)").

noncomputable def Epidemics.swgRate (n : ℕ) (p q : ℝ) (e : Sym2 (Fin n)) :

The probability that a pair is an edge of the percolated SWG(n, q): p for a cycle edge, p q otherwise.

Equations
Instances For
    theorem Epidemics.swgRate_nonneg {n : ℕ} {p q : ℝ} (hp0 : 0 ≤ p) (hq0 : 0 ≤ q) (e : Sym2 (Fin n)) :
    0 ≤ swgRate n p q e
    theorem Epidemics.swgRate_le_one {n : ℕ} {p q : ℝ} (hp0 : 0 ≤ p) (hp1 : p ≤ 1) (hq1 : q ≤ 1) (e : Sym2 (Fin n)) :
    swgRate n p q e ≤ 1
    noncomputable def Epidemics.swgCoin (n : ℕ) (e : Sym2 (Fin n)) (bq bp : Bool) :

    The collapsed coin of a pair: open percolation coin, and the pair is a cycle edge or an open bridge.

    Equations
    Instances For
      theorem Epidemics.perc_swg_eq {n : ℕ} (b ω : Sym2 (Fin n) → Bool) :
      perc (swg n b) ω = perc ⊤ fun (e : Sym2 (Fin n)) => swgCoin n e (b e) (ω e)

      The percolation graph of swg n b is the percolation of the complete graph by the collapsed coins.

      theorem Epidemics.expect_prob_swg_eq {n : ℕ} {p q : ℝ} (hp0 : 0 ≤ p) (hp1 : p ≤ 1) (hq0 : 0 ≤ q) (hq1 : q ≤ 1) (E : SimpleGraph (Fin n) → Prop) :
      ((coins q hq0 hq1).expect fun (b : Sym2 (Fin n) → Bool) => (coins p hp0 hp1).prob fun (ω : Sym2 (Fin n) → Bool) => E (perc (swg n b) ω)) = (Dynamics.Distribution.independent fun (e : Sym2 (Fin n)) => Dynamics.Distribution.bernoulli (swgRate n p q e) ⋯ ⋯).prob fun (ω : Sym2 (Fin n) → Bool) => E (perc ⊤ ω)

      The collapsed law: for every event E on graphs, its probability for the percolation graph of SWG(n, q) (over the bridges and the percolation) equals its probability for the percolation of the complete graph with independent coins of probability swgRate n p q.