I have been reading Ahlswede’s paper on An Elementary Proof of the Strong Converse Theorem for the Multiple-access Channel, J. Combinatorics, Information and System Sciences, Vol. 7, No. 3, 216-230. The preprint is here but I have a scanned version of the journal version thanks to the intrepid UC Libraries staff — they are a great resource!
I’m going to split up this rather rambling post into a few posts. The main result is the following: for the discrete memoryless MAC, let
Then the for any code of blocklength , rates , and average error , the rates must satisfy
The first step in the proof is to look at non-stationary discrete memoryless channels. Suppose we have a codebook for a point-to-point channel with codewords . You can think of these as vector inputs and outputs representing a whole block, and is just some channel. For a parameter and distribution on the output we can look at the set of outputs
The first thing to show is a packing lemma.
Lemma. Suppose that for an code with codewords and maximal error there exists a distribution and positive numbers such that
This Lemma can be used, with an appropriate choice of , to show a converse for non-stationary DMCs:
The first question is what should we choose? One choice is to put the uniform distribution on the codewords and then just set
Ahlswede calls this the “Fano-distribution,” and remarks that you can use this to get a weak converse. A good choice, used by Augustin, is to pick the output distribution induced by the product of the marginal distributions on each input letter via the uniform distribution of the codebook. Phew! That is a mouthful. So first you take the marginal distribution on each letter of the input:
then take the product of these:
And then look at the corresponding output distribution:
Ahlswede calls the input distribution in this case the “Fano*-distribution.” The intuition about this choice is that it factors into independent components (so we can split things into a sum of mutual informations), but the distribution is still related to the codebook rather than just the channel.
The next thing is to choose an appropriate . The way to understand the right choice is to look at the set , which corresponds to some event related to the (random) output of the channel. The condition of the Lemma says that the probability of this event under input should be less than . Taking logs on both sides we get that a occurs when
So we treat as a random variable and set
With this choice we can just apply Chebyshev’s inequality to get that in the Lemma.
Applying the Lemma and indulging in some bounding-ology yields the point-to-point result.
For a code of blocklength with messages and maximal error probability for the nonstationary DMC:
where the distributions of the random variables are given by the Fano-distribution on the codewords.
Note that in the mutual information expressions we use the Fano-distribution on the codewords. The choice of the Fano*-distribution for was just for applying the Lemma. I’ll pick up the next section of the argument later.