Ordinary compression under the letterwise criterion
OpenQAlgorithms.Papers.Independent.Support50.P38.theorem13Let 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 . For each fixed , there exist such that every , , admits an ordinary visible stochastic code, with independent private randomness and no shared seed, whose output law satisfies
The subscript denotes the marginal on the th output position. This is the source's letterwise criterion, with averaging outside the distance.
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 13, PDF p.7: no shared randomness and the precise letterwise criterion (5).
Communicating a choice from polynomially many seeds is included in the message alphabet. -/
theorem theorem13 {A B : Type} [Fintype A] [Fintype B] [DecidableEq B]
[Nonempty A] [Nonempty B] (p : A → ℝ) (w : A → B → ℝ)
(hp : IsLaw p) (hw : IsStochastic w) (error : ℝ) (he : 0 < error) (he1 : error < 1) :
∃ k : ℝ, 0 < k ∧ ∃ threshold : ℕ, ∀ n ≥ threshold, 0 < n →
∃ c : DistributionCompressionCode A B n,
Real.logb 2 (c.size : ℝ) ≤ n * sourceInformationBits p w + k * Real.sqrt n ∧
letterError p w c ≤ error := 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, with decidable equality on , let be nonnegative with total mass , let have nonnegative rows of total mass , and fix . Write , , and . There exist and a natural-number threshold such that for every with , there is a compression code with a positive message count , encoder distributions , and decoder distributions , for , whose output is , satisfying
and
Thus the stated error is the source average of the mean, over positions, of the total variation distances between the target single-position row and the corresponding output marginal. The decoder may be stochastic, and no shared seed is part of this code. Singleton alphabets and zero probabilities are allowed.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.