Motivation
A binary symmetric channel has enough symmetry to make Hamming distance and Hamming-ball counting natural. A general channel can erase some symbols, confuse some pairs more often than others, or have several inputs producing the same output law. A distance threshold alone no longer describes how convincing a received word is as evidence for a proposed input.
Information density measures that evidence by comparing the probability of an output under one proposed input with its probability under the overall input distribution. For the transmitted pair, its average approaches mutual information. For an unrelated competing input, a simple expectation bound makes a large value unlikely. These two facts give an existential coding theorem for every finite memoryless channel.
The proof chooses a codebook randomly to demonstrate that a good deterministic one exists. It does not provide a fast encoder, a practical decoder or a strong converse. We also prove the necessary rate bound without assuming that the actual codeword coordinates are independent, a distinction that matters for nearly every structured code.
Definitions
Definition 3.4.1
(Finite memoryless channel)
Let be nonempty finite input and output alphabets. A channel is a stochastic matrix with for every input . Its memoryless extension has conditional law
This is conditional independence of outputs given the entire input word; it places no independence requirement on the input distribution itself.
Definition 3.4.2
(Information density)
For a chosen input law , put . All logarithms are base two. On pairs with positive joint probability define information density
For candidate pairs with but , set the information density to minus infinity. Outputs with never occur in the random experiment based on and can be assigned rejection by its decoder. On a positive-probability transmitted pair the density is always finite.
Definition 3.4.3
(Codes, error criteria and capacity)
An -use code has indexed messages, a deterministic encoder into , and a decoder into message indices, possibly also reporting failure. Average error averages over a uniform message and channel noise. Maximum error is the largest conditional error over messages. The rate is . Define
The maximum exists: is continuous on the compact finite-dimensional probability simplex, using . Entropy, conditional entropy, divergence, data processing and Fano's inequality have been proved in the preceding units and are used with their finite-alphabet conventions.
Theorem/proposition
Theorem 3.4.4
(Every smaller rate is achievable)
For every , there is a sequence of deterministic codes whose rates approach and whose maximum error tends to zero. A rate-zero code with one message is always possible, including when . No efficiency guarantee for constructing or decoding these codes is asserted.
Theorem 3.4.5
(A weak converse without independent inputs)
For any -use code with and average error ,
Consequently every sequence with error tending to zero has rate limit superior at most . This bound does not prove that the error tends to one at every larger rate.
Proof sketch or proof idea
A transmitted pair has a typical information density
Proof
(Concentration of the true pair)
Choose with , and choose so that . Generate codewords independently from , retaining their message indices. For sufficiently large there are at least two. Repetitions are allowed in this temporary random list; they are included in the error analysis rather than silently assumed absent.
When one indexed word is transmitted through , averaging over the random list makes its coordinate pairs independent with joint law . The block information density is the sum of the one-coordinate densities. The summands have mean and finite variance , since their positive-probability support is finite. Chebyshev's inequality gives
The codeword randomness is being used here to prove existence. An eventual fixed codebook need not make its coordinates independent under a uniform choice of message.
A competing word rarely passes the threshold
Proof
(A likelihood-ratio bound for competitors)
Decode to a unique index whose word has block information density greater than ; report failure if there are zero or multiple such indices. For a competing word independent of the channel output, its law is and the output's marginal law is after averaging the transmitted random word. Define the nonnegative likelihood ratio on output support. Independence gives
For every positive-probability , an output with positive conditional probability also has positive probability, justifying the last equality despite possible zero channel entries. Markov's inequality now yields .
Fix a transmitted message index. An error can occur only if its true pair fails the threshold or a competing index passes. The union bound does not require the competitor events to be independent. Averaging also over the message index gives expected average error at most
which tends to zero. If two indexed words happen to be equal, their conflict is already among these events.
Fix the codebook and remove high-error messages
Proof
(Expurgation to maximum error)
The random ensemble is finite, so at least one deterministic codebook has average error at most . In that codebook, at least half the messages have individual error at most ; otherwise the average would exceed . Keep those messages and discard the others. Retain the decoder's old answers when they name a retained message, mapping any other answer to failure. This cannot turn a previously correct retained-message answer into an error.
The retained code has maximum error at most and at least messages. Its rate differs from by at most , while tends to . The maximum error therefore tends to zero with no asymptotic rate loss. For sufficiently large this error is below one half, which also rules out duplicate retained codewords: two identical transmitted words have identical output laws, so their two probabilities of correct identification cannot both exceed one half.
Proof X-ray
Three probability spaces and the threshold that links them
Three probability spaces do three jobs, and each hypothesis enters in one of them. The true-pair estimate averages over random codewords and channel noise. There the coordinate pairs are independent with law , so memorylessness and the product input law make the block density a sum of independent terms, and Chebyshev's inequality needs only a finite variance, which finite alphabets supply.
The competitor bound uses a different random word independent of the output. The key move is that this independence makes exactly, so Markov's inequality gives with no further knowledge of the channel. The threshold is the one parameter balancing the two estimates: it lies below the typical density of the true pair, yet high enough that about competitors still fail, which is possible because . Only after these averages is one deterministic codebook chosen, and expurgation then bounds errors over channel noise alone. Nothing claims that the final codebook's coordinates are independent.
Bound the information carried by any fixed code
Proof
(The weak converse)
Now consider an arbitrary fixed encoder and its possibly correlated input word . The memoryless conditional law gives
The first identity follows by averaging the entropy of a product conditional distribution for each input word. The inequality follows from the entropy chain rule and the fact that conditioning cannot increase entropy. Subtracting yields , since each coordinate has some input distribution allowed in the capacity maximum.
Let the uniform message be and the decoder's output . The Markov chain gives . Fano bounds , including a possible failure output. Since , combining the two statements gives the displayed converse. A maximum-error guarantee also bounds average error, so it cannot evade this restriction.
Worked examples
Worked example 3.4.6
(An erasure channel and an explicit existence estimate)
A binary erasure channel reveals the input with probability and otherwise returns a separate erasure symbol, independently at each use. For any input law, , so and capacity is bit per use, attained by a fair input.
For that fair input, information density is one on a revealed symbol and zero on an erasure, so its variance is . Choose target rate and . The proof gives average error at most for some fixed codebook, and at most twice that after expurgation. The estimate is loose for small block lengths, but it explicitly tends to zero. It does not produce the promised codebook or establish an efficient implementation.
Worked example 3.4.7
(Uniform inputs need not maximize capacity)
Let inputs be , with always producing output zero and always producing output one. The channel is deterministic, so mutual information equals output entropy. Uniform inputs give output probabilities and information . Instead choose each with probability one half and never use . The output is then fair and the information is one, the capacity because the output alphabet is binary. An extra input label that behaves identically to another does not automatically supply another distinguishable message symbol.
Worked example 3.4.8
(Memoryless outputs do not force independent inputs)
Take the noiseless binary channel, with capacity one. Choose one fair bit and set every input coordinate equal to . Each output coordinate is fair, so , but the entire output word has entropy only one because it is either all zero or all one. Thus , not . The converse correctly uses an inequality and applies to this repetition encoder. Substituting equality by an unjustified input-independence assumption would overstate the information carried by the actual code.
Common mistakes
Counterexample mode
Identical one-coordinate noise laws do not prove memorylessness
Suppose a single fair bit is added to every bit of a transmitted binary block. Each coordinate separately looks like a completely noisy binary channel. Yet the receiver sees either the entire word or its complement. Choose codewords whose first bit is zero, using the other bits as the message. The first received bit reveals , so all bits can be corrected with zero error, at rate . The noise is correlated across the block, so the product conditional law fails and a zero-capacity conclusion from one-coordinate marginals would be wrong.
Common mistake
(The proof is not a construction)
The theorem also does not assert that a uniform input is optimal, as the deterministic example shows. Nor does its exponentially large random list constitute a practical coding algorithm. The decoder may compare the received word with every indexed codeword; the proof's goal is existence at a rate, and efficient constructions require separate work.
Counterexample mode
Small average error does not bound every message
Claim: if the average error of a code sequence tends to zero, so does its maximum error. Use the noiseless binary channel with messages, each sent as its own -bit word, and a decoder that is correct except that it maps the output to the message of . The message is always decoded wrongly and every other message correctly, so the average error is while the maximum error is for every . The repair is expurgation: discarding messages whose error exceeds twice the average, here only , leaves maximum error zero at a rate loss of at most .
Summary
For a finite memoryless channel, capacity is the largest input–output mutual information. Information-density concentration and a likelihood-ratio bound prove all smaller positive rates achievable. Fixing a codebook and expurgating high-error messages gives maximum-error reliability. Fano and the memoryless entropy identity prove the weak converse even when the encoded inputs are correlated.
Exercises
Quick check
(Prove that capacity is zero exactly when every input symbol induces the same output distribution.)
Write capacity as an average of divergences from the output mixture.
Solution
If every row is the same, input and output are independent for every input law, so mutual information is zero. Conversely, if two rows differ, give their inputs equal probability. Mutual information is the average of the two divergences from their output-mixture law. Divergence is nonnegative and vanishes only for identical distributions, so at least one is positive and the information is positive. Hence the capacity maximum is positive.
Quick check
(Why is the competing random codeword independent of the output in the ensemble argument, while the transmitted random codeword is not?)
Ask which random variables generate the output.
Solution
Conditional on which index was sent, the output is generated from that index's random word and fresh channel noise. Every different index's word was drawn independently of both. The transmitted word and output are linked by the channel and have joint law ; replacing that joint law by the independent product would destroy the true-pair concentration argument.
Quick check
(If the target rate is a fixed , what asymptotic lower bound on average error follows from the proved converse? Does it force error to one?)
Rearrange the converse with .
Solution
Rearrangement gives , where . If , the limit inferior is at least . Except for a zero-capacity special case, this is generally below one. A strong-converse proof requires further reasoning beyond this inequality.
Quick check
(Explain why keeping at least half the messages loses asymptotically no rate, even though it can remove many messages in absolute number.)
Compare with .
Solution
Replacing by a number at least subtracts at most one from , and therefore at most from the rate. That loss tends to zero with block length. Counting removed messages directly misses that rate uses the logarithm of their number.