Exact reconstruction entropy rate and its infimum
ProvedQAlgorithms.Papers.Independent.Support50.P38.exactEntropy_limitLet 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 be the infimum of over all finite nonempty ordinary stochastic code alphabets and encoders and decoders reproducing exactly for every word . Define . Then
The feasible entropy values are nonempty and nonnegative: sending the label word is feasible. This gives a well-defined normalized exact encoder-entropy rate. Entropy-minimum attainment is retained explicitly in the finite-cardinality optimal-code theorems.
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
/-- PDF pp.1–2 and p.7: subadditivity of S and existence of its normalized entropy-rate
limit, equal to the infimum over positive blocklengths. -/
theorem exactEntropy_limit {A B : Type} [Fintype A] [Fintype B]
[Nonempty A] [Nonempty B] (p : A → ℝ) (w : A → B → ℝ)
(hp : IsLaw p) (hw : IsStochastic w) :
(∀ n m, exactEntropy p w (n + m) ≤ exactEntropy p w n + exactEntropy p w m) ∧
Tendsto (fun n : ℕ => exactEntropy p w (n + 1) / (n + 1 : ℝ))
atTop (nhds (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 , and let have nonnegative rows each summing to . For a natural number , a compression code consists of a positive message count , probability distributions on the messages for each , and probability distributions on for each message; call it exact when
Its induced message law is . With , define as the real infimum of over all exact length- codes, and define . Then
The subadditivity assertion includes or , using the single empty word and empty products equal to ; the displayed limit uses only positive lengths. Exactness is required on every input word, including words of zero source probability.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.