Weak converse with independent shared randomness
OpenQAlgorithms.Papers.Independent.Support50.P38.commonRandomness_lowerBoundLet 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 pair of alphabets there is a single function , uniform over all normalized source laws and stochastic channels on those alphabets, with as , such that every positive blocklength, every , and every visible code with an independent shared seed of arbitrary law and seed-averaged block error at most satisfy
This preserves the weak information lower bound when common randomness is allowed, without assigning the correction function an unsupported formula.
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.2–4: the weak converse still holds for arbitrary independent shared seed laws.
The vanishing correction f-tilde is uniform over source laws and channels on the fixed
alphabets, as in the entropy-continuity bound f to which the source refers. -/
theorem commonRandomness_lowerBound {A B : Type} [Fintype A] [Fintype B]
[Nonempty A] [Nonempty B] :
∃ f : ℝ → ℝ, Tendsto f (nhdsWithin 0 (Set.Ioi 0)) (nhds 0) ∧
∀ (p : A → ℝ) (w : A → B → ℝ), IsLaw p → IsStochastic w →
∀ error : ℝ, 0 < error → error < 1 → ∀ n : ℕ, 0 < n →
∀ c : SharedCode A B n, sourceAverageBlockError p w c.output ≤ error →
n * (sourceInformationBits p w - f error) ≤ Real.logb 2 (c.size : ℝ) := by sorry
end QAlgorithms.Papers.Independent.Support50.P38
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For any finite, nonempty sets and , there exists a function , with , having the following property. Let satisfy and , and let satisfy and for every . For every , every positive integer , and every shared code consisting of positive integers , seed weights with , encoder probabilities with for every seed and word , and decoder probabilities with for every , define its output by . If its source averaged block error satisfies , then
where and , with zero probability terms interpreted as zero. The same function works for all these distributions, errors, lengths, and codes for the given ; no sign condition on , uniformity condition on the seed distribution, or bound on the number of seeds is assumed.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.