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
- COBRA stopped when it visits
v(cobraStopped v, the stopped chainKernel.stoppedof the COBRA kernel): it avoidsvup to timetiffHit_C(v) > t; - BIPS with persistent source
von the sets that containv(bipsKernel v): BIPS starts from{v}and never losesv.
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).
One BIPS round with persistent source v, on the sets that contain v.
Equations
- Epidemics.bipsSourceStep v A r = āØEpidemics.bipsStep v (āA) r, āÆā©
Instances For
One COBRA round, stopped once v has been visited.
Equations
- Epidemics.cobraStopStep v C r = if v ā C then C else Epidemics.cobraStep C r
Instances For
COBRA stopped when it visits v: the stopped chain of the COBRA kernel on sets of vertices.
Equations
- Epidemics.cobraStopped v = (Dynamics.Kernel.ofStep Epidemics.cobraStep).stopped fun (C : Finset V) => v ā C
Instances For
BIPS with persistent source v, as a kernel on the sets that contain v.
Equations
Instances For
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.
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 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.
Stopped COBRA has not visited v after the rounds l iff COBRA has not visited v at any
time s ⤠l.length.
BIPS on the sets that contain v runs as bipsRun.
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.