THEOREM 2 — a bounded sequence with conditional drift ≤ −u E|z_k| crosses level t with probability ≤ ((1−u)/(1+u))^t
ProvedVectorPayoffs.Convex.blackwell_theorem2Let be real random variables on a probability space with almost surely, and let . Suppose that for every , almost surely,
Then for every real ,
This is the form of the strong law of large numbers that Blackwell quotes from his earlier paper and applies, in the proof of the LEMMA, to the rescaled increments of the approach process.
Formalization Note The page prints "" on the right of the hypothesis. The cited source (Blackwell 1954) and the proof use the conditional expectation ; since this is at most any conditional maximum, the hypothesis stated here is the weaker one and the theorem the stronger one, and the paper's derivation of (8) delivers it. The bound is added: for the base is and has no real -th power (Lean's rpow would return a junk value). is required almost surely. The are measurable, and is an arbitrary real (the bound is for ).
import Mathlib import Definitions.Def_VectorPayoffs_Convex_Recursion open MeasureTheory
namespace VectorPayoffs.Convex
/-- Blackwell (1956), §2, p. 5, THEOREM 2 (conditional expectation form of the drift
hypothesis; see the natural-language statement for the printed "max"). -/
theorem blackwell_theorem2 {Ω : Type} [MeasurableSpace Ω] (μ : Measure Ω)
[IsProbabilityMeasure μ] (z : ℕ → Ω → ℝ) (u : ℝ) (hu : 0 < u) (hu1 : u < 1)
(hmeas : ∀ k, 1 ≤ k → Measurable (z k))
(hbound : ∀ k, 1 ≤ k → ∀ᵐ ω ∂μ, |z k ω| ≤ 1)
(hdrift : ∀ k, 1 ≤ k →
μ[z k | pastSigma z (k - 1)] ≤ᵐ[μ] (-u) • μ[fun ω => |z k ω| | pastSigma z (k - 1)])
(t : ℝ) :
μ {ω | ∃ k, 1 ≤ k ∧ t ≤ ∑ i ∈ Finset.Icc 1 k, z i ω} ≤
ENNReal.ofReal (((1 - u) / (1 + u)) ^ t) := by sorry
end VectorPayoffs.Convex
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.