Documentation

Epidemics.CobraDual

COBRA ⇔ BIPS duality as a duality of kernels (EPI-4) #

The dictionary relation duality is Dynamics.Kernel.Dual H K L, š”¼_x[H(X₁, y)] = š”¼_y[H(x, Y₁)], which then holds at every time (Dynamics.Kernel.Dual.iterate). Theorem 4 of Cooper, Radzik and Rivera (PODC 2016) is such a duality, for H(C, A) = 1{C ∩ A = āˆ…}, between

In one round both sides of the identity agree for every choice of neighbours (cobraStopStep_inter_eq_empty_iff), so the kernels are dual (cobra_bips_dual) and the duality holds at every time. With Aā‚€ = {v} this is Theorem 4 with the hitting probability of the COBRA kernel (cobra_bips_duality_hitProb), and it gives the statement cobra_bips_duality back by the Markov property, without reversing the rounds (cobra_bips_duality_of_dual). The kernels need a round of neighbour choices to exist (Nonempty (Choices G k), true on the connected graphs with at least two vertices of the paper, choices_nonempty).

def Epidemics.bipsSourceStep {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} {k : ā„•} (v : V) (A : { A : Finset V // v ∈ A }) (r : Choices G k) :
{ A : Finset V // v ∈ A }

One BIPS round with persistent source v, on the sets that contain v.

Equations
Instances For
    def Epidemics.cobraStopStep {V : Type u_1} [DecidableEq V] {G : SimpleGraph V} {k : ā„•} (v : V) (C : Finset V) (r : Choices G k) :

    One COBRA round, stopped once v has been visited.

    Equations
    Instances For
      noncomputable def Epidemics.cobraStopped {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {k : ā„•} [Nonempty (Choices G k)] (v : V) :

      COBRA stopped when it visits v: the stopped chain of the COBRA kernel on sets of vertices.

      Equations
      Instances For
        noncomputable def Epidemics.bipsKernel {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {k : ā„•} [Nonempty (Choices G k)] (v : V) :

        BIPS with persistent source v, as a kernel on the sets that contain v.

        Equations
        Instances For
          theorem Epidemics.cobraStopStep_inter_eq_empty_iff {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} {k : ā„•} {v : V} (C : Finset V) {A : Finset V} (hA : v ∈ A) (r : Choices G k) :

          One round of the duality, pathwise. If v ∈ A, then for every round r, COBRA stopped at v from C avoids A after r iff C avoids BIPS from A after r.

          The stopped COBRA kernel is the kernel of the stopped round cobraStopStep.

          theorem Epidemics.cobra_bips_dual {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {k : ā„•} [Nonempty (Choices G k)] (v : V) :
          Dynamics.Kernel.Dual (fun (C : Finset V) (A : { A : Finset V // v ∈ A }) => if C ∩ ↑A = āˆ… then 1 else 0) (cobraStopped v) (bipsKernel v)

          COBRA ⇔ BIPS duality (Theorem 4) as a duality of kernels. COBRA stopped when it visits v and BIPS with persistent source v are dual with respect to H(C, A) = 1{C ∩ A = āˆ…}: š”¼_C[H(C₁, A)] = š”¼_A[H(C, A₁)] for every set C and every set A āˆ‹ v.

          theorem Epidemics.cobra_bips_duality_hitProb {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {k : ā„•} [Nonempty (Choices G k)] (v : V) (C : Finset V) (t : ā„•) :
          1 - (Dynamics.Kernel.ofStep cobraStep).hitProb (fun (D : Finset V) => v ∈ D) t C = (bipsKernel v).iterate t (fun (A : { A : Finset V // v ∈ A }) => if C ∩ ↑A = āˆ… then 1 else 0) ⟨{v}, ā‹ÆāŸ©

          Theorem 4 with hitting probabilities. For every vertex v, set C and time t, the probability that the COBRA kernel started from C has not visited v by time t, 1 - P_C(Hit_C(v) ≤ t), equals the probability that BIPS with source v started from {v} has not infected any vertex of C at time t.

          theorem Epidemics.not_mem_foldl_cobraStopStep {V : Type u_1} [DecidableEq V] {G : SimpleGraph V} {k : ā„•} (v : V) (C : Finset V) (l : List (Choices G k)) :
          v āˆ‰ List.foldl (cobraStopStep v) C l ↔ āˆ€ s ≤ l.length, v āˆ‰ cobraRun C (List.take s l)

          Stopped COBRA has not visited v after the rounds l iff COBRA has not visited v at any time s ≤ l.length.

          theorem Epidemics.foldl_bipsSourceStep {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} {k : ā„•} (v : V) (A : { A : Finset V // v ∈ A }) (l : List (Choices G k)) :
          ↑(List.foldl (bipsSourceStep v) A l) = bipsRun v (↑A) l

          BIPS on the sets that contain v runs as bipsRun.

          theorem Epidemics.cobra_bips_duality_of_dual {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {k : ā„•} [Nonempty (Choices G k)] (v : V) (C : Finset V) (t : ā„•) :
          (Dynamics.expList (Choices G k) t fun (l : List (Choices G k)) => if āˆ€ s ≤ t, v āˆ‰ cobraRun C (List.take s l) then 1 else 0) = Dynamics.expList (Choices G k) t fun (l : List (Choices G k)) => if C ∩ bipsRun v {v} l = āˆ… then 1 else 0

          Theorem 4 again, from the duality of kernels. The statement cobra_bips_duality, under Nonempty (Choices G k), derived from the one-round duality cobra_bips_dual by Dynamics.Kernel.Dual.iterate (the Markov property) instead of the reversal of the rounds.