# Information theory - Expurgation step to go from average error to worst case error in the large error regime

Consider a discrete memoryless channel $$N$$. We use a code to send messages over this channel.

Shannon showed that if we have a code $$C$$ with a finite number of codewords $$|C|$$ such that the average error is $$\varepsilon$$, then we can throw away half the codewords to obtain a code with $$|C|/2$$ codewords but now, the worst case error is bounded by $$2\varepsilon$$.

What is the analogous result in the case where the error is large? If I have a code $$C$$ that achieves an average error of $$1-\varepsilon$$ for some small $$\varepsilon$$, then can I throw away some codewords and still bound the worst case error by something meaningful?

• If you throw away codewords, the worst case error can only decrease. Commented Sep 22, 2021 at 16:23
• @YuvalFilmus the question is how to construct a code with bounded worst case error given a code with average error $1-\varepsilon$. I do not know the worst case error to begin with, I only know the average error. Commented Sep 22, 2021 at 18:39