Exact solution of the hidden Markov processes

We write a master equation for the distributions related to hidden Markov processes (HMPs) and solve it using a functional equation. Thus the solution of HMPs is mapped exactly to the solution of the functional equation. For a general case the latter can be solved only numerically. We derive an exact expression for the entropy of HMPs. Our expression for the entropy is an alternative to the ones given before by the solution of integral equations. The exact solution is possible because actually the model can be considered as a generalized random walk on a one-dimensional strip. While we give the solution for the two second-order matrices, our solution can be easily generalized for the $L$ values of the Markov process and $M$ values of observables: We should be able to solve a system of $L$ functional equations in the space of dimension $M-1$.

Figure 1

Entropy of the hidden Markov model versus the matrix parameter $a$ for the matrices $q_{11}=a$, $q_{22}=0.45$, $q_{21}=1-q_{11}$, $q_{12}=1-q_{22}$, ${\pi }_{11}=0.9$, ${\pi }_{21}=1-{\pi }_{11}$, ${\pi }_{22=0.8}$, and ${\pi }_{12}=1-{\pi }_{22}$, where $q_{ij}$ are the transition probabilities of the Markov model, while $q_{11}$ and $q_{22}$ are the probabilities of the correct observations. The solid line corresponds to Eq. (26), given by the solution of Eq. (22), using the numerical algorithm via Eq. (27) and $N=1000$. The closed circles correspond to the stochastic numerics for ${10}^6$ trials. The results derived by two methods coincide with the accuracy $\sim 0.0005$.