Ordinary compression rate bounded by exact encoder entropy
OpenQAlgorithms.Papers.Independent.Support50.P38.theorem14Let be finite nonempty alphabets, a probability law on , and a stochastic channel. All logarithms and entropies are in bits. Write for the memoryless product laws, , and . Let denote the minimum ordinary visible code alphabet cardinality at -average block total variation at most . Let be the optimized entropy of the encoder's message under exact reconstruction, and . For every fixed ,
This is an upper bound through exact encoder entropy, rather than through exact code cardinality.
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P38
noncomputable section
namespace QAlgorithms.Papers.Independent.Support50.P38
open scoped BigOperators Matrix ComplexConjugate
open Filter
open QAlgorithms.Papers.Independent.Information100.P56 (IsLaw)
open QAlgorithms.Papers.Independent.Frontier30.P12 (IsStochastic)
open QAlgorithms.Papers.Independent.Information100.P27 (shannon labelInformation)
attribute [local instance] Classical.propDecidable
/-- Theorem 14, PDF p.7: the ordinary fixed-error limsup rate is at most the optimized
exact encoder-entropy rate Gamma. Blocking the argument with arbitrary superletters is
implicit in the source; Gamma is not the minimum exact log-cardinality rate. -/
theorem theorem14 {A B : Type} [Fintype A] [Fintype B] [Nonempty A] [Nonempty B]
(p : A → ℝ) (w : A → B → ℝ) (hp : IsLaw p) (hw : IsStochastic w)
(error : ℝ) (he : 0 < error) (he1 : error < 1) :
Filter.limsup (sizeRate p w error) atTop ≤ exactEntropyRate p w := by sorry
end QAlgorithms.Papers.Independent.Support50.P38
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
Let be finite nonempty types, let be nonnegative with sum , let have nonnegative rows each summing to , and fix . At length , consider codes with a positive message count , encoder distributions , decoder distributions , and output , for . Let be the infimum in of the sizes of codes satisfying
Let be the real infimum of , where and , over codes exact on every , meaning ; put . Then the limit superior along natural numbers satisfies
All lengths in this rate sequence are positive; zero source and channel probabilities and singleton alphabets are included, and exactness in the definition of also covers zero-probability input words.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.