Improved Lower Bounds for I.I.D. Deletion Channels

We consider the capacity of binary deletion channels, where bits are deleted independently with probability \$d\$. We improve significantly upon the framework used in \cite{DG,DM} to lower bound this capacity, by utilizing a stronger definition of a typical output from the channel. In this paper, we specifically focus on codeword sequences given by a first order Markov chain. Our results give the best bounds on the capacity for all values of \$d\$; in particular, for \$d \geq 0.65\$, we surpass Ullman's combinatorial upper bound for channels with an asymptotic fraction of \$d\$ synchronization errors. Hence our results explicitly indicate a need for new upper bounds in the case of channels with i.i.d. synchronization errors.