# 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. – Ran G. May 25 '16 at 1:49

## 1 Answer

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 . – William Hird May 25 '16 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. – Ran G. May 25 '16 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? – William Hird May 25 '16 at 1:17
• @WilliamHird it would be helpful if you gave a formal statement of what you are looking for. – Ran G. May 25 '16 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. – William Hird May 25 '16 at 1:42