Documentation

Dynamics.Hitting

Facts about hitting probabilities #

General facts about K.hitProb B t a = P_a(T_B ≤ t) for an arbitrary finite Markov kernel K, proved by induction on t through the recursion of hitProb (hitProb_of_mem, hitProb_zero_of_not_mem, hitProb_succ_of_not_mem), without stopping times:

theorem Dynamics.Kernel.hitProb_nonneg {α : Type u_1} [Fintype α] (K : Kernel α) (B : α → Prop) (t : ℕ) (a : α) :
0 ≤ K.hitProb B t a

A hitting probability is nonnegative.

theorem Dynamics.Kernel.hitProb_le_one {α : Type u_1} [Fintype α] (K : Kernel α) (B : α → Prop) (t : ℕ) (a : α) :
K.hitProb B t a ≤ 1

A hitting probability is at most 1.

theorem Dynamics.Kernel.hitProb_mono {α : Type u_1} [Fintype α] (K : Kernel α) {B B' : α → Prop} (hB : ∀ (a : α), B a → B' a) (t : ℕ) (a : α) :
K.hitProb B t a ≤ K.hitProb B' t a

Hitting a larger set is more likely.

theorem Dynamics.Kernel.hitProb_le_hitProb_succ {α : Type u_1} [Fintype α] (K : Kernel α) (B : α → Prop) (s : ℕ) (a : α) :
K.hitProb B s a ≤ K.hitProb B (s + 1) a

Hitting probabilities grow with the time horizon (one step).

theorem Dynamics.Kernel.hitProb_mono_time {α : Type u_1} [Fintype α] (K : Kernel α) (B : α → Prop) {s t : ℕ} (h : s ≤ t) (a : α) :
K.hitProb B s a ≤ K.hitProb B t a

Hitting probabilities grow with the time horizon.

theorem Dynamics.Kernel.hitProb_sub_le_event {α : Type u_1} [Fintype α] (K : Kernel α) {B P : α → Prop} (habs : ∀ (a : α), P a → (K a).prob P = 1) {T : ℕ} {ε : ℝ} (hε : 0 ≤ ε) (hB : ∀ (b : α), B b → 1 - ε ≤ K.event P T b) (t : ℕ) (a : α) :
K.hitProb B t a - ε ≤ K.event P (t + T) a

Hit, then absorb. Let P be absorbing for K. If from every state of B the chain is in P after T steps with probability at least 1 - ε (ε ≥ 0), then from any state a it is in P at time t + T with probability at least P_a(T_B ≤ t) - ε.

theorem Dynamics.Kernel.event_amplify {α : Type u_1} [Fintype α] (K : Kernel α) {P : α → Prop} (habs : ∀ (a : α), P a → (K a).prob P = 1) {T₀ T₁ : ℕ} {ε δ : ℝ} (hε : 0 ≤ ε) (h₁ : ∀ (b : α), 1 - ε ≤ K.event P T₁ b) (a : α) (h₀ : 1 - δ ≤ K.event P T₀ a) :
1 - δ * ε ≤ K.event P (T₀ + T₁) a

Amplification. Let P be absorbing for K, and suppose that from every state the chain is in P after T₁ steps with probability at least 1 - ε (ε ≥ 0). If from a it is in P after T₀ steps with probability at least 1 - δ, then it is in P after T₀ + T₁ steps with probability at least 1 - δ ε.