Asymptotic channel simulation and feedback rate region
OpenQAlgorithms.Papers.Independent.Support50.P38.corollary12Let be a channel between finite nonempty alphabets . All rates are in bits per use. For and , say that is achievable at asymptotic error if for every error slack and rate slack , every sufficiently large positive admits a shared-seed code with deterministic output from seed and message, communication at most , prepared randomness at most , and total variation at most for every input word. Then
The two maxima range independently over all input probability laws and need not have a common maximizer. Independent local randomness is free. This characterizes channel simulation with noiseless passive feedback, including boundary rates by arbitrary slack.
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
/-- Corollary 12, PDF p.6: exact asymptotic rate region for uniform-on-input channel
simulation with noiseless passive feedback. The two suprema may use different input laws;
expressing each constraint for every law avoids any assumption of a common maximizer. -/
theorem corollary12 {A B : Type} [Fintype A] [Fintype B] [DecidableEq B]
[Nonempty A] [Nonempty B] (w : A → B → ℝ) (hw : IsStochastic w)
(error communication randomness : ℝ) (he : 0 ≤ error) (he1 : error < 1)
(hr : 0 ≤ communication) (hc : 0 ≤ randomness) :
FeedbackRates w error communication randomness ↔
((∀ p : A → ℝ, IsLaw p → sourceInformationBits p w ≤ communication) ∧
(∀ p : A → ℝ, IsLaw p → shannon (sourceOutputMarginal p w) ≤ communication + randomness)) := 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 , and let have nonnegative rows each summing to . Fix reals , , and . Define , , and . The following are equivalent: first, for every tolerance and slack , there is a natural-number threshold such that for every with , there exists a shared code with positive message and seed counts , a nonnegative seed distribution of total mass , encoder distributions , and deterministic decoder distributions for some , whose output satisfies
second, for every with and , both and . The codes in the first assertion may depend on , but each code must meet its error bound for every input word. The seed law is not required to be uniform, the randomness bound counts seeds, and the case is included through the requirement for every positive tolerance.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.