Tilted law minimizes KL on its alternative-divergence level set
ProvedQAlgorithms.Papers.Independent.Gap48.P41.tilted_law_minimizes_KL_on_levelLet be a nonempty finite alphabet, and let be probability distributions on , allowing zero coordinates. Write for natural-log Kullback–Leibler divergence, with zero mass contributing zero and support failure giving . For real , put
A zero gives zero tilted mass, and inverse powers act only on positive support. The finite rate condition entails . Define
where the infimum ranges over all probability distributions. The second divergence is finite for every feasible law; the first may be infinite.
Let satisfy . For every probability distribution on ,
This is the Appendix's level-set minimization claim. Trial distributions need not be supported on ; their divergence to is then infinite.
import Definitions.Def_QAlgorithms_Papers_Independent_Gap48_P41
noncomputable section
namespace QAlgorithms.Papers.Independent.Gap48.P41
open scoped Matrix ComplexOrder BigOperators
open Filter QAlgorithms
open QAlgorithms.Papers.Independent.Information100.P60 (Mat copies)
open QAlgorithms.Papers.Independent.Information100.P71 (supportPower)
open QAlgorithms.Papers.Independent.Information100.P07 (positiveProjection)
open QAlgorithms.Papers.Independent.Dependency50.P28
(tr SupportLE relativeEntropy scalarPower classicalD typeI accept TestSequence
scaled logNonnegativeExtended)
open QAlgorithms.Papers.Independent.Claimed50.P15 (legendre)
open QAlgorithms.Papers.Independent.Information100.P56 (IsLaw)
attribute [local instance] Classical.propDecidable Classical.decEq
variable {I : Type} [Fintype I] [DecidableEq I]
variable {X : Type} [Fintype X]
/-- PDF pp.8--9, Appendix, (23): every law on the tilt's q-divergence level has
at least the tilt's divergence to p. The comparison is between KL values; phat
is arbitrary and may have infinite divergence to p. No auxiliary t>=0 from the
source's proof is assumed. -/
theorem tilted_law_minimizes_KL_on_level [Nonempty X]
(p q : X → ℝ) (hp : IsLaw p) (hq : IsLaw q) (r s : ℝ)
(hr : classicalD (.finite 1 (by norm_num)) p q < (r : EReal)) (hs : 0 < s)
(hlevel : classicalD (.finite 1 (by norm_num)) (tilt p q s) q = (r : EReal))
(phat : X → ℝ) (hphat : IsLaw phat)
(heq : classicalD (.finite 1 (by norm_num)) phat q = classicalD (.finite 1 (by norm_num)) (tilt p q s) q) :
classicalD (.finite 1 (by norm_num)) (tilt p q s) p ≤ classicalD (.finite 1 (by norm_num)) phat p := by sorry
end QAlgorithms.Papers.Independent.Gap48.P41
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let be a finite, nonempty set, and let be nonnegative functions each summing to . For real functions , define if whenever , and otherwise, using natural logarithms. Write for and for , including for zero and negative exponents. Define and . Suppose satisfy , , and . For every nonnegative function summing to and satisfying , one has
in the extended-real order. Zero probabilities are allowed: the strict bound on requires wherever , while may equal . The exact-level hypothesis is assumed and may be impossible to satisfy, as when .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.