Tight Asymptotic Bounds for the Deletion Channel with Small Deletion Probabilities

In this paper, we consider the capacity C of the binary deletion channel for the limiting case where the deletion probability p goes to 0. It is known that for any p < 1/2, the capacity satisfies C >= 1?H(p), where H is the standard binary entropy. We show that this lower bound is essentially tight in the limit, by providing an upper bound C <= 1?(1?o(1))H(p), where the o(1) term is understood to be vanishing as p goes to 0. Our proof utilizes a natural counting argument that should prove helpful in analyzing related channels.