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.