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:
hitProb_nonneg,hitProb_le_one: hitting probabilities are probabilities;hitProb_mono,hitProb_mono_time: they grow with the target set and with the time horizon;hitProb_sub_le_event(hit, then absorb): if from every state ofBthe chain is in an absorbing eventPafterTsteps with probability at least1 - ε, andBis hit withintsteps with probabilityh, then the chain is inPat timet + Twith probability at leasth - ε. This is the strong Markov property at the hitting time ofB;event_amplify(amplification): if an absorbing event is reached withinT₁steps with probability at least1 - εfrom every state, then a first block ofT₀steps that fails with probability at mostδis followed by a block that fails with probability at mostε, so both fail with probability at mostδ ε.
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) - ε.
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 - δ ε.