New bounds on the entropy rate of hidden Markov processes

Let {X_t} be a stationary finite-alphabet Markov chain and {Z_t} denote its noisy version when corrupted by a discrete memoryless channel. Let P(X_t∈·|Z_-∞^t) denote the conditional distribution of X_t given all past and present noisy observations, a simplex-valued random variable. We present a new approach to bounding the entropy rate of {Z_t} by approximating the distribution of this random variable. This approximation is facilitated by the construction and study of a Markov process whose stationary distribution determines the distribution of P(X_t∈·|Z_-∞^t). To illustrate the efficacy of this approach, we specialize it and derive concrete bounds for the case of a binary Markov chain corrupted by a binary symmetric channel (BSC). These bounds are seen to capture the behavior of the entropy rate in various asymptotic regimes.