  We consider a class of small-sample distribution estimators over noisy
channels. Our estimators are designed for repetition channels, and rely on
properties of the runs of the observed sequences. These runs are modeled via a
special type of Markov chains, termed alternating Markov chains. We show that
alternating chains have redundancy that scales sub-linearly with the lengths of
the sequences, and describe how to use a distribution estimator for alternating
chains for the purpose of distribution estimation over repetition channels.
