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