Alternating Markov chains for distribution estimation in the presence of errors

摘要

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 special types 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.