here are the four posts I made on the strong converse for the MAC:
- Part 1 : the setup and Fano distributions
- Part 2 : choosing a non-product subcode
- Part 3 : a wringing lemma
- Part 4 : almost-independence via wringing
Thanks for reading!
In the previous post we saw how to take two distributions and on that are close and show that there must be some fixed values for individual variables such that the single letter marginals of and are close when you condition on .
Corollary 1 Let and suppose and let be a code for the MAC with maximal error probability . Then for an and there exist for and fixed values such that the subcode formed by
has maximal error ,
and for all and and all ,
where and are distributed according to the Fano distribution of the subcode.
That is, we can condition on some values at and (a) not lose too much rate for each user and (b) the joint distribution of the subcode is almost a product distribution. Remember, the Fano distribution is just the uniform distribution on the codewords of the subcode induced by .
So how does this result follow from the Wringing Lemma discussed before? Let be the Fano distribution of the original code, and let be the product distribution induced by the marginal distributions on the code:
Then just churn through the implications of the Lemma.
So putting the whole argument together, we start first with an code for the MAC and then we get a subcode from pairs defined before. This code satisfies rate bounds which look almost like what we want — they have sums of mutual informations like except that are distributed uniformly on , so they are not independent. We can then apply the corollary above to get that there is a sub-subcode indexed by for which the Fano distribution on is almost independent, and for which we have not lost too much rate. Now we have rate bounds with a sum of terms where the inputs are almost independent, so then we can use the continuity of mutual information and entropy to get upper bounds with sums of where the inputs are finally independent.
There are three steps here — first you find a subcode with more uniform error properties but dependence between the codewords, then you wring out the dependence without giving up too much rate, and finally you substitute in the independent inputs without giving up too much rate. And that’s the value of wringing arguments: in order to get the nice structure from the subcode with you have to get back the independence of inputs that you lost.