Adaptive observations: a product supermartingale and deferred decisions #
An adaptive process observes obs h ω after the history h of its previous observations, the
randomness being ω (hist obs ω k is the history after k steps). Examples: querying one coin
ω (next h) per step (EPI-3's depth-first search, where obs h ω = ω (next h)), or a block of
coins, or the partners of a node in a random matching (EPI-6's exploration).
- Histories.
hist, its length, one more step (hist_succ_eq_iff), and the history as a list of prescribed answers (hist_eq_iff). - Supermartingale lemma (
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 (histProd) has expectation at most1. With Markov's inequality this bounds the probability that the product is large. - Deferred decisions (
Distribution.expect_prod_hist_le_one_of_fresh): under an independent familyDistribution.independent P, if each observation reads coordinates not read before along the history (readSet), the conditional expectation of a factor is its unconditional expectation, so it suffices thatE[f h (obs h ω)] ≤ 1for every historyh.
Histories of an adaptive observation process #
The history of an adaptive observation process after k steps: the list of the first k
observations, the observation after the history h being obs h ω.
Equations
- Dynamics.hist obs ω 0 = []
- Dynamics.hist obs ω k.succ = Dynamics.hist obs ω k ++ [obs (Dynamics.hist obs ω k) ω]
Instances For
The product of the factors f along the first m steps, from step j on.
Equations
- Dynamics.histProd obs f ω j m = ∏ k ∈ Finset.Ico j (j + m), f (Dynamics.hist obs ω k) (obs (Dynamics.hist obs ω k) ω)
Instances For
The supermartingale lemma #
Conditioning step: from step j on, after the history h₀, the product of the factors has
conditional expectation at most 1.
Supermartingale lemma. If the factors f h b ≥ 0 have conditional expectation at most
1 given every history h, then the product of the factors along the first m steps of the
process has expectation at most 1.
Fresh observations of independent coordinates (deferred decisions) #
The coordinates read during the history h, the observation after the history h' reading
the coordinates supp h'.
Equations
- Dynamics.readSet supp h = (Finset.range h.length).biUnion fun (j : ℕ) => supp (List.take j h)
Instances For
The event that the history is h depends only on the coordinates read along h.
Deferred decisions for adaptive observations of independent coordinates. If every
observation obs h ω reads only the coordinates supp h, which were not read before along h,
and the factors satisfy E[f h (obs h ω)] ≤ 1 for every history h (an unconditional
expectation), then the product of the factors along the process has expectation at most 1.