  Inference in hidden Markov model has been challenging in terms of scalability
due to dependencies in the observation data. In this paper, we utilize the
inherent memory decay in hidden Markov models, such that the forward and
backward probabilities can be carried out with subsequences, enabling efficient
inference over long sequences of observations. We formulate this forward
filtering process in the setting of the random dynamical system and there exist
Lyapunov exponents in the i.i.d random matrices production. And the rate of the
memory decay is known as $\lambda_2-\lambda_1$, the gap of the top two Lyapunov
exponents almost surely. An efficient and accurate algorithm is proposed to
numerically estimate the gap after the soft-max parametrization. The length of
subsequences $B$ given the controlled error $\epsilon$ is
$B=\log(\epsilon)/(\lambda_2-\lambda_1)$. We theoretically prove the validity
of the algorithm and demonstrate the effectiveness with numerical examples. The
method developed here can be applied to widely used algorithms, such as
mini-batch stochastic gradient method. Moreover, the continuity of Lyapunov
spectrum ensures the estimated $B$ could be reused for the nearby parameter
during the inference.
