  In this paper, we consider the problem of sequential transmission over the
binary symmetric channel (BSC) with full, noiseless feedback. Naghshvar et al.
proposed a one-phase encoding scheme, for which we refer to as the small-enough
difference (SED) encoder, which can achieve capacity and Burnashev's optimal
error exponent for symmetric binary-input channels. They also provided a
non-asymptotic upper bound on the average blocklength, which implies an
achievability bound on rates. However, their achievability bound is loose
compared to the simulated performance of SED encoder, and even lies beneath
Polyanskiy's achievability bound of a system limited to stop feedback. This
paper significantly tightens the achievability bound by using a Markovian
analysis that leverages both the submartingale and Markov properties of the
transmitted message. Our new non-asymptotic lower bound on achievable rate lies
above Polyanskiy's bound and is close to the actual performance of the SED
encoder over the BSC.
