.Let $\{X_t\}$ be a stationary finite-alphabet Markov chain and $\{Z_t\}$ denote its noisy version when corrupted by a discrete memoryless channel. $\{Z_t\}$, known as a hidden Markov process, arises in many contexts both as an information source, and as noise. Notwithstanding its simple characterization in terms of the state-to-state and the channel transition probabilities, little is known about the entropy rate of $\{Z_t\}$ (key to the most basic questions in data compression and communications).

We present a new approach to bounding the entropy rate of $\{Z_t\}$ by the construction and study of a closely related Markov process. Our approach leads to bounds that are sufficiently tight to characterize the behavior of the entropy rate in various asymptotic regimes. These bounds are particularly easy to obtain in regimes that exhibit a ``concentration of the support'' (a property that will be explained), such as the `high SNR', `low SNR', and `weak dependence' regimes.

Asymptotics of the entropy rate are obtained also in regimes that lack this concentration property by appealing to the constructed Markov process, but via a more delicate study of its dynamics. The `rare transitions' regime is one such example.

As a bonus, our analysis also gives rise to a deterministic algorithm for approximating the entropy rate, achieving the best known precision-complexity tradeoff.

The talk is based on joint work with Erik Ordentlich. Results for the `rare transitions' regime are joint also with Chandra Nair.