Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5 — Uniform downward passage expectation

Proved
MatchingWhileLearning.DEEM.lemma_5

by Shuze Chen · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

bandit-algorithmsoperations-researchp2o-gran-per-chapterp2o-plan-paperp2o-v1probability

Fix a positive integer VVV, a bound M>0M>0M>0, and positive means m(j)m^{(j)}m(j) for j=1,…,Vj=1,\ldots,Vj=1,…,V. There exists a finite nonnegative constant Z=Z(V,M,(m(j)))Z=Z(V,M,(m^{(j)}))Z=Z(V,M,(m(j))) such that the following holds on every probability space. Take 0<b‾<b‾0<\underline b<\overline b0<b​<b, starts k(j)∈(b‾,b‾)k^{(j)}\in(\underline b,\overline b)k(j)∈(b​,b), and real-valued increments IID along time for each walk, with mean m(j)m^{(j)}m(j) and absolute value at most MMM. No independence between walks is required. Set Sn(j)=k(j)+∑s=1nXs(j)S_n^{(j)}=k^{(j)}+\sum_{s=1}^n X_s^{(j)}Sn(j)​=k(j)+∑s=1n​Xs(j)​ and T=inf⁡{n:min⁡jSn(j)<b‾}T=\inf\{n:\min_j S_n^{(j)}<\underline b\}T=inf{n:minj​Sn(j)​<b​}. Then

E[T1{T<∞}]≤Z.\mathbb E[T\mathbf1_{\{T<\infty\}}]\le Z.E[T1{T<∞}​]≤Z.

The same ZZZ works for every barrier, start, and admissible step law with the fixed means and bound.

Differences from the source:

  • encoding: random variables and their expectations → measurable functions on a probability space, IID within each walk, almost-sure bounds and prescribed integrals; reason: these are the usual random-variable conventions and boundedness supplies integrability
  • encoding: T times the indicator of finite passage → extended-natural first-hit time and a nonnegative integral equal to T on finite-hit paths and zero otherwise; reason: this is the source random variable and avoids the zero default of a nonintegrable real integral
  • encoding: walks and increments indexed starting at one → walks indexed by Fin V and increments by naturals starting at zero; reason: only the labels of the first V walks and first n increments change
Preamble
import Definitions.Def_MatchingWhileLearning_DEEM_Stopping

open scoped BigOperators ENNReal
open Filter MeasureTheory ProbabilityTheory
open MatchingWhileLearning.DEEM
Formal statement
namespace MatchingWhileLearning.DEEM

theorem lemma_5 (V : ℕ) (hV : 0 < V) (M : ℝ) (hM : 0 < M)
    (means : Fin V → ℝ) (hm : ∀ j, 0 < means j) :
    ∃ Z : ℝ, 0 ≤ Z ∧ ∀ (Ω : Type) [MeasurableSpace Ω] (P : Measure Ω),
      IsProbabilityMeasure P → ∀ (lower upper : ℝ) (start : Fin V → ℝ),
      0 < lower → lower < upper → (∀ j, start j ∈ Set.Ioo lower upper) →
      ∀ X : Fin V → ℕ → Ω → ℝ,
      (∀ j n, Measurable (X j n)) →
      (∀ j, iIndepFun (X j) P) →
      (∀ j n, IdentDistrib (X j n) (X j 0) P P) →
      (∀ j n, ∀ᵐ ω ∂P, |X j n ω| ≤ M) →
      (∀ j n, ∫ ω, X j n ω ∂P = means j) →
      finiteHitExpectation P X start lower ≤ ENNReal.ofReal Z := by sorry

end MatchingWhileLearning.DEEM
Source
Johari, Kamble, Kanoria, Matching While Learning, arXiv:1603.04549v7, https://arxiv.org/abs/1603.04549v7, Lemma 5, p. 58 (PDF p. 58)
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

This statement does not involve the matching model; the letter MMM here is a real number.

Data.

  • V∈NV\in\mathbb NV∈N with V>0V>0V>0.
  • A real M>0M>0M>0.
  • Reals μ0,…,μV−1\mu_0,\dots,\mu_{V-1}μ0​,…,μV−1​ with every μj>0\mu_j>0μj​>0.

Assertion. There exists a real Z≥0Z\ge0Z≥0, depending only on (V,M,μ)(V,M,\mu)(V,M,μ), such that the following holds for:

  • every measurable space Ω\OmegaΩ and every probability measure PPP on it;
  • all reals 0<ℓ<u0<\ell<u0<ℓ<u;
  • all starting points sj∈(ℓ,u)s_j\in(\ell,u)sj​∈(ℓ,u) (open interval);
  • all real processes Xj(n,ω)X_j(n,\omega)Xj​(n,ω), j<Vj<Vj<V, n∈Nn\in\mathbb Nn∈N, satisfying:
    • each Xj(n)X_j(n)Xj​(n) is measurable;
    • for each fixed jjj, the family (Xj(n))n∈N(X_j(n))_{n\in\mathbb N}(Xj​(n))n∈N​ is mutually independent under PPP (nothing is assumed across different jjj);
    • each Xj(n)X_j(n)Xj​(n) has the same law as Xj(0)X_j(0)Xj​(0);
    • ∣Xj(n)∣≤M|X_j(n)|\le M∣Xj​(n)∣≤M almost surely;
    • E[Xj(n)]=μj\mathbb E[X_j(n)]=\mu_jE[Xj​(n)]=μj​.

Then

∫ΩT(ω) 1[T(ω)<∞] dP(ω) ≤ Z,\int_\Omega T(\omega)\,\mathbf 1[T(\omega)<\infty]\,dP(\omega)\ \le\ Z,∫Ω​T(ω)1[T(ω)<∞]dP(ω) ≤ Z,

where

T(ω)=inf⁡{n∈N: ∃j<V, sj+∑k<nXj(k,ω)<ℓ}T(\omega)=\inf\Big\{n\in\mathbb N:\ \exists j<V,\ s_j+\sum_{k<n}X_j(k,\omega)<\ell\Big\}T(ω)=inf{n∈N: ∃j<V, sj​+k<n∑​Xj​(k,ω)<ℓ}

is the first time any one walk is below ℓ\ellℓ, with T=∞T=\inftyT=∞ if never. Paths with T=∞T=\inftyT=∞ contribute 000.

The bound ZZZ is uniform over Ω\OmegaΩ, PPP, ℓ\ellℓ, uuu, sss, and the laws of the XjX_jXj​ subject to the listed constraints.

Degenerate cases.

  • V=0V=0V=0 is excluded.
  • T≥1T\ge1T≥1 always, since every sj>ℓs_j>\ellsj​>ℓ.
  • The upper level uuu enters only through sj<us_j<usj​<u.
  • Ω\OmegaΩ ranges over types in the base universe.
Human review
  • Endorsed by Community (Bot) · Oct 29, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Oct 29, 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