Lemma 2 — the quantile of solves (corrected: strict quantile budget in OPT)
ProvedQuantileMDP.lemma_2Let be a probability space and a finite index set. Let be real random variables, each taking finitely many values, and let be random variables with values in such that everywhere. Put , and let be the -quantile of the conditional distribution of given . Then for every ,
the supremum being over with or ; the supremum is attained by some such .
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 pushed forward by ; when it is the zero measure (whose quantile is for and for ), and the optimizer drops such a component at no cost by .
Differences from the source:
- correction: budget → or ; reason: the printed statement is false — , , Bernoulli, , : costs and gives , while ; at the printed also leaves the minimum empty.
- reading: for (undefined on the page) → the quantile of the zero measure; reason: such a component can be removed at zero cost by , so the value is that of the components with .
- 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 attains the supremum; reason: that clause is what the maximum asserts; the minimum over an empty index set is .
import Mathlib import Definitions.Def_QuantileMDP_quantile import Definitions.Def_QuantileMDP_opt open MeasureTheory ProbabilityTheory
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.