Estimating the state of a Markov chain over a noisy communication channel: A bound and an encoder

We consider the problem of estimating the state of a Markov chain after N time units, when observed over a noisy communication channel. Specifically, a Markov chain is observed by an encoder. The encoder communicates with a decoder over the noisy communication channel. The past channel outputs are available causally to the encoder. The objective of the encoder is to maximize the mutual information between the state of the Markov chain after N time units, and the vector of channel outputs for N time units. We show that an outer bound on the reward under any encoding policy is N times the information-theoretic capacity of the noisy channel. We show that the optimal encoding scheme is a function of the current state of the Markov chain, and the a-posteriori distribution of the current state given all the past channel outputs. We describe a simple encoding scheme called posterior matching, which has desirable properties.