Proof of Theorem 3, p. 21 — the minimum posterior equals 1/(1 + ((1+ζ)/(1−ζ))^{|N¹ − N⁰|})
ProvedFastCLO.LowerBound.posterior_identitybayes-risklower-boundsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and let . Then
In the lower-bound construction the left side is the minimum of the posterior probabilities of and given the data, where and count the observations at with each of the two possible cost vectors. The identity shows that this posterior depends on the data only through .
Formalization Note This is the second equality of the page's display. The hypothesis keeps ; the proof uses .
Preamble
import Mathlib
Formal statement
namespace FastCLO.LowerBound
/-- The posterior identity (Hu, Kallus, Mao, arXiv:2011.03030v3, proof of Theorem 3, p. 21, the
display after "Hence,"): with `a = (1+ζ)/2`, `c = (1−ζ)/2` and counts `N⁰, N¹`,
`min{a^{N¹}c^{N⁰}, a^{N⁰}c^{N¹}} / (a^{N¹}c^{N⁰} + a^{N⁰}c^{N¹}) = 1 / (1 + ((1+ζ)/(1−ζ))^{|N¹ − N⁰|})`.
Formalization Note: this is the second equality of the display (the first identifies the left side
with the minimum posterior probability). `ζ < 1` keeps `1 − ζ ≠ 0`; the proof uses `ζ ≤ 1/2`. -/
theorem posterior_identity (ζ : ℝ) (h0 : 0 ≤ ζ) (h1 : ζ < 1) (N0 N1 : ℕ) :
min (((1 + ζ) / 2) ^ N1 * ((1 - ζ) / 2) ^ N0) (((1 + ζ) / 2) ^ N0 * ((1 - ζ) / 2) ^ N1) /
(((1 + ζ) / 2) ^ N1 * ((1 - ζ) / 2) ^ N0 + ((1 + ζ) / 2) ^ N0 * ((1 - ζ) / 2) ^ N1) =
1 / (1 + ((1 + ζ) / (1 - ζ)) ^ (Int.natAbs ((N1 : ℤ) - N0))) := by sorry
end FastCLO.LowerBound
Source
Hu, Kallus, Mao, Fast Rates for Contextual Linear Optimization, arXiv:2011.03030v3, proof of Theorem 3 (A.2), p. 21, the display after "Hence,"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.