On the deletion channel with small deletion probability
Yash Kanoria Andrea Montanari
Proceedings of the IEEE International Symposium on Information Theory, Austin, TX, USA, June 2010
Abstract

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