Documentation

Dynamics.Adaptive

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 of an adaptive observation process #

def Dynamics.hist {Ω : Type u_1} {β : Type u_2} (obs : List β → Ω → β) (ω : Ω) :
ℕ → List β

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
Instances For
    @[simp]
    theorem Dynamics.hist_zero {Ω : Type u_1} {β : Type u_2} (obs : List β → Ω → β) (ω : Ω) :
    hist obs ω 0 = []
    @[simp]
    theorem Dynamics.length_hist {Ω : Type u_1} {β : Type u_2} (obs : List β → Ω → β) (ω : Ω) (k : ℕ) :
    (hist obs ω k).length = k
    theorem Dynamics.hist_succ_eq_iff {Ω : Type u_1} {β : Type u_2} (obs : List β → Ω → β) (ω : Ω) (k : ℕ) (h : List β) (b : β) :
    hist obs ω (k + 1) = h ++ [b] ↔ hist obs ω k = h ∧ obs h ω = b
    theorem Dynamics.hist_eq_iff {Ω : Type u_1} {β : Type u_2} (obs : List β → Ω → β) (ω : Ω) (L : List β) :
    hist obs ω L.length = L ↔ ∀ k < L.length, some (obs (List.take k L) ω) = L[k]?

    The history is a given list L iff every observation along L gives the next entry of L.

    noncomputable def Dynamics.histProd {Ω : Type u_1} {β : Type u_2} (obs : List β → Ω → β) (f : List β → β → ℝ) (ω : Ω) (j m : ℕ) :

    The product of the factors f along the first m steps, from step j on.

    Equations
    Instances For
      theorem Dynamics.histProd_succ {Ω : Type u_1} {β : Type u_2} (obs : List β → Ω → β) (f : List β → β → ℝ) (ω : Ω) (j m : ℕ) :
      histProd obs f ω j (m + 1) = f (hist obs ω j) (obs (hist obs ω j) ω) * histProd obs f ω (j + 1) m
      theorem Dynamics.histProd_zero_succ {Ω : Type u_1} {β : Type u_2} (obs : List β → Ω → β) (f : List β → β → ℝ) (ω : Ω) (k : ℕ) :
      histProd obs f ω 0 (k + 1) = histProd obs f ω 0 k * f (hist obs ω k) (obs (hist obs ω k) ω)
      theorem Dynamics.histProd_nonneg {Ω : Type u_1} {β : Type u_2} (obs : List β → Ω → β) {f : List β → β → ℝ} (hf0 : ∀ (h : List β) (b : β), 0 ≤ f h b) (ω : Ω) (j m : ℕ) :
      0 ≤ histProd obs f ω j m

      The supermartingale lemma #

      theorem Dynamics.Distribution.expect_ind_histProd_le {Ω : Type u_1} {β : Type u_2} [Fintype Ω] [Fintype β] [DecidableEq β] (P : Distribution Ω) (obs : List β → Ω → β) (f : List β → β → ℝ) (hf0 : ∀ (h : List β) (b : β), 0 ≤ f h b) (hf : ∀ (h : List β), (P.expect fun (ω : Ω) => if hist obs ω h.length = h then f h (obs h ω) else 0) ≤ P.expect fun (ω : Ω) => if hist obs ω h.length = h then 1 else 0) (m : ℕ) (h₀ : List β) :
      (P.expect fun (ω : Ω) => if hist obs ω h₀.length = h₀ then histProd obs f ω h₀.length m else 0) ≤ P.expect fun (ω : Ω) => if hist obs ω h₀.length = h₀ then 1 else 0

      Conditioning step: from step j on, after the history h₀, the product of the factors has conditional expectation at most 1.

      theorem Dynamics.Distribution.expect_prod_hist_le_one {Ω : Type u_1} {β : Type u_2} [Fintype Ω] [Fintype β] [DecidableEq β] (P : Distribution Ω) (obs : List β → Ω → β) (f : List β → β → ℝ) (hf0 : ∀ (h : List β) (b : β), 0 ≤ f h b) (hf : ∀ (h : List β), (P.expect fun (ω : Ω) => if hist obs ω h.length = h then f h (obs h ω) else 0) ≤ P.expect fun (ω : Ω) => if hist obs ω h.length = h then 1 else 0) (m : ℕ) :
      (P.expect fun (ω : Ω) => histProd obs f ω 0 m) ≤ 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) #

      def Dynamics.readSet {ι : Type u_1} {β : Type u_3} [DecidableEq ι] (supp : List β → Finset ι) (h : List β) :

      The coordinates read during the history h, the observation after the history h' reading the coordinates supp h'.

      Equations
      Instances For
        theorem Dynamics.hist_eq_iff_of_agree {ι : Type u_1} {α : Type u_2} {β : Type u_3} [DecidableEq ι] (obs : List β → (ι → α) → β) (supp : List β → Finset ι) (hobs : ∀ (h : List β) (ω ω' : ι → α), (∀ i ∈ supp h, ω i = ω' i) → obs h ω = obs h ω') (h : List β) (ω ω' : ι → α) :
        (∀ i ∈ readSet supp h, ω i = ω' i) → (hist obs ω h.length = h ↔ hist obs ω' h.length = h)

        The event that the history is h depends only on the coordinates read along h.

        theorem Dynamics.Distribution.expect_prod_hist_le_one_of_fresh {ι : Type u_1} {α : Type u_2} {β : Type u_3} [Fintype ι] [DecidableEq ι] [Fintype α] [Fintype β] [DecidableEq β] (P : ι → Distribution α) (obs : List β → (ι → α) → β) (supp : List β → Finset ι) (hobs : ∀ (h : List β) (ω ω' : ι → α), (∀ i ∈ supp h, ω i = ω' i) → obs h ω = obs h ω') (hfresh : ∀ (h : List β), Disjoint (supp h) (readSet supp h)) (f : List β → β → ℝ) (hf0 : ∀ (h : List β) (b : β), 0 ≤ f h b) (hf : ∀ (h : List β), ((independent P).expect fun (ω : ι → α) => f h (obs h ω)) ≤ 1) (m : ℕ) :
        ((independent P).expect fun (ω : ι → α) => histProd obs f ω 0 m) ≤ 1

        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.