# Coding for channels with concentrated error

Can we implement a reduced-error transmission over a channel with error frequency having $\liminf<\frac{1}{2}$ and $\limsup>\frac{1}{2}$?

We know that if a channel with error flips (in the limit) strictly less than 1/2 of the bits, we can recover asymptotically error-free transmission with an appropriate code. By bit-inversion, this applies if, in the limit, the channel flips strictly more than 1/2 of the bits.

These arguments don't actually deal with the limit, though... they simply require $$\limsup_{n\to\infty}{\frac{E\cap\left[0,n\right)}{n}}<\frac{1}{2}\text{ or }\liminf_{n\to\infty}{\frac{E\cap\left[0,n\right)}{n}}>\frac{1}{2},$$ taking $E$ to be the set of locations of the flipped bits. That is, we recover asymptotically error-free transmission if $E$ has upper density $<\frac{1}{2}$ or lower density $>\frac{1}{2}$.

Of course, there are channels with error density $\frac{1}{2}$ with capacity 0, so there's not always a useful code.

This leaves a gap I find interesting. Can we say anything about channels with error having lower density $<\frac{1}{2}$ and upper density $>\frac{1}{2}$? In particular, can we reduce the upper density by use of a (possibly standard) error-correcting code?

For the sake of argument, suppose we have a binary error channel that introduces errors with upper density $\frac{3}{4}$ and lower density $\frac{1}{4}$. Can we use this to implement a transmission with reduced upper density of error? (As a concrete goal - can we get the upper density of error below $\frac{5}{8}$?)

I suspect we can't guarantee asymptotically error-free transmission, but if it's possible, such a scheme would obviously answer my question. In any case, I have no objection to a code that sacrifices an increase in lower density of error to achieve a decrease in upper density of error.

• Normally, there is some model for the noise, such as independent chances for flipping bits. Which model are you assuming that would produce that behavior? – Douglas Zare Oct 21 '14 at 15:00
• @DouglasZare - I was actually noting that I think the standard results are independent of the model chosen, if we speak in terms of limiting error frequency; that is, they're valid against the adversarial model of noise with the given density. I mean to assume that same worst-case model, since I'm coming at this from the perspective of computability. – Eric Astor Oct 21 '14 at 17:01
• I stand corrected that my previous answer is wrong. Thinking about this some more, the problem implies some complexity -- there must be increasingly long runs with BER bounded above 1/2 and long runs with BER bounded below 1/2. Otherwise, the cumulative BER couldn't have lim inf less than 1/2 and lim sup greater than 1/2. If you know in advance how far the limits are away from 1/2 and use an error-correcting code that works successfully in that regime, then you can send fixed-length data blocks and get an infinite number through successfully. – Dale Jun 4 '17 at 19:05
• @Dale As it happens - this question's original motivation was resolved a few years ago, using almost exactly the method you suggest. Benoit Monin coupled that approach with list decoding, proved that infinitely many blocks would get through with positive information, and used this to show that one could essentially implement a transmission with arbitrarily small error. For reference, see lacl.fr/~benoit.monin/ressources/papers/resolution_gamma.pdf – Eric Astor Sep 21 '17 at 19:10