Documentation

Dynamics.Lazy

Lazy kernels #

The lazy version (I + K)/2 of a finite kernel K stays put with probability 1/2 and otherwise moves according to K (Kernel.lazy). It charges every self-loop with weight at least 1/2 (lazy_weight_self_ge_half), charges everything K charges (lazy_weight_pos) and has the same stationary distributions as K (lazy_stationary_iff). Laziness is the standard way to make a walk aperiodic, e.g. the lazy random walk (I + D⁻¹A)/2 on a graph (Kernel.lazyNeighbor in Dynamics/RandomWalk.lean).

noncomputable def Dynamics.Kernel.lazy {V : Type u_1} [Fintype V] [DecidableEq V] (K : Kernel V) :

The lazy version (I + K)/2 of a kernel: stay with probability 1/2, otherwise move according to K.

Equations
Instances For
    theorem Dynamics.Kernel.lazy_weight {V : Type u_1} [Fintype V] [DecidableEq V] (K : Kernel V) (i j : V) :
    (K.lazy i).weight j = ((if i = j then 1 else 0) + (K i).weight j) / 2

    Entries of the lazy kernel: (I + K)/2.

    theorem Dynamics.Kernel.lazy_expect {V : Type u_1} [Fintype V] [DecidableEq V] (K : Kernel V) (x : V) (f : V → ℝ) :
    (K.lazy x).expect f = f x / 2 + (K x).expect f / 2

    Expectation under the lazy kernel: half the current value plus half the K-expectation.

    Laziness does not change stationary distributions: p (I + K)/2 = p ↔ p K = p.

    theorem Dynamics.Kernel.lazy_weight_self_ge_half {V : Type u_1} [Fintype V] [DecidableEq V] (K : Kernel V) (v : V) :
    1 / 2 ≤ (K.lazy v).weight v

    The lazy kernel charges every self-loop with weight at least 1/2.

    theorem Dynamics.Kernel.lazy_selfLoop_pos {V : Type u_1} [Fintype V] [DecidableEq V] (K : Kernel V) (v : V) :
    0 < (K.lazy v).weight v

    The lazy kernel charges every self-loop.

    theorem Dynamics.Kernel.lazy_weight_pos {V : Type u_1} [Fintype V] [DecidableEq V] (K : Kernel V) {i j : V} (h : 0 < (K i).weight j) :
    0 < (K.lazy i).weight j

    The lazy kernel charges everything K charges.