Adaptive observations: a finite supermartingale lemma (EPI-6, tools) #
Tools for the exploration argument of [BCDPTZ22] (Appendix C), in finite probability.
- Histories. An adaptive process observes
obs h ωafter the historyhof previous observations (hist obs ω kis the history afterksteps, in the core'sDynamics.Adaptive). EPI-3'squeryAnswers(one coin per step) is the special caseobs h ω = ω (next h); here the observations are arbitrary (blocks of coins, partners in a matching, …). - Supermartingale lemma (the core's
Distribution.expect_prod_hist_le_one): if every factorf h b ≥ 0has conditional expectation at most1given the historyh, the product of the factors along the process has expectation at most1. With Markov's inequality this gives the tail bound of the exploration (Epidemics.SmallWorldExplore), in the role of the Galton–Watson comparison of the paper. - Coordinatewise combination of independent families (the core's
Distribution.expect_expect_coord, inDynamics.Independent): ifxandyare independent families,fun i => φ i (x i) (y i)is an independent family. This gives the independence of disjoint sets of coordinates (Distribution.expect_mul_of_dep) and, inEpidemics.SmallWorldCollapse, the law of the percolatedSWG(n, q). - Fresh observations of independent coordinates (the core's
Distribution.expect_prod_hist_le_one_of_fresh): if each observation reads coordinates not read before, the conditional expectation is the unconditional one, so it suffices thatE[f h (obs h ω)] ≤ 1for every historyh(principle of deferred decisions). - Blocks of coins: the moment-generating function of the open coordinates of a block (the
core's
Distribution.independent_bernoulli_expect_exp_sum, inDynamics.Chernoff) and the bound1 - r + r eˣ ≤ exp (κ r x)(one_sub_add_mul_exp_le).