7 - Computing entropy rates for hidden Markov processes

Summary

Abstract. In this article we want to show how certain analytic techniques from dynamical systems, and more particularly thermodynamics, can be used to give new explicit formulae for entropy rates for certain hidden Markov processes. As a byproduct, the method gives potentially very accurate numerical approximations to the entropy rate.

Introduction

We want to describe an approach to studying entropy rates for certain hidden Markov processes. Our motivation for studying this problem comes from a previous approach to Lyapunov exponents for random matrix products, which we shall also briefly describe. We were first introduced to the connection between Lyapunov exponents and entropy rates by the article of Jacquet et al. [8]. However, there is a close analogy which probably dates back as far as the work of Furstenberg [3] and Blackwell [1]. They studied Lyapunov exponents and entropy rates, respectively, by considering associated stationary measures. For simplicity, we shall restrict ourselves to the specific case of binary symmetric channels with noise. However, there is scope for generalizing this method to more general settings.

Our aim is to present new explicit formulae for the entropy rates and, thus, by suitable approximations, give an algorithm for the explicit computation. The usual techniques for studying entropy rates tend to give algorithms which give exponential convergence (reflecting the use of positive matrices and associated transfer operators). The techniques we describe typically lead to a faster super-exponential convergence.