Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2.7 — smallest-superharmonic-majorant criterion

Disproved
PeskirShiryaev.General.sufficient_majorant

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

optimal-stoppingp2o-gran-per-chapterp2o-plan-bookp2o-v1probabilitysuperharmonic-functions

Let XXX satisfy the strong Markov and regularity assumptions of Section 2.2 on E=RdE=\mathbb R^dE=Rd, d≥1d\ge1d≥1. Let G:E→RG:E\to\mathbb RG:E→R be measurable with Exsup⁡t≥0∣G(Xt)∣<∞E_x\sup_{t\ge0}|G(X_t)|<\inftyEx​supt≥0​∣G(Xt​)∣<∞ for all xxx. Define V(x)=sup⁡τExG(Xτ)V(x)=\sup_\tau E_xG(X_\tau)V(x)=supτ​Ex​G(Xτ​) over stopping times finite almost surely at the initial state. Suppose the smallest superharmonic majorant V^\widehat VV of GGG exists, is lower semicontinuous, and GGG is upper semicontinuous. Let

D={x:V^(x)=G(x)},τD=inf⁡{t≥0:Xt∈D}.D=\{x:\widehat V(x)=G(x)\},\qquad \tau_D=\inf\{t\ge0:X_t\in D\}.D={x:V(x)=G(x)},τD​=inf{t≥0:Xt​∈D}.

The entry time is a Markov time. If Px(τD<∞)=1P_x(\tau_D<\infty)=1Px​(τD​<∞)=1 for every xxx, then

V^=V,ExG(XτD)=V(x)(x∈E),\widehat V=V,\qquad E_xG(X_{\tau_D})=V(x)\quad(x\in E),V=V,Ex​G(XτD​​)=V(x)(x∈E),

and τD\tau_DτD​ is optimal. If Px(τD<∞)<1P_x(\tau_D<\infty)<1Px​(τD​<∞)<1 for some xxx, there is no almost-surely finite stopping rule optimal at every initial state.

This is the sufficient majorant criterion for existence, including its nonexistence alternative.

Formalization Note This item is the infinite-horizon Theorem 2.7 itself. The candidate majorant and the expected-reward value are separate objects, and equality is a conclusion. The nonexistence clause negates a common optimal rule for all initial states, matching the global convention of (2.2.9). Empty contact sets yield infinity. The finite-horizon extension in Remark 2.8 and Corollary 2.9 is outside this mission's scope.

Preamble
import Definitions.Def_PeskirShiryaev_General_StoppingProblem

open MeasureTheory ProbabilityTheory Filter Set
open scoped NNReal ENNReal Topology
Formal statement
/- Imported Lean declarations, reproduced for self-contained code review:
namespace PeskirShiryaev.General

abbrev State (d : ℕ) := Fin d → ℝ


def RightContinuousPaths {Ω A : Type*} [TopologicalSpace A]
    (Y : ℝ≥0 → Ω → A) (ω : Ω) : Prop :=
  ∀ t, ContinuousWithinAt (fun s => Y s ω) (Ici t) t


structure MarkovModel (d : ℕ) (Ω : Type*) [mΩ : MeasurableSpace Ω] where
  dimension_pos : 0 < d
  P : State d → Measure Ω
  probability : ∀ x, IsProbabilityMeasure (P x)
  measurable_laws : ∀ A : Set Ω, MeasurableSet A → Measurable (fun x => P x A)
  filtration : Filtration ℝ≥0 mΩ
  filtration_rightContinuous : filtration.IsRightContinuous
  X : ℝ≥0 → Ω → State d
  adapted : Adapted filtration X
  starts : ∀ x, ∀ᵐ ω ∂P x, X 0 ω = x
  rightContinuous : ∀ ω, RightContinuousPaths X ω
  strongMarkov : ∀ (x : State d) (τ : Ω → ℝ≥0∞)
    (hτ : IsStoppingTime filtration τ),
    (∀ᵐ ω ∂P x, τ ω < ⊤) →
    ∀ (s : ℝ≥0) (f : State d → ℝ), Measurable f →
      Bornology.IsBounded (Set.range f) →
      (P x)[fun ω => f (X ((τ ω).toNNReal + s) ω) | hτ.measurableSpace]
        =ᵐ[P x] (fun ω => ∫ ω', f (X s ω') ∂P (X (τ ω).toNNReal ω))
  leftContinuous_stopping : ∀ (x : State d) (τ : Ω → ℝ≥0∞)
    (τn : ℕ → Ω → ℝ≥0∞),
    IsStoppingTime filtration τ →
    (∀ n, IsStoppingTime filtration (τn n)) →
    (∀ ω, Monotone (fun n => τn n ω)) →
    (∀ᵐ ω ∂P x, Tendsto (fun n => τn n ω) atTop (𝓝 (τ ω))) →
    ∀ᵐ ω ∂P x, τ ω < ⊤ →
      Tendsto (fun n => X (τn n ω).toNNReal ω) atTop (𝓝 (X (τ ω).toNNReal ω))

end PeskirShiryaev.General

namespace PeskirShiryaev.General

variable {d : ℕ} {Ω : Type*} [MeasurableSpace Ω]


def Admissible (M : MarkovModel d Ω) (x : State d) (τ : Ω → ℝ≥0∞) : Prop :=
  IsStoppingTime M.filtration τ ∧ ∀ᵐ ω ∂M.P x, τ ω < ⊤


noncomputable def gainSup (M : MarkovModel d Ω) (G : State d → ℝ) (ω : Ω) : ℝ≥0∞ :=
  ⨆ t : ℝ≥0, ENNReal.ofReal |G (M.X t ω)|

def GainIntegrable (M : MarkovModel d Ω) (G : State d → ℝ) : Prop :=
  Measurable G ∧ ∀ x, AEMeasurable (gainSup M G) (M.P x) ∧
    (∫⁻ ω, gainSup M G ω ∂M.P x) < ⊤


noncomputable def reward (M : MarkovModel d Ω) (G : State d → ℝ)
    (τ : Ω → ℝ≥0∞) (ω : Ω) : ℝ :=
  if τ ω = ⊤ then 0 else G (M.X (τ ω).toNNReal ω)


noncomputable def value (M : MarkovModel d Ω) (G : State d → ℝ) (x : State d) : ℝ :=
  sSup {r : ℝ | ∃ τ : Ω → ℝ≥0∞, Admissible M x τ ∧ r = ∫ ω, reward M G τ ω ∂M.P x}

def Optimal (M : MarkovModel d Ω) (G : State d → ℝ) (τ : Ω → ℝ≥0∞) : Prop :=
  ∀ x, Admissible M x τ ∧ Integrable (reward M G τ) (M.P x) ∧
    (∫ ω, reward M G τ ω ∂M.P x) = value M G x


def Superharmonic (M : MarkovModel d Ω) (F : State d → ℝ) : Prop :=
  Measurable F ∧ ∀ (x : State d) (σ : Ω → ℝ≥0∞), Admissible M x σ →
    Integrable (reward M F σ) (M.P x) ∧ (∫ ω, reward M F σ ω ∂M.P x) ≤ F x

def LeastMajorant (M : MarkovModel d Ω) (G F : State d → ℝ) : Prop :=
  Superharmonic M F ∧ (∀ x, G x ≤ F x) ∧
    ∀ H : State d → ℝ, Superharmonic M H → (∀ x, G x ≤ H x) → ∀ x, F x ≤ H x


noncomputable def entryTime (M : MarkovModel d Ω) (D : Set (State d)) (ω : Ω) : ℝ≥0∞ :=
  ⨅ t : {t : ℝ≥0 // M.X t ω ∈ D}, (t.val : ℝ≥0∞)

noncomputable def contactTime (M : MarkovModel d Ω) (G F : State d → ℝ) : Ω → ℝ≥0∞ :=
  entryTime M {x | F x = G x}

noncomputable def stoppedValue (M : MarkovModel d Ω) (F : State d → ℝ)
    (τ : Ω → ℝ≥0∞) (t : ℝ≥0) (ω : Ω) : ℝ :=
  F (M.X (min (t : ℝ≥0∞) (τ ω)).toNNReal ω)

end PeskirShiryaev.General
-/

namespace PeskirShiryaev.General

theorem sufficient_majorant {d : ℕ} {Ω : Type*} [MeasurableSpace Ω]
    (M : MarkovModel d Ω) (G Vhat : State d → ℝ) (hG : GainIntegrable M G)
    (hmajorant : LeastMajorant M G Vhat)
    (hlsc : LowerSemicontinuous Vhat) (husc : UpperSemicontinuous G) :
    IsStoppingTime M.filtration (contactTime M G Vhat) ∧
    (((∀ x, ∀ᵐ ω ∂M.P x, contactTime M G Vhat ω < ⊤) →
      Vhat = value M G ∧ Optimal M G (contactTime M G Vhat)) ∧
    ((∃ x, M.P x {ω | contactTime M G Vhat ω < ⊤} < 1) →
      ¬ ∃ τ : Ω → ℝ≥0∞, Optimal M G τ)) := by sorry

end PeskirShiryaev.General
Source
Peskir and Shiryaev, Optimal Stopping and Free-Boundary Problems, Birkhäuser Verlag, 2006, DOI 10.1007/978-3-7643-7390-0, pp. 40–41 (PDF 60–61), Theorem 2.7, Eqs. (2.2.27)–(2.2.28); standing assumptions pp. 34–35.
Read-back

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

Setting. Fix a natural number ddd, a measurable space (Ω,F)(\Omega,\mathcal F)(Ω,F), and a "Markov model" MMM on Ω\OmegaΩ with state space Rd\mathbb R^dRd (functions {0,…,d−1}→R\{0,\dots,d-1\}\to\mathbb R{0,…,d−1}→R, with the product topology). The model consists of the following data and requirements:

  • d>0d>0d>0.
  • A family of probability measures (Px)x∈Rd(P_x)_{x\in\mathbb R^d}(Px​)x∈Rd​ on Ω\OmegaΩ, such that x↦Px(A)x\mapsto P_x(A)x↦Px​(A) is measurable for every measurable A⊆ΩA\subseteq\OmegaA⊆Ω.
  • A filtration (Ft)t≥0(\mathcal F_t)_{t\ge 0}(Ft​)t≥0​ indexed by t∈[0,∞)t\in[0,\infty)t∈[0,∞), contained in F\mathcal FF and right-continuous.
  • A process Xt:Ω→RdX_t:\Omega\to\mathbb R^dXt​:Ω→Rd for t≥0t\ge 0t≥0, adapted to (Ft)(\mathcal F_t)(Ft​).
  • X0=xX_0=xX0​=x holds PxP_xPx​-almost surely for every xxx.
  • For every ω\omegaω, the path t↦Xt(ω)t\mapsto X_t(\omega)t↦Xt​(ω) is right-continuous at every ttt.
  • Strong Markov property. Take any xxx, any [0,∞][0,\infty][0,∞]-valued (Ft)(\mathcal F_t)(Ft​)-stopping time τ\tauτ with τ<∞\tau<\inftyτ<∞ PxP_xPx​-a.s., any s≥0s\ge 0s≥0, and any measurable bounded f:Rd→Rf:\mathbb R^d\to\mathbb Rf:Rd→R. Then PxP_xPx​-a.s.
Ex[f(Xτ+s)∣Fτ](ω)=∫f(Xs(ω′)) PXτ(ω)(ω)(dω′).E_x\big[f(X_{\tau+s})\mid\mathcal F_\tau\big](\omega)=\int f(X_s(\omega'))\,P_{X_{\tau(\omega)}(\omega)}(d\omega').Ex​[f(Xτ+s​)∣Fτ​](ω)=∫f(Xs​(ω′))PXτ(ω)​(ω)​(dω′).

Here "XτX_\tauXτ​" means XXX evaluated at τ(ω)\tau(\omega)τ(ω) converted to a finite time, with the convention that τ(ω)=∞\tau(\omega)=\inftyτ(ω)=∞ is converted to time 000.

  • Left-continuity along stopping times. Take any xxx, any stopping time τ\tauτ, and any stopping times τn\tau_nτn​ such that n↦τn(ω)n\mapsto\tau_n(\omega)n↦τn​(ω) is nondecreasing for every ω\omegaω and τn→τ\tau_n\to\tauτn​→τ PxP_xPx​-a.s. Then PxP_xPx​-a.s. on {τ<∞}\{\tau<\infty\}{τ<∞} we have Xτn→XτX_{\tau_n}\to X_\tauXτn​​→Xτ​, with the same convention that an infinite time is read as 000.

Auxiliary notions.

  • A map τ:Ω→[0,∞]\tau:\Omega\to[0,\infty]τ:Ω→[0,∞] is admissible at xxx if it is an (Ft)(\mathcal F_t)(Ft​)-stopping time and τ<∞\tau<\inftyτ<∞ PxP_xPx​-a.s.
  • For F:Rd→RF:\mathbb R^d\to\mathbb RF:Rd→R, the reward of τ\tauτ is RFτ(ω)=F(Xτ(ω)(ω))R_F^\tau(\omega)=F(X_{\tau(\omega)}(\omega))RFτ​(ω)=F(Xτ(ω)​(ω)) if τ(ω)<∞\tau(\omega)<\inftyτ(ω)<∞, and RFτ(ω)=0R_F^\tau(\omega)=0RFτ​(ω)=0 if τ(ω)=∞\tau(\omega)=\inftyτ(ω)=∞.
  • The value is
V(x)=sup⁡{∫RGτ dPx  :  τ admissible at x}.V(x)=\sup\Big\{\textstyle\int R_G^\tau\,dP_x \;:\; \tau \text{ admissible at } x\Big\}.V(x)=sup{∫RGτ​dPx​:τ admissible at x}.

This is the supremum in R\mathbb RR, which by convention equals 000 if the set is unbounded above or empty. Each integral is the Lebesgue (Bochner) integral, which by convention equals 000 when RGτR_G^\tauRGτ​ is not PxP_xPx​-integrable.

  • FFF is superharmonic if FFF is measurable and, for every xxx and every σ\sigmaσ admissible at xxx, RFσR_F^\sigmaRFσ​ is PxP_xPx​-integrable with ∫RFσ dPx≤F(x)\int R_F^\sigma\,dP_x\le F(x)∫RFσ​dPx​≤F(x).
  • A stopping time τ\tauτ is optimal if, for every xxx, it is admissible at xxx, RGτR_G^\tauRGτ​ is PxP_xPx​-integrable, and ∫RGτ dPx=V(x)\int R_G^\tau\,dP_x=V(x)∫RGτ​dPx​=V(x).
  • For D={y∈Rd:V^(y)=G(y)}D=\{y\in\mathbb R^d:\hat V(y)=G(y)\}D={y∈Rd:V^(y)=G(y)}, the contact time is
τD(ω)=inf⁡{t≥0:Xt(ω)∈D}∈[0,∞].\tau_D(\omega)=\inf\{t\ge 0: X_t(\omega)\in D\}\in[0,\infty].τD​(ω)=inf{t≥0:Xt​(ω)∈D}∈[0,∞].

The infimum is taken in [0,∞][0,\infty][0,∞], so it equals ∞\infty∞ when the path never enters DDD, and it need not be attained.

Hypotheses. Let G,V^:Rd→RG,\hat V:\mathbb R^d\to\mathbb RG,V^:Rd→R, and assume:

  1. GGG is measurable, and for every xxx the function ω↦sup⁡t≥0∣G(Xt(ω))∣∈[0,∞]\omega\mapsto\sup_{t\ge 0}|G(X_t(\omega))|\in[0,\infty]ω↦supt≥0​∣G(Xt​(ω))∣∈[0,∞] is PxP_xPx​-a.e. measurable with finite PxP_xPx​-expectation.
  2. V^\hat VV^ is superharmonic and G≤V^G\le\hat VG≤V^ pointwise.
  3. Every superharmonic H:Rd→RH:\mathbb R^d\to\mathbb RH:Rd→R with G≤HG\le HG≤H pointwise satisfies V^≤H\hat V\le HV^≤H pointwise.
  4. V^\hat VV^ is lower semicontinuous and GGG is upper semicontinuous.

Conclusion. Three statements hold together:

  • (a) τD\tau_DτD​ is an (Ft)(\mathcal F_t)(Ft​)-stopping time, meaning {τD≤t}∈Ft\{\tau_D\le t\}\in\mathcal F_t{τD​≤t}∈Ft​ for all t≥0t\ge0t≥0.
  • (b) If τD<∞\tau_D<\inftyτD​<∞ PxP_xPx​-a.s. for every xxx, then V^(x)=V(x)\hat V(x)=V(x)V^(x)=V(x) for all xxx, and τD\tau_DτD​ is optimal in the sense above.
  • (c) If there is some xxx with Px({τD<∞})<1P_x(\{\tau_D<\infty\})<1Px​({τD​<∞})<1, then no optimal stopping time exists. That is, there is no τ:Ω→[0,∞]\tau:\Omega\to[0,\infty]τ:Ω→[0,∞] that is admissible at every xxx, has PxP_xPx​-integrable reward for every xxx, and attains V(x)V(x)V(x) for every xxx.

Part (b) is an implication, not an equivalence, and part (c) asserts only the non-existence of a stopping time that is optimal at all starting points simultaneously.

Degenerate cases.

  • d=0d=0d=0 is excluded by the model, so the state space is Rd\mathbb R^dRd with d≥1d\ge1d≥1.
  • No model exists when Ω\OmegaΩ is empty, since probability measures are required. No model exists when Ω\OmegaΩ is a single point either: X0=xX_0=xX0​=x PxP_xPx​-a.s. for every xxx would force one point to equal every xxx. The model's hypotheses are therefore satisfiable only on richer Ω\OmegaΩ.
  • If DDD is empty, or a path never enters DDD, then τD=∞\tau_D=\inftyτD​=∞ there. If DDD is empty, every Px(τD<∞)=0<1P_x(\tau_D<\infty)=0<1Px​(τD​<∞)=0<1, so the hypothesis of (b) fails and (c) asserts that no optimal stopping time exists.
  • On {τ=∞}\{\tau=\infty\}{τ=∞}:
    • the reward is defined to be 000, not a limit of G(Xt)G(X_t)G(Xt​);
    • in the strong Markov and left-continuity axioms, XτX_\tauXτ​ silently means X0X_0X0​.
  • τD=0\tau_D=0τD​=0 wherever X0∈DX_0\in DX0​∈D.
  • The value V(x)V(x)V(x) uses the real-supremum convention: it would be 000 if the set of expected rewards were unbounded above. The set is nonempty, because the constant time 000 is admissible.
  • An expected reward is taken as 000 whenever the reward is not integrable or not measurable.
  • Px({τD<∞})P_x(\{\tau_D<\infty\})Px​({τD​<∞}) is the measure (outer measure, if non-measurable) of that set.
  • The "pointwise" inequalities and the semicontinuity requirements are imposed at every point of Rd\mathbb R^dRd, including points the process may never visit.
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