# Capacity of the Deletion Channel

Consider a Binary Deletion Channel with a deletion probability p of 1/2 and the channel has no error correction coding at all and that any given message can only be sent once. I want to conjecture that the capacity for the aforementioned channel is zero ( channel capacity for the Deletion Channel is presently unknown), can anyone point to any known complexity results that would point me in the direction of proving or disproving my conjecture?

• The capacity of the deletion channel $\text{Del}: X\to Y$ with deletion prob $p$ can be defined to be $\lim_n \frac1n \max_{P_{X^n}}I(X^n ; Y^n)$ where $I()$ is mutual information and $P_{X^n}$ is any possible distribution on $X^n$. This definition is independent of "error correction" and of "sending message only once". Please formulate properly what is the quantity you wish to get. Specifically, how the above two vague notions (marked in quotations) are defined. Commented May 25, 2016 at 1:49

The capacity of a deletion channel with deletion probability $p$ is still not fully understood, however it is known to be somewhere between $1-h(p)$ and $(1-p)/9$.

See a survey by Michael Mitzenmacher on deletion channels: A survey of results for deletion channels and related synchronization channels.

• Yes I have read that paper but my question is about a deletion channel with the restrictions mentioned . Commented May 25, 2016 at 0:53
• @WilliamHird Can you prperly define your restrictions? Channel's capacity is a property of the channel. If you use it in a strange way (e.g., without using error correction) you will not be able to achieve the capacity, but that doesn't change the capacity of the channel. Please clarify your question. Commented May 25, 2016 at 0:56
• That's the point of my question, to try to prove that with no error correction and the restriction that any message can only be sent once, you can't reach the 1-h(p) and (1-p)/9 bound. Is this bound mentioned in the paper for the "raw channel" or for a channel with error correction coding? Commented May 25, 2016 at 1:17
• @WilliamHird it would be helpful if you gave a formal statement of what you are looking for. Commented May 25, 2016 at 1:33
• G: Not trying to be cute here, but I thought my question was clear , maybe if you ask me specifically what you don't understand about the question as posed we can go from there. Commented May 25, 2016 at 1:42

This is an old question, but let me give a final response for anyone who comes across it.

Your restriction is that we are not allowed to do any coding. In other words, every source codeword is transmitted directly across the channel. Since there is no redundancy being added, the transmission rate is 1 bit per symbol. As mentioned by Ran, we know that such a rate is not possible due to the channel capacity upper bound of $$1/9(1-d)$$ for deletion probability $$d$$.

A more direct way to show that such a rate cannot be achieved is to consider the block error. For a block length $$N$$ approaching infinity, there is almost surely at least 1 deletion in the channel output. WLOG, consider an input sequence $$x = (x_1,x_2,x_3\ldots,x_N)$$ that becomes $$y = (x_2,x_3\ldots,x_N)$$ after deleting $$x_1$$. Looking at $$y$$, there are multiple possible input sequences, only one of which is the transmitted $$x$$. The best decoder is guaranteed to make an error with non-zero probability, and hence the block error of this symbol is non-zero. For multiple deletions, this block error is only going to increase towards 1.