Information theoretical aspects of hidden Markov processes

Abstract

The primary concerns of this thesis are some information theoretical proper- ties of hidden Markov processes. From an information theoretical perspective, a hidden Markov process is often viewed as a Markov chain observed through a discrete memoryless channel. Since information sources with memory are often modelled as Markov chains, hidden Markov processes are of particular interest both in theory and application. The first part of this thesis is devoted to the R ́enyi entropy rate of hidden Markov processes. In 1960, the R ́enyi entropy was introduced as a generalization of the Shannon entropy and the R ́enyi entropy rate is similarly defined as the limit of the averaged R ́enyi entropy whenever this limit exists. As opposed to the Shannon entropy rate, which has been proved to exist for all stationary random processes, the well-definedness of the R ́enyi entropy rate for a general stationary process has been open for decades. In the first part of this thesis, a modified Bernstein blocking method is proposed to establish the existence of R ́enyi entropy rates for hidden Markov processes under certain assumptions. Furthermore, by constructing the Markov approximating sequence, it is proved that under mild conditions, the R ́enyi entropy rates for the approximating Markov processes con- verge exponentially to that of the original hidden Markov process, as the Markov order goes to infinity. The second part of this thesis focuses on the computation of the capacity for finite-state channels with Markovian inputs. In this case, the channel ca- pacity boils down to the maximum of the mutual information rate between the input Markov chain and the output hidden Markov process. However, the lack of an explicit expression for the mutual information rate renders classical de- scent methods inapplicable. In this part, a deterministic algorithm is proposed to handle this issue under mild concavity assumptions. Compared to some ran- domized algorithms proposed recently, this algorithm is simple enough to be carried out and proves to achieve exponential accuracy in exponential time. For some special channels as elaborated in this thesis, this algorithm achieves expo- nential accuracy in polynomial time. Finally, a non-trivial adjustment of this algorithm is also made to deal with the case when the concavity assumptions are not available. These two algorithms are supposed to be particularly useful to some optimization problems when the target functions are expressed as the limits of convergent sequences.