Together with µ$_{0}$ ( { 0 } ) = q$_{0}$ , we have µ$_{0}$ ∈ Λ$_{0}$( γ, q$_{0}$ ) , i.e., Λ$_{0}$( γ, q$_{0}$ ) is closed, and the compactness of Λ$_{0}$( γ, q$_{0}$ ) then follows. Now P$_{X}$ can be proved to be discrete by following the same development as in the proof of Theorem 1 with Lemma 1 substituted by Lemma 7. Because P$_{X}$ is the stationary distribution of the Markov process, the maximum of the lower bound L ( · ) is achieved by a discrete first-order Markov process. Based on Theorem 2, in order to find the lower bound of the capacity, we can maximize L ( µ ) and obtain an optimized discrete first-order Markov input µ ∗ = {X , α, β, P$_{X}$ } in Λ( γ, q, c ) . Let µ$_{0}$ denote the capacity-achieving distribution, then In Section VI-A, we develop a computationally efficient scheme to determine µ $^{∗}$, which is a good approximation of the capacity-achieving input µ$_{0}$ . A. Computation of the entropy of Hidden Markov Processes VI. NUMERICAL METHODS AND RESULTS In order to numerically calculate the mutual information (85), it is important to compute the differ- ential entropy rate of a HMP generated by Markov input through the AWGN channel. Computing the (differential) entropy rate of HMPs is a hard problem. Most works in this area focus on the entropy rate of the binary Markov input through various channels. Reference [22] solves a linear system for the stationary distribution of the quantized Markov process to obtain a good approximation of the entropy rate for the HMP output generated by binary Markov input through a binary symmetric channel. In [23], the entropy rate of HMP generated by binary-symmetric Markov input through arbitrary memoryless channels is studied and a numerical method is presented based on quantizing a fixed-point functional equation. Based on these existing studies, a Monte Carlo algorithm is provided in this paper to compute the differential entropy rate of HMPs generated from a m -state Markov chain ( m ≥ 3 ) through the AWGN channel. We sketch the main ideas in our algorithm for computing the differential entropy rate in this subsection. Based on Blackwell’s work [24], the entropy of HMPs can be expressed as an expectation on the distribution of the conditional distribution of X$_{0}$ given the past observations Y 0 $_{−∞}$. In order to estimate 26 I ( µ$_{0}$ ) ≥ I ( µ $^{∗}$) ≥ L ( µ $^{∗}$) . (131)