Single-letterization, Fano's inequality, and the weak converse over finite alphabets
ProvedTranscendenceTower.ConversePlatform.memoryless_converseFive facts about repeated use of a memoryless channel and about what a decoder can recover from it, over arbitrary finite alphabets, in nats.
-
The independence bound. For any law on words of length , the entropy of the word is at most the sum of the entropies of its coordinate marginals. Observing things at once is never more uncertain than observing them separately and adding up.
-
Memorylessness. The entropy of a product law is exactly the sum of the entropies of its factors. Independent uses contribute independently; nothing accumulates across them.
-
The -use bound. For a memoryless channel and any prior on input words — correlated across uses or not — the information the output word carries about the input word is at most the sum over coordinates of the information a single use carries. Bounding each summand by the one-use capacity then gives the familiar . That the prior is arbitrary is the content: correlating the inputs is permitted and does not help.
-
Fano's inequality. For a joint law on (guess, truth) over an alphabet of size with error probability , the uncertainty about the truth that survives knowing the guess is at most , where is the binary entropy. If the guess is usually right, little uncertainty remains.
-
The weak converse. If in addition the information the guess carries about the truth is at most , then the entropy of the truth is at most plus that same error term. For a uniform truth over possibilities this reads : a decoder that is usually right can only have been distinguishing about possibilities.
The mathematics is classical. What is established is that these identities and bounds hold for the guarded finite sums as defined, with zero-mass cells contributing zero by an explicit case split rather than by a limit, and under no positivity hypotheses on the marginals.
Limits. The constant in item 4 is , not the sharper textbook . The bound in item 5 is a hypothesis rather than an instantiation: items 3 and 5 concern different quantities — and — and joining them requires the data processing inequality, which is not proved here. No achievability statement is made or approached.
import Definitions.Def_TranscendenceTowerConverse set_option autoImplicit false open scoped BigOperators open TranscendenceTower.FiniteInformation open TranscendenceTower.ConversePlatform
theorem TranscendenceTower.ConversePlatform.memoryless_converse (α β γ : Type) [Fintype α] [DecidableEq α]
[Fintype β] [DecidableEq β] [Fintype γ] [DecidableEq γ] :
-- the independence bound on words
(∀ (n : ℕ) (law : (Fin n → β) → ℝ), (∀ w, 0 ≤ law w) → (∑ w, law w = 1) →
entropy law ≤ ∑ i : Fin n, entropy (coordMarginal law i))
-- memorylessness: entropy is additive across coordinates
∧ (∀ (n : ℕ) (rows : Fin n → β → ℝ), (∀ i b, 0 ≤ rows i b) →
(∀ i, ∑ b, rows i b = 1) →
entropy (productLaw rows) = ∑ i : Fin n, entropy (rows i))
-- the n-use bound, for an arbitrary and possibly correlated input prior
∧ (∀ (n : ℕ) (prior : (Fin n → α) → ℝ) (K : α → β → ℝ),
(∀ x, 0 ≤ prior x) → (∑ x, prior x = 1) → (∀ a b, 0 ≤ K a b) →
(∀ a, ∑ b, K a b = 1) →
mutualInfo (channelJoint prior K)
≤ ∑ i : Fin n,
(entropy (coordMarginal (sndMarginal (channelJoint prior K)) i)
- ∑ a : α, coordMarginal prior i a * entropy (K a)))
-- Fano's inequality
∧ (∀ J : γ → γ → ℝ, (∀ g w, 0 ≤ J g w) → (∑ g, ∑ w, J g w = 1) →
condEntropy J
≤ shannon (correctProb J) + shannon (errorProb J)
+ errorProb J * Real.log (Fintype.card γ))
-- and the weak converse it supports
∧ (∀ (J : γ → γ → ℝ) (bound : ℝ), (∀ g w, 0 ≤ J g w) →
(∑ g, ∑ w, J g w = 1) → mutualInfo J ≤ bound →
entropy (sndMarginal J)
≤ bound + shannon (correctProb J) + shannon (errorProb J)
+ errorProb J * Real.log (Fintype.card γ)) := by sorry