# Lossless vs lossy compressible bin sequences

What are some interesting differences between the set of lossless and lossy compressible binary sequences (lossy := there exists a decompression algorithm that can recover over 50% of the sequence’s bits)?

How can we characterize the set of sequences that under the lossy def become compressible that under the lossless def were not?

• You have to be a bit more precise about the condition "can recover over 50% of the sequence’s bits". Presumably you mean in the limit -- perhaps limsup of the average error is bounded away from $1/2$. – Aryeh Sep 11 at 7:06