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.
- Same chain on counts (
Kernel.Lumps f K L, kindsame-chain: "the same transition kernel, on configurations or, where stated, on counts"). From every statex, one step ofKobserved throughf(for instance the number of individuals of a type) is one step ofLfromf x. The lumping lifts to the law at every time,(K^t x).map f = L^t (f x)(Lumps.law, withKernel.lawthe law at timet), to expectations, events and path functionals (Lumps.iterate,Lumps.event,Lumps.trajectory), so fixation, consensus and hitting probabilities ofKread throughfare those ofL(Lumps.event,Lumps.hitProb). - Same jump chain (
Kernel.jump,Kernel.SameJumpChain, kindjump-chain: "the same chain once idle steps are removed ...; the processes differ by a random time change, so absorption probabilities agree but running times need not"). The jump chain ofKis its step conditioned on moving; a state thatKnever leaves stays absorbing. Kernels whose rows are proportional off the diagonal have the same jump chain (sameJumpChain_of_weight); a lazy version is an example (lazy_sameJumpChain). Kernels with the same jump chain have the same harmonic functions (SameJumpChain.apply_eq_self_iff) and the same absorption probabilities (SameJumpChain.iSup_event_eq). - Duality (
Kernel.Dual H K L, kindduality: "an exact identity between probabilities of one process and of a dual process ..."):E_x[H(X_t, y)] = E_y[H(x, Y_t)], which follows for everytfrom the case of one step (Dual.iterate). - Mean field (
Kernel.MeanField K φ F, kindmean-field: "the expected one-step change ... coincides; the stochastic processes may differ"): the expected one-step map of the observablesφis the recursionF,E_x[φ(X₁)] = F(φ(x)). A lumping transfers it (Lumps.meanField).
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.
Distributions with the same weights are equal.
The weight of a point is the expectation of its indicator.
Distributions with the same expectations are equal.
Fubini's theorem for two finite distributions.
Laws at finite times #
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 #
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
- Dynamics.Kernel.Lumps f K L = ∀ (x : α), (K x).map f = L (f x)
Instances For
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).
Same jump chain #
The weights of the states other than x add up to 1 - K(x, x).
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
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).
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.
A lazy version has the same jump chain: its idle steps are removed.
A nonnegative harmonic function that is at least 1 on A bounds the probability of A at
every time.
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 #
Expectations under L at time t commute with a finite average over a parameter.
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
- Dynamics.Kernel.Dual H K L = ∀ (x : α) (y : β), K.apply (fun (a : α) => H a y) x = L.apply (H x) y
Instances For
Mean field #
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.
Instances For
A lumping transfers a mean-field map to the observables read through the lumping map.