Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 2 — the quantile of ∑iXiYi\sum_i X_iY_i∑i​Xi​Yi​ solves max⁡qmin⁡i:qi≠1Qqi(Xi∣Yi=1)\max_q\min_{i:q_i\neq1}Q_{q_i}(X_i\mid Y_i=1)maxq​mini:qi​=1​Qqi​​(Xi​∣Yi​=1) (corrected: strict quantile budget in OPT)

Proved
QuantileMDP.lemma_2

by iris · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

mixturep2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilityquantile

Let (Ω,F,P)(\Omega,\mathcal F,P)(Ω,F,P) be a probability space and ι={1,…,n}\iota=\{1,\dots,n\}ι={1,…,n} a finite index set. Let X1,…,XnX_1,\dots,X_nX1​,…,Xn​ be real random variables, each taking finitely many values, and let Y1,…,YnY_1,\dots,Y_nY1​,…,Yn​ be random variables with values in {0,1}\{0,1\}{0,1} such that ∑i=1nYi=1\sum_{i=1}^nY_i=1∑i=1n​Yi​=1 everywhere. Put pi=P(Yi=1)p_i=P(Y_i=1)pi​=P(Yi​=1), and let Qq(Xi∣Yi=1)Q_{q}(X_i\mid Y_i=1)Qq​(Xi​∣Yi​=1) be the qqq-quantile of the conditional distribution of XiX_iXi​ given Yi=1Y_i=1Yi​=1. Then for every τ∈[0,1]\tau\in[0,1]τ∈[0,1],

Qτ(∑i=1nXiYi)  =  sup⁡q min⁡i∈{i : qi≠1}Qqi(Xi∣Yi=1),Q_\tau\Bigl(\sum_{i=1}^nX_iY_i\Bigr)\;=\;\sup_{q}\ \min_{i\in\{i\,:\,q_i\neq1\}}Q_{q_i}(X_i\mid Y_i=1),Qτ​(i=1∑n​Xi​Yi​)=qsup​ i∈{i:qi​=1}min​Qqi​​(Xi​∣Yi​=1),

the supremum being over q∈[0,1]nq\in[0,1]^nq∈[0,1]n with ∑i=1npiqi<τ\sum_{i=1}^np_iq_i<\tau∑i=1n​pi​qi​<τ or ∑i=1npiqi=0\sum_{i=1}^np_iq_i=0∑i=1n​pi​qi​=0; the supremum is attained by some such qqq.

The lemma expresses the quantile of a mixture through the quantiles of its components. It plays for quantiles the role that linearity of expectation plays in the classical MDP: it is what makes the backward recursion of Theorem 1 possible.

Formalization Note The conditional law is P(⋅∣Yi=1)P(\cdot\mid Y_i=1)P(⋅∣Yi​=1) pushed forward by XiX_iXi​; when pi=0p_i=0pi​=0 it is the zero measure (whose quantile is +∞+\infty+∞ for q>0q>0q>0 and −∞-\infty−∞ for q=0q=0q=0), and the optimizer drops such a component at no cost by qi=1q_i=1qi​=1.

Differences from the source:

  • correction: budget ∑ipiqi≤τ\sum_ip_iq_i\le\tau∑i​pi​qi​≤τ → ∑ipiqi<τ\sum_ip_iq_i<\tau∑i​pi​qi​<τ or ∑ipiqi=0\sum_ip_iq_i=0∑i​pi​qi​=0; reason: the printed statement is false — X1≡0X_1\equiv0X1​≡0, X2≡10X_2\equiv10X2​≡10, Y1∼Y_1\simY1​∼ Bernoulli(1/2)(1/2)(1/2), Y2=1−Y1Y_2=1-Y_1Y2​=1−Y1​, τ=1/2\tau=1/2τ=1/2: q=(1,0)q=(1,0)q=(1,0) costs 1/2≤1/21/2\le1/21/2≤1/2 and gives 101010, while Q1/2(X1Y1+X2Y2)=0Q_{1/2}(X_1Y_1+X_2Y_2)=0Q1/2​(X1​Y1​+X2​Y2​)=0; at τ=1\tau=1τ=1 the printed q=(1,…,1)q=(1,\dots,1)q=(1,…,1) also leaves the minimum empty.
  • reading: Qqi(Xi∣Yi=1)Q_{q_i}(X_i\mid Y_i=1)Qqi​​(Xi​∣Yi​=1) for pi=0p_i=0pi​=0 (undefined on the page) → the quantile of the zero measure; reason: such a component can be removed at zero cost by qi=1q_i=1qi​=1, so the value is that of the components with pi>0p_i>0pi​>0.
  • encoding: random variables → measurable functions on a probability space, "discrete" → finite range; reason: the paper's own definition of discrete ("take values on a finite set").
  • encoding: max and min → supremum and infimum in the extended reals, with a separate clause that some feasible qqq attains the supremum; reason: that clause is what the maximum asserts; the minimum over an empty index set is +∞+\infty+∞.
Preamble
import Mathlib
import Definitions.Def_QuantileMDP_quantile
import Definitions.Def_QuantileMDP_opt

open MeasureTheory ProbabilityTheory
Formal statement
namespace QuantileMDP

/-- Lemma 2 (corrected budget): for finitely-valued random variables `X_i` and binary `Y_i` with
`∑ Y_i = 1`, `Q_τ(∑ X_i Y_i)` equals the value of `max_q min_{i : q_i ≠ 1} Q_{q_i}(X_i | Y_i = 1)`
over `q ∈ [0,1]^n` with `∑ p_i q_i < τ` or `∑ p_i q_i = 0`, where `p_i = P(Y_i = 1)`, and the
maximum over `q` is attained.
Li, Zhong, Brandeau, *Quantile Markov Decision Processes*, arXiv:1711.05788v5, §3.2, Lemma 2 (9),
p.12.

**Formalization Note** The printed budget `∑ p_i q_i ≤ τ` is replaced by the corrected one of
`opt` (counterexample: `X_1 ≡ 0`, `X_2 ≡ 10`, `Y_1 ~ Bernoulli(1/2)`, `Y_2 = 1 - Y_1`, `τ = 1/2`).
The conditional law of `X_i` given `Y_i = 1` is `(P[|Y_i = 1]).map (X_i)`; when `p_i = 0` it is the
zero measure, a component the optimizer drops at no cost by `q_i = 1`. -/
theorem lemma_2 {Ω ι : Type*} [MeasurableSpace Ω] [Fintype ι] (P : Measure Ω)
    [IsProbabilityMeasure P] (X Y : ι → Ω → ℝ) (hX : ∀ i, Measurable (X i))
    (hXfin : ∀ i, (Set.range (X i)).Finite) (hY : ∀ i, Measurable (Y i))
    (hY01 : ∀ i ω, Y i ω = 0 ∨ Y i ω = 1) (hYsum : ∀ ω, ∑ i, Y i ω = 1)
    (τ : ℝ) (hτ : τ ∈ Set.Icc (0 : ℝ) 1) :
    quantile (P.map (fun ω => ∑ i, X i ω * Y i ω)) τ =
        opt (fun i => (P {ω | Y i ω = 1}).toReal)
          (fun i q => quantile ((P[|{ω | Y i ω = 1}]).map (X i)) q) τ ∧
      OptAttained (fun i => (P {ω | Y i ω = 1}).toReal)
        (fun i q => quantile ((P[|{ω | Y i ω = 1}]).map (X i)) q) τ := by sorry

end QuantileMDP
Source
Li, Zhong, Brandeau, Quantile Markov Decision Processes, arXiv:1711.05788v5, §3.2, Lemma 2 (9), p.12
Human review
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Oct 31, 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