Lemma lem:ineqs: tail transfer for a maximum #
Source lines 2426–2437. Let H_i be integer valued and let N_i, L_i be nonnegative random
variables with {H_i ≥ h_i} = {N_i ≥ 1} and {L_i ≥ 1} ⊆ {H_i ≥ h_i}. If E[N_i] → 0 then
P(H_i ≥ h_i) → 0; if L_i → ∞ in probability then P(H_i ≥ h_i) → 1.
The index runs along an arbitrary filter, and each i carries its own probability space (the
laws 𝒯^n of the paper). Expectations are lintegrals in ℝ≥0∞, so that a statement
E[N_i] → 0 cannot be satisfied by a junk value of an infinite expectation. "L_i → ∞ in
probability" means P(L_i ≤ K) → 0 for every K.
First half of Lemma lem:ineqs: if the expected witness count N_i(h_i) vanishes, the
upper-tail probability P(H_i ≥ h_i) vanishes (Markov's inequality).
Second half of Lemma lem:ineqs: if the lower witness count L_i(h_i) tends to infinity in
probability (here: P(L_i < 1) → 0 suffices, which follows from P(L_i ≤ K) → 0 for any
K ≥ 1), then P(H_i ≥ h_i) → 1.