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?

  • $\begingroup$ Check out the Wikipedia page: en.wikipedia.org/wiki/…. $\endgroup$ Nov 25 '14 at 18:49
  • $\begingroup$ @ Yuval Filmus: My question is about the binary deletion channel, not the binary erasure channel. $\endgroup$
    – user34722
    Nov 25 '14 at 18:55
  • $\begingroup$ Can you explain what is the binary deletion channel, then? $\endgroup$ Nov 25 '14 at 18:55
  • $\begingroup$ Yes, the Wiki article you just referenced me gives the definitions of both channels :-) $\endgroup$
    – user34722
    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.

In contrast, the binary channel with 50% errors is completely opaque - the output distribution doesn't depend on the input at all. You can't even send one bit.

  • $\begingroup$ Lets assume that you can't re-transmit any bits and there are no error correcting bits sent with the message, if 90% of the bits are deleted can you still transmit information? $\endgroup$
    – user34722
    Nov 25 '14 at 19:10
  • 2
    $\begingroup$ I just showed you how to transmit one bit with arbitrarily high success probability. Even in the usual binary communication channel, unless there are no errors at all, you have to use some code to transmit information. That's the game. That's what it means to transmit information. $\endgroup$ Nov 25 '14 at 19:14
  • $\begingroup$ That's my point, I don't want to transmit any information at all, my question is purely theoretical, I'm looking for a mathematical way to compare the capacity of a channel with 50% of its bits being flipped to a channel with 50% of its bits being erased, why can't both cases be deemed to be zero capacity? $\endgroup$
    – user34722
    Nov 25 '14 at 19:21
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 25 '14 at 19:23
  • $\begingroup$ @user34722 : don't mix "erase" with "delete", here they are different things. Further, I don't see if you want some intuition or some demonstration. If the first, Yuval answer fits the bill (and perhaps also the consideration of the erasure channel). If the second, then you can just compute the bounds. $\endgroup$
    – leonbloy
    Nov 25 '14 at 19:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.