Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

THEOREM 2 — a bounded sequence with conditional drift ≤ −u E|z_k| crosses level t with probability ≤ ((1−u)/(1+u))^t

Proved
VectorPayoffs.Convex.blackwell_theorem2

by mikedeng1 · Sep 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

maximal-inequalityp2o-batch-p200ap2o-gran-per-chapterp2o-plan-paperp2o-v1strong-lawsupermartingale

Let z1,z2,…z_1,z_2,\dotsz1​,z2​,… be real random variables on a probability space with ∣zk∣≤1|z_k|\le1∣zk​∣≤1 almost surely, and let 0<u<10<u<10<u<1. Suppose that for every k≥1k\ge1k≥1, almost surely,

E(zk∣z1,…,zk−1)≤−u E(∣zk∣∣z1,…,zk−1).E(z_k\mid z_1,\dots,z_{k-1})\le -u\,E(|z_k|\mid z_1,\dots,z_{k-1}).E(zk​∣z1​,…,zk−1​)≤−uE(∣zk​∣∣z1​,…,zk−1​).

Then for every real ttt,

Prob{z1+⋯+zk≥t for some k≥1}≤(1−u1+u)t.\mathrm{Prob}\{z_1+\dots+z_k\ge t\text{ for some }k\ge1\}\le\Big(\frac{1-u}{1+u}\Big)^t .Prob{z1​+⋯+zk​≥t for some k≥1}≤(1+u1−u​)t.

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 "−umax⁡(∣zk∣∣z1,…,zk−1)-u\max(|z_k|\mid z_1,\dots,z_{k-1})−umax(∣zk​∣∣z1​,…,zk−1​)" on the right of the hypothesis. The cited source (Blackwell 1954) and the proof use the conditional expectation E(∣zk∣∣⋅)E(|z_k|\mid\cdot)E(∣zk​∣∣⋅); 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 u<1u<1u<1 is added: for u≥1u\ge1u≥1 the base (1−u)/(1+u)(1-u)/(1+u)(1−u)/(1+u) is ≤0\le0≤0 and has no real ttt-th power (Lean's rpow would return a junk value). ∣zk∣≤1|z_k|\le1∣zk​∣≤1 is required almost surely. The zkz_kzk​ are measurable, and ttt is an arbitrary real (the bound is ≥1\ge1≥1 for t≤0t\le0t≤0).

Preamble
import Mathlib
import Definitions.Def_VectorPayoffs_Convex_Recursion

open MeasureTheory
Formal statement
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
Source
Blackwell, An analog of the minimax theorem for vector payoffs, Pacific J. Math. 6(1), 1956, p. 5, THEOREM 2 (quoted from Blackwell, On optimal systems, Ann. Math. Statist. 25, 1954)
Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me