Maximal tail bound (proof of Theorem 2)
ProvedAzumaWeightedSums.IteratedLog.max_tail_leconcentrationmartingalemaximal-inequalityp2o-batch-pfp1bp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let belong to class [G] with for all , let be a real sequence, , and suppose . With , for every ,
This is the bound that, in the proof of Theorem 2, "the Tchebycheff inequality and (2.3)" yield: a maximal Azuma–Hoeffding inequality for weighted sums of conditionally sub-Gaussian martingale differences. It is the probabilistic input to the Borel–Cantelli argument for Theorem 2.
Formalization Note The probability is the measure (in ) of the set where . The paper's printed proof of Theorem 2 writes the increment in the denominator of the corresponding exponent; Chebyshev's exponential inequality and (2.3) give the full sum of squared weights, which is what is stated here.
Preamble
import Mathlib import Definitions.Def_AzumaWeightedSums_IteratedLog_ClassG import Definitions.Def_AzumaWeightedSums_IteratedLog_WeightedSums open MeasureTheory ProbabilityTheory Filter Topology
Formal statement
namespace AzumaWeightedSums.IteratedLog
/-- The maximal tail bound that "the Tchebycheff inequality and (2.3)" give in the proof of
Theorem 2 of Azuma 1967 (pp. 362–363): under [G] with `τ(x_n) ≤ 1`, for every `n`, every
real sequence `(b_k)` with `Σ_{k=1}^n b_k² > 0` and every `λ ≥ 0`,
`P{S_n^* > λ} ≤ 8 exp(−λ² / (2 Σ_{k=1}^n b_k²))`. -/
theorem max_tail_le {Ω : Type*} {mΩ : MeasurableSpace Ω} {μ : Measure Ω}
[IsProbabilityMeasure μ] {ℱ : Filtration ℕ mΩ} {x : ℕ → Ω → ℝ}
(hx : IsCondSubgaussianOne μ ℱ x) (b : ℕ → ℝ) (n : ℕ) (hb : 0 < sqWeightSum b n)
(lam : ℝ) (hlam : 0 ≤ lam) :
μ {ω | lam < maxAbsWeightedSum b x n ω}
≤ ENNReal.ofReal (8 * Real.exp (-(lam ^ 2) / (2 * sqWeightSum b n))) := by sorry
end AzumaWeightedSums.IteratedLog
Source
Azuma, Weighted sums of certain dependent random variables, Tôhoku Math. J. 19 (1967), https://doi.org/10.2748/tmj/1178243286, pp. 362–363, proof of Theorem 2 ("using the Tchebycheff inequality and (2.3)")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.