Documentation

Epidemics.CobraCoverBranching

COBRA with branching factor 1 + ρ (EPI-4, Corollary 1 and Theorem 3) #

Cooper, Radzik, Rivera, PODC 2016 (arXiv:1602.05768), Corollary 1 (Section 3) and Theorem 3 (Section 1).

In COBRA with expected branching factor 1 + ρ, each informed vertex pushes to one uniformly random neighbour and, with probability ρ, to a second one (chosen with replacement); in the dual BIPS each vertex other than the source contacts one random neighbour and, with probability ρ, a second one. Here ρ = p/q is rational: a round (CoinChoices G q) gives every vertex two neighbour samples and a uniform coin in Fin q, and the vertex uses its second sample iff its coin is < p (coinTargets). Both processes read the same rounds.

@[reducible, inline]
abbrev Epidemics.CoinChoices {V : Type u_1} (G : SimpleGraph V) (q : ℕ) :
Type u_1

One round of the branching-factor-1 + p/q processes: two neighbour samples per vertex (Choices G 2) and one coin per vertex, uniform in Fin q. Under the uniform distribution all samples and coins are independent.

Equations
Instances For
    def Epidemics.coinTargets {V : Type u_1} [DecidableEq V] {G : SimpleGraph V} {q : ℕ} (p : ℕ) (ρ : CoinChoices G q) (x : V) :

    The neighbours used by the vertex x in the round ρ: its first sample, and also its second sample when its coin is < p (probability p/q). COBRA pushes to these vertices, and BIPS contacts them.

    Equations
    Instances For
      def Epidemics.cobraCoinStep {V : Type u_1} [DecidableEq V] {G : SimpleGraph V} {q : ℕ} (p : ℕ) (D : Finset V) (ρ : CoinChoices G q) :

      One round of COBRA with branching factor 1 + p/q: every vertex of D pushes to its coinTargets.

      Equations
      Instances For
        def Epidemics.cobraCoinRun {V : Type u_1} [DecidableEq V] {G : SimpleGraph V} {q : ℕ} (p : ℕ) (C : Finset V) (l : List (CoinChoices G q)) :

        COBRA with branching factor 1 + p/q after the rounds l (first round first), from C.

        Equations
        Instances For
          def Epidemics.bipsCoinStep {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} {q : ℕ} (p : ℕ) (v : V) (A : Finset V) (ρ : CoinChoices G q) :

          One round of BIPS with branching factor 1 + p/q and persistent source v: a vertex is infected next iff it is v or one of its coinTargets is in the current infected set A.

          Equations
          Instances For
            def Epidemics.bipsCoinRun {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} {q : ℕ} (p : ℕ) (v : V) (A₀ : Finset V) (l : List (CoinChoices G q)) :

            BIPS with branching factor 1 + p/q and source v after the rounds l, from A₀.

            Equations
            Instances For
              theorem Epidemics.cobraCoin_bips_duality {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} {q : ℕ} [DecidableRel G.Adj] (p : ℕ) (v : V) (C : Finset V) (t : ℕ) :
              (Dynamics.expList (CoinChoices G q) t fun (l : List (CoinChoices G q)) => if ∀ s ≤ t, v ∉ cobraCoinRun p C (List.take s l) then 1 else 0) = Dynamics.expList (CoinChoices G q) t fun (l : List (CoinChoices G q)) => if C ∩ bipsCoinRun p v {v} l = ∅ then 1 else 0

              Theorem 4 for branching factor 1 + p/q: P(Hit_C(v) > t ∣ C₀ = C) = P(C ∩ A_t = ∅ ∣ A₀ = {v}) for COBRA and BIPS with branching factor 1 + p/q. Same proof as cobra_bips_duality: pathwise, COBRA from C along r₁, …, r_t visits v iff BIPS from {v} along r_t, …, r₁ infects a vertex of C.

              theorem Epidemics.bipsCoin_expected_growth {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} {p q : ℕ} [DecidableRel G.Adj] {r : ℕ} (hreg : G.IsRegularOfDegree r) (hr : 0 < r) (hq : 0 < q) (hpq : p ≤ q) (v : V) (A : Finset V) :
              ↑A.card * (1 + ↑p / ↑q * (1 - Dynamics.lambdaG G r ^ 2) * (1 - ↑A.card / ↑(Fintype.card V))) ≤ Dynamics.avg fun (ρ : CoinChoices G q) => ↑(bipsCoinStep p v A ρ).card

              Corollary 1 (Section 3). On an r-regular graph (r > 0), for 0 ≤ ρ = p/q ≤ 1, one round of BIPS with branching factor 1 + ρ from the infected set A gives E(|A_{t+1}| ∣ A_t = A) ≥ |A| (1 + ρ (1 - λ²)(1 - |A|/n)).

              theorem Epidemics.bipsCoin_growthProcess {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} {p q : ℕ} [DecidableRel G.Adj] {r : ℕ} (hreg : G.IsRegularOfDegree r) (hr : 0 < r) (hq : 0 < q) (hpq : p ≤ q) (w : V) {c : ℝ} (hc : c ≤ ↑p / ↑q * (1 - Dynamics.lambdaG G r ^ 2)) :

              BIPS with branching factor 1 + p/q and source w is a growth process (GrowthProcess) with every rate c ≤ (p/q)(1 - λ²): source, moment generating function (tgtBips_mgf_le), Corollary 1, monotonicity, V absorbing.

              theorem Epidemics.coinTargets_nonempty {V : Type u_1} [DecidableEq V] {G : SimpleGraph V} {p q : ℕ} (ρ : CoinChoices G q) (u : V) :
              theorem Epidemics.pos_of_rho {p q : ℕ} {ρ₀ : ℝ} (hρ₀ : 0 < ρ₀) (h : ρ₀ ≤ ↑p / ↑q) :
              0 < q

              ρ₀ ≤ p/q with ρ₀ > 0 forces q > 0.

              theorem Epidemics.bipsCoin_infection_time (lam₀ ρ₀ : ℝ) (hlam₀ : lam₀ < 1) (hρ₀ : 0 < ρ₀) :
              ∃ (C : ℝ) (N : ℕ), ∀ {V : Type u_2} [inst : Fintype V] [inst_1 : DecidableEq V] (G : SimpleGraph V) [inst_2 : DecidableRel G.Adj] (r p q : ℕ), G.IsRegularOfDegree r → 0 < r → p ≤ q → ρ₀ ≤ ↑p / ↑q → Dynamics.lambdaG G r ≤ lam₀ → N ≤ Fintype.card V → ∀ (v : V) (T : ℕ), C * Real.log ↑(Fintype.card V) ≤ ↑T → (Dynamics.expList (CoinChoices G q) T fun (l : List (CoinChoices G q)) => if bipsCoinRun p v {v} l = Finset.univ then 0 else 1) ≤ C / ↑(Fintype.card V) ^ 3

              Theorem 2 for branching factor 1 + ρ (the BIPS half of Theorem 3, "the proof of Theorem 3 follows from the proof of Theorem 1, by using Corollary 1"). For constants λ₀ < 1 and ρ₀ > 0 there are C and N such that on every r-regular graph (r > 0) with n ≥ N vertices and λ ≤ λ₀, for ρ = p/q ∈ [ρ₀, 1], every source v and every T ≥ C log n, BIPS with branching factor 1 + ρ from {v} has not infected all vertices at time T with probability at most C / n³.

              theorem Epidemics.cobra_cover_time_branching (lam₀ ρ₀ : ℝ) (hlam₀ : lam₀ < 1) (hρ₀ : 0 < ρ₀) :
              ∃ (C : ℝ) (N : ℕ), ∀ {V : Type u_2} [inst : Fintype V] [inst_1 : DecidableEq V] (G : SimpleGraph V) [inst_2 : DecidableRel G.Adj] (r p q : ℕ), G.IsRegularOfDegree r → 0 < r → p ≤ q → ρ₀ ≤ ↑p / ↑q → Dynamics.lambdaG G r ≤ lam₀ → N ≤ Fintype.card V → ∀ (u : V) (T : ℕ), C * Real.log ↑(Fintype.card V) ≤ ↑T → (Dynamics.expList (CoinChoices G q) T fun (l : List (CoinChoices G q)) => if ((Finset.Icc 1 T).biUnion fun (s : ℕ) => cobraCoinRun p {u} (List.take s l)) = Finset.univ then 0 else 1) ≤ C / ↑(Fintype.card V) ^ 2

              Theorem 3 (Section 1), probability bound. For constants λ₀ < 1 and ρ₀ > 0 there are C and N such that on every r-regular graph (r > 0) with n ≥ N vertices and λ ≤ λ₀, for ρ = p/q ∈ [ρ₀, 1], every start vertex u and every T ≥ C log n, COBRA with branching factor 1 + ρ from {u} fails to visit every vertex at the times 1, …, T with probability at most C / n². (The paper assumes G connected; λ < 1 forces it.)

              theorem Epidemics.cobra_cover_time_branching_expectation (lam₀ ρ₀ : ℝ) (hlam₀ : lam₀ < 1) (hρ₀ : 0 < ρ₀) :
              ∃ (C : ℝ) (N : ℕ), ∀ {V : Type u_2} [inst : Fintype V] [inst_1 : DecidableEq V] (G : SimpleGraph V) [inst_2 : DecidableRel G.Adj] (r p q : ℕ), G.IsRegularOfDegree r → 0 < r → p ≤ q → ρ₀ ≤ ↑p / ↑q → Dynamics.lambdaG G r ≤ lam₀ → N ≤ Fintype.card V → ∀ (u : V) (H : ℕ), (∑ s ∈ Finset.range H, Dynamics.expList (CoinChoices G q) s fun (l : List (CoinChoices G q)) => if ((Finset.Icc 1 s).biUnion fun (t : ℕ) => cobraCoinRun p {u} (List.take t l)) = Finset.univ then 0 else 1) ≤ C * Real.log ↑(Fintype.card V)

              Theorem 3 (Section 1), expectation bound: under the same hypotheses, every partial tail sum ∑_{s < H} P(cov(u) > s) of the cover time of COBRA with branching factor 1 + ρ is at most C log n.