Documentation

Dynamics.Perturbed

Perturbed round-based processes #

A round-based process step : S → R → S, driven by i.i.d. uniform rounds, is perturbed within Adm along a function P : List R → S of the rounds played so far when P [] = s and, after every round r, the new state P (l ++ [r]) is related by Adm to the unperturbed step (P l) r. Since P may depend on the whole list of rounds, this covers adaptive adversaries; the process is no longer a Markov chain on S, but every bound below only needs one-round estimates that hold for every admissible perturbation of the round.

Two phases of such a run are glued with Dynamics.expList_le_of_split.

noncomputable def Dynamics.failInd (p : Prop) :

Indicator of the failure of a proposition: 0 if it holds, 1 otherwise (for a membership b ∈ B, this is Kernel.outside B b).

Equations
Instances For
    theorem Dynamics.failInd_of {p : Prop} (h : p) :

    A proposition that holds does not fail.

    theorem Dynamics.failInd_of_not {p : Prop} (h : ¬p) :

    A proposition that does not hold fails.

    A failure indicator is nonnegative.

    A failure indicator is at most 1.

    theorem Dynamics.failInd_mono {p q : Prop} (h : p → q) :

    A stronger proposition fails more often.

    def Dynamics.Perturbed {S : Type u_1} {R : Type u_2} (step : S → R → S) (Adm : S → S → Prop) (s : S) (P : List R → S) :

    P is a run of step from s perturbed within Adm: it starts at s and, after every round r, the new state is related by Adm to the output of step.

    Equations
    Instances For
      theorem Dynamics.Perturbed.shift {S : Type u_1} {R : Type u_2} {step : S → R → S} {Adm : S → S → Prop} {s : S} {P : List R → S} (hP : Perturbed step Adm s P) (l₀ : List R) :
      Perturbed step Adm (P l₀) fun (l : List R) => P (l₀ ++ l)

      After the rounds l₀, a perturbed run is again a perturbed run.

      theorem Dynamics.Perturbed.first {S : Type u_1} {R : Type u_2} {step : S → R → S} {Adm : S → S → Prop} {s : S} {P : List R → S} (hP : Perturbed step Adm s P) (r : R) :
      Adm (step s r) (P [r])

      The first round of a perturbed run is a perturbation of one round from its start.

      theorem Dynamics.expList_le_of_drift_perturbed {S : Type u_1} {R : Type u_2} [Fintype R] [Nonempty R] (step : S → R → S) (Adm : S → S → Prop) (φ : S → ℝ) {ρ ε : ℝ} (hρ0 : 0 ≤ ρ) (hρ1 : ρ ≤ 1) (hε : 0 ≤ ε) (hφ : ∀ (s : S) (g : R → S), (∀ (r : R), Adm (step s r) (g r)) → (avg fun (r : R) => φ (g r)) ≤ ρ * φ s + ε) (T : ℕ) (s : S) (P : List R → S) :
      Perturbed step Adm s P → (expList R T fun (l : List R) => φ (P l)) ≤ ρ ^ T * φ s + ↑T * ε

      Fixed-time drift for perturbed runs. If every perturbed round maps the potential φ to at most ρ φ + ε in expectation (0 ≤ ρ ≤ 1, 0 ≤ ε), then after T rounds the expected potential is at most ρ ^ T φ + T ε.

      theorem Dynamics.expList_path_perturbed {S : Type u_1} {R : Type u_2} [Fintype R] [Nonempty R] (step : S → R → S) (Adm : S → S → Prop) {ε : ℝ} (hε : 0 ≤ ε) (T : ℕ) (B : ℕ → Set S) :
      (∀ (i : ℕ), ∀ s ∈ B i, ∀ (g : R → S), (∀ (r : R), Adm (step s r) (g r)) → (avg fun (r : R) => failInd (g r ∈ B (i + 1))) ≤ ε) → ∀ (s : S) (P : List R → S), Perturbed step Adm s P → s ∈ B 0 → (expList R T fun (l : List R) => failInd (∀ t ≤ T, P (List.take t l) ∈ B t)) ≤ ↑T * ε

      Chains of moves for perturbed runs. If, for every i, every perturbed round from a state of B i misses B (i + 1) with probability at most ε, then a perturbed run from B 0 fails to follow P (l.take t) ∈ B t for all t ≤ T with probability at most T ε.