Common-randomness compression with typical-word guarantees
OpenQAlgorithms.Papers.Independent.Support50.P38.theorem9Let 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 and . There are and , depending only on these fixed data, such that every , , admits a visible stochastic code with common message alphabet and an independent uniform seed on values. If is its output channel averaged over the seed, then
Here consists of words whose count of each letter differs from by at most . The result quantifies communication and shared randomness separately.
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 9, PDF pp.4–5, including (4), (11), and BOTH resource bounds. The general
construction is credited by the source to Bennett et al. [6], footnote 4, and independently
Duer–Vidal–Cirac [9]. Constants may depend on the fixed source, error, and typical width. -/
theorem theorem9 {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) (error width : ℝ)
(he : 0 < error) (he1 : error < 1) (hd : 0 < width) :
∃ k : ℝ, 0 < k ∧ ∃ threshold : ℕ, ∀ n ≥ threshold, 0 < n →
∃ c : SharedCode A B n, c.Uniform ∧
Real.logb 2 (c.size : ℝ) ≤ n * sourceInformationBits p w + k * Real.sqrt n ∧
Real.logb 2 (c.seeds : ℝ) ≤ n * sourceConditionalEntropyBits p w + k * 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 satisfy and , and let satisfy and for every . For real numbers and , there are a real and a natural-number threshold such that every positive integer at least that threshold admits a shared code with positive message count , positive seed count , uniform seed weights , stochastic encoder rows , and stochastic decoder rows , whose output is
and for which
Here , , and , where . In addition, every satisfying
satisfies . Zero probabilities are allowed; the displayed occurrence condition then forces zero occurrences of any with .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.