Documentation

Dynamics.Rounds

Processes driven by independent uniform rounds #

Many dynamics in this repository are given by a deterministic update step : S → R → S applied to a sequence of i.i.d. uniform rounds r : R, with expectations computed by expList. ofStep step is the corresponding finite Markov kernel, and iterate_ofStep identifies its iterates with the expList expectations, so results about kernels (for instance Dynamics.Kernel.nested_phases) apply to such round-based processes. The probability missProb of missing a target after T rounds composes over stages (missProb_comp) and, for a target closed under every round, amplifies over consecutive blocks (missProb_amplify).

noncomputable def Dynamics.Kernel.ofStep {S : Type u_1} {R : Type u_2} [Fintype S] [Fintype R] [Nonempty R] (step : S → R → S) :

The Markov kernel of one uniformly random round of step.

Equations
Instances For
    theorem Dynamics.Kernel.apply_ofStep {S : Type u_1} {R : Type u_2} [Fintype S] [Fintype R] [Nonempty R] (step : S → R → S) (f : S → ℝ) (s : S) :
    (ofStep step).apply f s = avg fun (r : R) => f (step s r)
    theorem Dynamics.Kernel.ofStep_weight_pos {S : Type u_1} {R : Type u_2} [Fintype S] [Fintype R] [Nonempty R] (step : S → R → S) (s : S) (r : R) :
    0 < (ofStep step s).weight (step s r)

    Every outcome of one round has positive probability.

    theorem Dynamics.Kernel.prob_ofStep {S : Type u_1} {R : Type u_2} [Fintype S] [Fintype R] [Nonempty R] (step : S → R → S) (P : S → Prop) (s : S) :
    (ofStep step s).prob P = avg fun (r : R) => if P (step s r) then 1 else 0
    theorem Dynamics.Kernel.iterate_ofStep {S : Type u_1} {R : Type u_2} [Fintype S] [Fintype R] [Nonempty R] (step : S → R → S) (T : ℕ) (f : S → ℝ) (s : S) :
    (ofStep step).iterate T f s = expList R T fun (l : List R) => f (List.foldl step s l)

    Iterating the kernel is averaging over T i.i.d. uniform rounds.

    theorem Dynamics.Kernel.event_ofStep {S : Type u_1} {R : Type u_2} [Fintype S] [Fintype R] [Nonempty R] (step : S → R → S) (P : S → Prop) (T : ℕ) (s : S) :
    (ofStep step).event P T s = expList R T fun (l : List R) => if P (List.foldl step s l) then 1 else 0
    theorem Dynamics.expList_escape {S : Type u_1} {R : Type u_2} [Fintype R] [Nonempty R] (step : S → R → S) {p : ℝ} (hp : 0 ≤ p) (T : ℕ) (G : ℕ → Set S) (x : S) :
    x ∈ G 0 → (∀ t < T, ∀ y ∈ G t, (avg fun (r : R) => if step y r ∈ G (t + 1) then 0 else 1) ≤ p) → (expList R T fun (l : List R) => if List.foldl step x l ∈ G T then 0 else 1) ≤ ↑T * p

    Escaping a moving target. If a round-based process starts in G 0 and, for every t < T, one round from any state of G t misses G (t + 1) with probability at most p, then after T rounds it lies outside G T with probability at most T p. This is the union bound over rounds used by lower bounds such as Theorem 4.2 of Becchetti et al. (SPAA 2014).

    Missing a target after i.i.d. rounds #

    noncomputable def Dynamics.missProb {S : Type u_1} {R : Type u_2} [Fintype R] (step : S → R → S) (B : Set S) (T : ℕ) (s : S) :

    Probability that the process driven by T i.i.d. uniform rounds of step, started at s, is outside B after T rounds.

    Equations
    Instances For
      theorem Dynamics.missProb_zero {S : Type u_1} {R : Type u_2} [Fintype R] (step : S → R → S) (B : Set S) (s : S) :
      missProb step B 0 s = if s ∈ B then 0 else 1

      With no round, the process misses B exactly when it starts outside B.

      theorem Dynamics.missProb_succ {S : Type u_1} {R : Type u_2} [Fintype R] (step : S → R → S) (B : Set S) (T : ℕ) (s : S) :
      missProb step B (T + 1) s = avg fun (r : R) => missProb step B T (step s r)

      The first round is averaged out first.

      theorem Dynamics.missProb_nonneg {S : Type u_1} {R : Type u_2} [Fintype R] (step : S → R → S) (B : Set S) (T : ℕ) (s : S) :
      0 ≤ missProb step B T s

      A missing probability is nonnegative.

      theorem Dynamics.missProb_le_one {S : Type u_1} {R : Type u_2} [Fintype R] [Nonempty R] (step : S → R → S) (B : Set S) (T : ℕ) (s : S) :
      missProb step B T s ≤ 1

      A missing probability is at most 1.

      theorem Dynamics.missProb_mono {S : Type u_1} {R : Type u_2} [Fintype R] (step : S → R → S) {B B' : Set S} (h : B ⊆ B') (T : ℕ) (s : S) :
      missProb step B' T s ≤ missProb step B T s

      Missing a smaller set is more likely.

      theorem Dynamics.missProb_comp {S : Type u_1} {R : Type u_2} [Fintype R] [Nonempty R] (step : S → R → S) {B D : Set S} {T₁ T₂ : ℕ} {e : ℝ} (he : 0 ≤ e) (hD : ∀ y ∈ B, missProb step D T₂ y ≤ e) (s : S) :
      missProb step D (T₁ + T₂) s ≤ missProb step B T₁ s + e

      Composition of stages (Markov property): if from every state of B the process misses D after T₂ rounds with probability at most e, then from s it misses D after T₁ + T₂ rounds with probability at most missProb step B T₁ s + e.

      theorem Dynamics.missProb_of_closed {S : Type u_1} {R : Type u_2} [Fintype R] (step : S → R → S) {B : Set S} (hB : ∀ y ∈ B, ∀ (r : R), step y r ∈ B) {y : S} (hy : y ∈ B) (T : ℕ) :
      missProb step B T y = 0

      A target closed under every round is never left.

      theorem Dynamics.missProb_antitone {S : Type u_1} {R : Type u_2} [Fintype R] [Nonempty R] (step : S → R → S) {B : Set S} (hB : ∀ y ∈ B, ∀ (r : R), step y r ∈ B) (s : S) {T T' : ℕ} (h : T ≤ T') :
      missProb step B T' s ≤ missProb step B T s

      The probability of missing a target closed under every round does not increase with time.

      theorem Dynamics.missProb_amplify {S : Type u_1} {R : Type u_2} [Fintype R] (step : S → R → S) {B : Set S} (hB : ∀ y ∈ B, ∀ (r : R), step y r ∈ B) {T : ℕ} {p : ℝ} (hp : ∀ (y : S), missProb step B T y ≤ p) (k : ℕ) (s : S) :
      missProb step B (k * T) s ≤ p ^ k

      Amplification (the expList form of Dynamics.Kernel.event_amplify): if a target closed under every round is missed after T rounds with probability at most p from every state, then it is missed after k T rounds with probability at most p ^ k, since each block of T rounds fails independently of the previous ones.