Small-error communication refinement with passive feedback
OpenQAlgorithms.Papers.Independent.Support50.P38.remark10Let 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 . Fix a typical width . There are and , independent of the error parameter, such that for every and , , a uniform-shared-seed visible code satisfies
Its seed-averaged block error is at most , and its pointwise error is at most on , defined by the count tolerance . Moreover, the decoder's output word is a deterministic function of the seed and message, so both parties recover the identical realized word. This refines the error dependence of the communication bound; no additional error-dependent seed-size bound is asserted.
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
/-- Remark 10, PDF p.5: quantitative small-error refinement and noiseless passive feedback.
The constant and threshold are uniform in 0 < lambda <= 1/2; no lambda-dependent seed bound
is invented. The source's supporting tail (10) has a counterexample (see moderation ledger);
this statement retains the expressly stated resource claim without assuming that tail. -/
theorem remark10 {A B : Type} [Fintype A] [Fintype B] [DecidableEq A] [DecidableEq B]
[Nonempty A] [Nonempty B] (p : A → ℝ) (w : A → B → ℝ)
(hp : IsLaw p) (hw : IsStochastic w) (width : ℝ) (hd : 0 < width) :
∃ k : ℝ, 0 < k ∧ ∃ threshold : ℕ,
∀ error : ℝ, 0 < error → error ≤ 1 / 2 → ∀ n ≥ threshold, 0 < n →
∃ c : SharedCode A B n, c.Uniform ∧ c.PassiveFeedback ∧
Real.logb 2 (c.size : ℝ) ≤
n * sourceInformationBits p w + k * (-Real.logb 2 error) * Real.sqrt n ∧
sourceAverageBlockError p w c.output ≤ error ∧
∀ x, VarianceTypicalWord p width x → tv (wordChannel w x) (c.output x) ≤ 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, let be nonnegative with total mass , let have nonnegative rows of total mass , and fix a width . Write , , , , , and . There exist and a natural-number threshold such that, for every and every with , there is a shared code with positive message and seed counts , seed distribution , encoder distributions , and decoder distributions , whose output is , satisfying for every seed and admitting words such that if and otherwise. This code obeys
and its total variation error is also at most for every satisfying for all . The same work for every allowed ; the code may depend on . No upper bound on the seed count is asserted, and zero source probabilities and singleton alphabets are included.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.