# Capacity of a Binary Deletion Channel

It is well known that a communication channel with a randomly induced 50% bit error rate has zero capacity but determining the capacity of a binary deletion channel is still an open problem. Why wouldn't a channel with 50% of its bits being deleted also be deemed to have zero capacity?

• Check out the Wikipedia page: en.wikipedia.org/wiki/…. Nov 25 '14 at 18:49
• @ Yuval Filmus: My question is about the binary deletion channel, not the binary erasure channel. Nov 25 '14 at 18:55
• Can you explain what is the binary deletion channel, then? Nov 25 '14 at 18:55
• Yes, the Wiki article you just referenced me gives the definitions of both channels :-) Nov 25 '14 at 18:59

A channel with 90% of its bits deleted is still capable of transmitting information. For example, you can send one bit by sending it a hundred times. You can probably send more bits this way, say by transmitting $0^{100} 1^{100}$ for 0 and $0^{200} 1^{100}$ for 1. This still doesn't show that the capacity is positive, but makes it seem reasonable. This survey by Mitzenmacher claims that the capacity is at least $(1-p)/9$, compared to $1-p$ in the binary erasure channel.
• 50% is a magic number only for the binary symmetric channel. It's not a magic number for the binary deletion channel. You can transmit information for any $p \neq 1$, where $p$ is the fraction of deleted bits. A binary symmetric channel with 50% error has zero capacity since the output distribution doesn't depend on the input at all. This is not the case for the binary deletion channel. Nov 25 '14 at 19:23