Documentation

Dynamics.Relations

Relations between finite chains #

The cross-field dictionary of Leanamics (home_page/_data/dictionary.yml) says that processes of different fields are the same Markov chain, or are related by a kind of relation. This file gives four of these kinds a precise meaning for finite kernels Kernel α = α → Distribution α, quoting the dictionary's description of each kind.

The other kinds of the dictionary (same continuous-time chain, coupling, large-population limit, same deterministic recursion) are not statements about one step of two finite kernels and are not defined here.

theorem Dynamics.Distribution.ext {α : Type u_1} [Fintype α] {p q : Distribution α} (h : ∀ (a : α), p.weight a = q.weight a) :
p = q

Distributions with the same weights are equal.

theorem Dynamics.Distribution.weight_eq_expect_ite {α : Type u_1} [Fintype α] [DecidableEq α] (p : Distribution α) (a : α) :
p.weight a = p.expect fun (b : α) => if b = a then 1 else 0

The weight of a point is the expectation of its indicator.

theorem Dynamics.Distribution.ext_expect {α : Type u_1} [Fintype α] {p q : Distribution α} (h : ∀ (f : α → ℝ), p.expect f = q.expect f) :
p = q

Distributions with the same expectations are equal.

theorem Dynamics.Distribution.map_map {α : Type u_1} {β : Type u_2} {γ : Type u_3} [Fintype α] [Fintype β] [Fintype γ] (p : Distribution α) (f : α → β) (g : β → γ) :
(p.map f).map g = p.map fun (a : α) => g (f a)

Transporting along f and then along g is transporting along g ∘ f.

theorem Dynamics.Distribution.map_point {α : Type u_1} {β : Type u_2} [Fintype α] [Fintype β] (a : α) (f : α → β) :
(point a).map f = point (f a)

A point mass is transported to a point mass.

theorem Dynamics.Distribution.expect_comm {α : Type u_1} {β : Type u_2} [Fintype α] [Fintype β] (p : Distribution α) (q : Distribution β) (F : α → β → ℝ) :
(p.expect fun (a : α) => q.expect (F a)) = q.expect fun (b : β) => p.expect fun (a : α) => F a b

Fubini's theorem for two finite distributions.

Laws at finite times #

theorem Dynamics.Kernel.advance_expect {α : Type u_1} [Fintype α] (K : Kernel α) (p : Distribution α) (g : α → ℝ) :
(K.advance p).expect g = p.expect (K.apply g)

Expectations after one step of a distribution: 𝔼_{pK}[g] = 𝔼_p[Kg].

theorem Dynamics.Kernel.law_expect {α : Type u_1} [Fintype α] (K : Kernel α) (p : Distribution α) (t : ℕ) (g : α → ℝ) :
(K.law p t).expect g = p.expect (K.iterate t g)

The law at time t computes the expectations at time t: 𝔼_{pKᵗ}[g] = 𝔼_p[Kᵗg]; from a point mass, (K.law (point x) t).expect g = K.iterate t g x.

Same chain on counts: lumping #

def Dynamics.Kernel.Lumps {α : Type u_1} {β : Type u_2} [Fintype α] [Fintype β] (f : α → β) (K : Kernel α) (L : Kernel β) :

Same chain on counts (kind same-chain of the dictionary: "the same transition kernel, on configurations or, where stated, on counts"). K lumps to L along f when, from every state x, one step of K observed through f is one step of L from f x: (K x).map f = L (f x). Then f(X_t) evolves as the chain L from f x: it has the same law at every time (Lumps.law) and the same path functionals (Lumps.trajectory).

Equations
Instances For
    theorem Dynamics.Kernel.lumps_iff_apply {α : Type u_1} {β : Type u_2} [Fintype α] [Fintype β] {f : α → β} {K : Kernel α} {L : Kernel β} :
    Lumps f K L ↔ ∀ (g : β → ℝ) (x : α), K.apply (fun (a : α) => g (f a)) x = L.apply g (f x)

    A lumping in terms of observables: 𝔼_x[g(f(X₁))] = 𝔼_{f x}[g(Y₁)] for every g.

    theorem Dynamics.Kernel.Lumps.apply {α : Type u_1} {β : Type u_2} [Fintype α] [Fintype β] {f : α → β} {K : Kernel α} {L : Kernel β} (h : Lumps f K L) (g : β → ℝ) (x : α) :
    K.apply (fun (a : α) => g (f a)) x = L.apply g (f x)

    One step of a lumping, on observables.

    theorem Dynamics.Kernel.Lumps.iterate {α : Type u_1} {β : Type u_2} [Fintype α] [Fintype β] {f : α → β} {K : Kernel α} {L : Kernel β} (h : Lumps f K L) (t : ℕ) (g : β → ℝ) (x : α) :
    K.iterate t (fun (a : α) => g (f a)) x = L.iterate t g (f x)

    A lumping lifts to every time, on observables: 𝔼_x[g(f(X_t))] = 𝔼_{f x}[g(Y_t)].

    theorem Dynamics.Kernel.Lumps.law {α : Type u_1} {β : Type u_2} [Fintype α] [Fintype β] {f : α → β} {K : Kernel α} {L : Kernel β} (h : Lumps f K L) (p : Distribution α) (t : ℕ) :
    (K.law p t).map f = L.law (p.map f) t

    A lumping lifts to the law at every time: (pKᵗ).map f = (p.map f) Lᵗ; from a point mass, (K^t x).map f = L^t (f x).

    theorem Dynamics.Kernel.Lumps.event {α : Type u_1} {β : Type u_2} [Fintype α] [Fintype β] {f : α → β} {K : Kernel α} {L : Kernel β} (h : Lumps f K L) (s : β → Prop) (t : ℕ) (x : α) :
    K.event (fun (a : α) => s (f a)) t x = L.event s t (f x)

    The probability that f(X_t) lies in s is the probability that Y_t lies in s.

    theorem Dynamics.Kernel.Lumps.trajectory {α : Type u_1} {β : Type u_2} [Fintype α] [Fintype β] {f : α → β} {K : Kernel α} {L : Kernel β} (h : Lumps f K L) (t : ℕ) (x : α) (F : List β → β → ℝ) :
    (K.trajectory t x fun (l : List α) (c : α) => F (List.map f l) (f c)) = L.trajectory t (f x) F

    A lumping lifts to functionals of the whole trajectory up to time t.

    theorem Dynamics.Kernel.Lumps.hitProb {α : Type u_1} {β : Type u_2} [Fintype α] [Fintype β] {f : α → β} {K : Kernel α} {L : Kernel β} (h : Lumps f K L) (B : β → Prop) (t : ℕ) (x : α) :
    K.hitProb (fun (a : α) => B (f a)) t x = L.hitProb B t (f x)

    Hitting probabilities transfer: P_x(f(X_s) ∈ B for some s ≤ t) = P_{f x}(Y_s ∈ B for some s ≤ t).

    theorem Dynamics.Kernel.Lumps.comp {α : Type u_1} {β : Type u_2} {γ : Type u_3} [Fintype α] [Fintype β] [Fintype γ] {f : α → β} {K : Kernel α} {L : Kernel β} {M : Kernel γ} {g : β → γ} (h : Lumps f K L) (h' : Lumps g L M) :
    Lumps (fun (a : α) => g (f a)) K M

    Lumpings compose.

    Same jump chain #

    theorem Dynamics.Kernel.sum_erase_weight {α : Type u_1} [Fintype α] (K : Kernel α) (x : α) [DecidableEq α] :
    ∑ y ∈ Finset.univ.erase x, (K x).weight y = 1 - (K x).weight x

    The weights of the states other than x add up to 1 - K(x, x).

    theorem Dynamics.Kernel.weight_eq_zero_of_weight_self {α : Type u_1} [Fintype α] (K : Kernel α) {x : α} (hx : (K x).weight x = 1) {y : α} (hy : y ≠ x) :
    (K x).weight y = 0

    A state that K never leaves gives no weight to the other states.

    theorem Dynamics.Kernel.eq_point_of_weight_self {α : Type u_1} [Fintype α] (K : Kernel α) {x : α} (hx : (K x).weight x = 1) :

    A state that K never leaves: one step from it is the point mass.

    noncomputable def Dynamics.Kernel.jump {α : Type u_1} [Fintype α] (K : Kernel α) :

    The jump chain of K (kind jump-chain of the dictionary: "the same chain once idle steps are removed"): from x, the step of K conditioned on leaving x, which gives weight K(x, y) / (1 - K(x, x)) to every y ≠ x. A state that K never leaves (K(x, x) = 1) stays absorbing.

    Equations
    Instances For
      def Dynamics.Kernel.SameJumpChain {α : Type u_1} [Fintype α] (K L : Kernel α) :

      Two kernels have the same jump chain (kind jump-chain of the dictionary).

      Equations
      Instances For
        theorem Dynamics.Kernel.jump_of_weight_self {α : Type u_1} [Fintype α] (K : Kernel α) {x : α} (hx : (K x).weight x = 1) :

        From a state that K never leaves, the jump chain stays put.

        theorem Dynamics.Kernel.jump_weight_self {α : Type u_1} [Fintype α] (K : Kernel α) {x : α} (hx : (K x).weight x ≠ 1) :
        (K.jump x).weight x = 0

        From a state that K may leave, the jump chain moves.

        theorem Dynamics.Kernel.weight_eq_mul_jump {α : Type u_1} [Fintype α] (K : Kernel α) {x y : α} (hy : y ≠ x) :
        (K x).weight y = (1 - (K x).weight x) * (K.jump x).weight y

        Off the diagonal, K(x, y) = (1 - K(x, x)) · J(x, y) for the jump chain J of K.

        theorem Dynamics.Kernel.apply_eq_jump {α : Type u_1} [Fintype α] (K : Kernel α) (g : α → ℝ) (x : α) :
        K.apply g x = (K x).weight x * g x + (1 - (K x).weight x) * K.jump.apply g x

        One step of K stays put with probability K(x, x) and otherwise follows its jump chain: Kg(x) = K(x, x) g(x) + (1 - K(x, x)) Jg(x).

        theorem Dynamics.Kernel.apply_eq_self_iff_jump {α : Type u_1} [Fintype α] (K : Kernel α) (g : α → ℝ) (x : α) :
        K.apply g x = g x ↔ K.jump.apply g x = g x

        g is harmonic at x for K iff it is harmonic at x for the jump chain of K.

        theorem Dynamics.Kernel.sameJumpChain_of_weight {α : Type u_1} [Fintype α] {K L : Kernel α} (h : ∀ (x : α), ∃ (c : ℝ), 0 < c ∧ ∀ (y : α), y ≠ x → (K x).weight y = c * (L x).weight y) :

        Criterion for the same jump chain. If, from every state, the rows of K and L are proportional off the diagonal with a positive factor, then K and L have the same jump chain.

        theorem Dynamics.Kernel.jump_jump {α : Type u_1} [Fintype α] (K : Kernel α) :

        The jump chain of a jump chain is itself.

        theorem Dynamics.Kernel.jump_eq_self {α : Type u_1} [Fintype α] (K : Kernel α) (h : ∀ (x : α), (K x).weight x = 0 ∨ (K x).weight x = 1) :
        K.jump = K

        A kernel that stays put only at the states it never leaves is its own jump chain.

        A lazy version has the same jump chain: its idle steps are removed.

        theorem Dynamics.Kernel.SameJumpChain.apply_eq_self_iff {α : Type u_1} [Fintype α] {K L : Kernel α} (h : K.SameJumpChain L) (g : α → ℝ) (x : α) :
        K.apply g x = g x ↔ L.apply g x = g x

        Kernels with the same jump chain have the same harmonic functions, state by state.

        theorem Dynamics.Kernel.event_monotone_of_absorbing {α : Type u_1} [Fintype α] (K : Kernel α) {A : α → Prop} (hA : ∀ (a : α), A a → (K a).prob A = 1) (x : α) :
        Monotone fun (t : ℕ) => K.event A t x

        If A is absorbing, the probability of A at time t increases with t.

        theorem Dynamics.Kernel.apply_iSup_event {α : Type u_1} [Fintype α] (K : Kernel α) {A : α → Prop} (hA : ∀ (a : α), A a → (K a).prob A = 1) (x : α) :
        K.apply (fun (y : α) => ⨆ (t : ℕ), K.event A t y) x = ⨆ (t : ℕ), K.event A t x

        The absorption probability of an absorbing event is harmonic.

        theorem Dynamics.Kernel.event_le_of_harmonic {α : Type u_1} [Fintype α] (K : Kernel α) {A : α → Prop} {g : α → ℝ} (hg0 : ∀ (y : α), 0 ≤ g y) (hgA : ∀ (y : α), A y → 1 ≤ g y) (hg : ∀ (y : α), K.apply g y = g y) (t : ℕ) (x : α) :
        K.event A t x ≤ g x

        A nonnegative harmonic function that is at least 1 on A bounds the probability of A at every time.

        theorem Dynamics.Kernel.SameJumpChain.iSup_event_eq {α : Type u_1} [Fintype α] {K L : Kernel α} (h : K.SameJumpChain L) {A : α → Prop} (hK : ∀ (a : α), A a → (K a).prob A = 1) (hL : ∀ (a : α), A a → (L a).prob A = 1) (x : α) :
        ⨆ (t : ℕ), K.event A t x = ⨆ (t : ℕ), L.event A t x

        Same jump chain, same absorption probabilities. If K and L have the same jump chain and A is absorbing for both, then from every state the probability of absorption in A, the supremum of the probabilities of A at finite times, is the same for K and for L.

        Duality #

        theorem Dynamics.Kernel.expect_iterate_comm {β : Type u_2} {γ : Type u_3} [Fintype β] [Fintype γ] (L : Kernel β) (p : Distribution γ) (F : γ → β → ℝ) (t : ℕ) (y : β) :
        (p.expect fun (c : γ) => L.iterate t (F c) y) = L.iterate t (fun (b : β) => p.expect fun (c : γ) => F c b) y

        Expectations under L at time t commute with a finite average over a parameter.

        def Dynamics.Kernel.Dual {α : Type u_1} {β : Type u_2} [Fintype α] [Fintype β] (H : α → β → ℝ) (K : Kernel α) (L : Kernel β) :

        Duality (kind duality of the dictionary: "an exact identity between probabilities of one process and of a dual process ..."). K on α and L on β are dual with respect to H : α → β → ℝ when 𝔼_x[H(X₁, y)] = 𝔼_y[H(x, Y₁)] for all x and y; it then holds at every time (Dual.iterate).

        Equations
        Instances For
          theorem Dynamics.Kernel.Dual.iterate {α : Type u_1} {β : Type u_2} [Fintype α] [Fintype β] {H : α → β → ℝ} {K : Kernel α} {L : Kernel β} (h : Dual H K L) (t : ℕ) (x : α) (y : β) :
          K.iterate t (fun (a : α) => H a y) x = L.iterate t (H x) y

          One-step duality gives duality at every time: 𝔼_x[H(X_t, y)] = 𝔼_y[H(x, Y_t)].

          theorem Dynamics.Kernel.Dual.symm {α : Type u_1} {β : Type u_2} [Fintype α] [Fintype β] {H : α → β → ℝ} {K : Kernel α} {L : Kernel β} (h : Dual H K L) :
          Dual (fun (b : β) (a : α) => H a b) L K

          Duality is symmetric.

          Mean field #

          def Dynamics.Kernel.MeanField {α : Type u_1} [Fintype α] {ι : Type u_4} (K : Kernel α) (φ : α → ι → ℝ) (F : (ι → ℝ) → ι → ℝ) :

          Mean field (kind mean-field of the dictionary: "the expected one-step change ... coincides; the stochastic processes may differ"). The observables φ i of K follow the recursion F in expectation over one step: 𝔼_x[φ(X₁)] = F(φ(x)). Two chains with the same observables and map F have the same mean-field recursion.

          Equations
          • K.MeanField φ F = ∀ (x : α) (i : ι), K.apply (fun (a : α) => φ a i) x = F (φ x) i
          Instances For
            theorem Dynamics.Kernel.Lumps.meanField {α : Type u_1} {β : Type u_2} [Fintype α] [Fintype β] {ι : Type u_4} {f : α → β} {K : Kernel α} {L : Kernel β} (h : Lumps f K L) {φ : β → ι → ℝ} {F : (ι → ℝ) → ι → ℝ} (hL : L.MeanField φ F) :
            K.MeanField (fun (a : α) => φ (f a)) F

            A lumping transfers a mean-field map to the observables read through the lumping map.

            theorem Dynamics.Kernel.MeanField.iterate_id {α : Type u_1} [Fintype α] {ι : Type u_4} {K : Kernel α} {φ : α → ι → ℝ} (h : K.MeanField φ fun (u : ι → ℝ) => u) (t : ℕ) (x : α) (i : ι) :
            K.iterate t (fun (a : α) => φ a i) x = φ x i

            With the identity as mean-field map, every observable keeps its expectation at all times (it is a martingale).