The deletion channel is the simplest point-to-point communication channel that models lack of synchronization. Despite significant effort, little is known about its capacity, and even less about optimal coding schemes. In this paper we intiate a new systematic approach to this problem, by demonstrating that capacity can be computed in a series expansion for small deletion probability. We compute two leading terms of this expansion, and show that capacity is achieved, up to this order, by i.i.d. uniform random distribution of the input. We think that this strategy can be useful in a number of capacity calculations.
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.