Lemma 1 — E[f(Bin(x, γ))] is nondecreasing and convex in x when f is nondecreasing and convex
ProvedAirlineYieldMgmt.BookingLimits.lemma1_binomial_convexLet , , be nondecreasing and convex, and let . For each non-negative integer let be a binomial- random variable and
Then is nondecreasing and convex on :
In the paper this lemma (quoted from Shaked and Shanthikumar, 1994, Example 6.A.2) is what makes the terminal value concave and nonincreasing, which starts the induction behind the booking-limit result.
Formalization Note. with MonotoneOn f (Set.Ici 0) and ConvexOn ℝ (Set.Ici 0) f, the paper's ", ". The expectation is the finite binomial sum binomExp x γ f. Convexity in is stated as the discrete second-difference inequality, not as convexity of a real interpolation.
import Mathlib import Definitions.Def_AirlineYieldMgmt_BookingLimits_Model
namespace AirlineYieldMgmt.BookingLimits
/-- Lemma 1 (p. 151). If `f(y)`, `y ≥ 0`, is nondecreasing and convex and `0 < γ < 1`, then
`h(x) := E[f(Y(x))]` with `Y(x) ∼ Bin(x, γ)` is nondecreasing and (discretely) convex in
`x ∈ {0, 1, …}`. -/
theorem lemma1_binomial_convex (f : ℝ → ℝ) (hf_mono : MonotoneOn f (Set.Ici 0))
(hf_convex : ConvexOn ℝ (Set.Ici 0) f) (γ : ℝ) (hγ0 : 0 < γ) (hγ1 : γ < 1) :
Monotone (fun x : ℕ => binomExp x γ f) ∧
∀ x : ℕ, binomExp (x + 1) γ f - binomExp x γ f ≤
binomExp (x + 2) γ f - binomExp (x + 1) γ f := by sorry
end AirlineYieldMgmt.BookingLimits
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Hypotheses. Let be any function that is nondecreasing on and convex on . Its behaviour on the negative reals is unrestricted. Let be a real number with (both inequalities strict).
The function studied. For define
the expectation of for .
Conclusion. The statement asserts both of the following:
- is nondecreasing on : .
- For every ,
That is, the forward differences of are nondecreasing (discrete convexity) on all of .
Degenerate cases. Only the values enter . At , . The endpoint values and are excluded by the hypotheses. The hypotheses are satisfiable, for example by any constant , in which case is constant and both conclusions hold with equality.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.