# 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

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$.