A Simple Lower Bound for the Capacity of the Deletion Channel

Abstract

We present a simple proof that the capacity of the binary independent and identically distributed (i.i.d.) deletion channel, where each bit is deleted independently with probability d, is at least (1-d)/9, by developing a correspondence between the deletion channel and an insertion/deletion channel that we call a Poisson-repeat channel