Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLow and Upper Bound of Approximate Sequence for the Entropy Rate of Binary Hidden Markov Processes
454
0
0.0
(
0
)
Added by
Shuangping Chen
Publication date
2011
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In the paper, the approximate sequence for entropy of some binary hidden Markov models has been found to have two bound sequences, the low bound sequence and the upper bound sequence. The error bias of the approximate sequence is bound by a geometric sequence with a scale factor less than 1 which decreases quickly to zero. It helps to understand the convergence of entropy rate of generic hidden Markov models, and it provides a theoretical base for estimating the entropy rate of some hidden Markov models at any accuracy.
rate research
Read More
Recently, Samorodnitsky proved a strengthened version of Mrs. Gerbers Lemma, where the output entropy of a binary symmetric channel is bounded in terms of the average entropy of the input projected on a random subset of coordinates. Here, this result is applied for deriving novel lower bounds on the entropy rate of binary hidden Markov processes. For symmetric underlying Markov processes, our bound improves upon the best known bound in the very noisy regime. The nonsymmetric case is also considered, and explicit bounds are derived for Markov processes that satisfy the $(1,infty)$-RLL constraint.
While two hidden Markov process (HMP) resp. quantum random walk (QRW) parametrizations can differ from one another, the stochastic processes arising from them can be equivalent. Here a polynomial-time algorithm is presented which can determine equivalence of two HMP parametrizations $cM_1,cM_2$ resp. two QRW parametrizations $cQ_1,cQ_2$ in time $O(|S|max(N_1,N_2)^{4})$, where $N_1,N_2$ are the number of hidden states in $cM_1,cM_2$ resp. the dimension of the state spaces associated with $cQ_1,cQ_2$, and $S$ is the set of output symbols. Previously available algorithms for testing equivalence of HMPs were exponential in the number of hidden states. In case of QRWs, algorithms for testing equivalence had not yet been presented. The core subroutines of this algorithm can also be used to efficiently test hidden Markov processes and quantum random walks for ergodicity.
Distributed arithmetic coding (DAC) has been shown to be effective for Slepian-Wolf coding, especially for short data blocks. In this letter, we propose to use the DAC to compress momery-correlated sources. More specifically, the correlation between sources is modeled as a hidden Markov process. Experimental results show that the performance is close to the theoretical Slepian-Wolf limit.
The rate-distortion dimension (RDD) of an analog stationary process is studied as a measure of complexity that captures the amount of information contained in the process. It is shown that the RDD of a process, defined as two times the asymptotic ratio of its rate-distortion function $R(D)$ to $log {1over D}$ as the distortion $D$ approaches zero, is equal to its information dimension (ID). This generalizes an earlier result by Kawabata and Dembo and provides an operational approach to evaluate the ID of a process, which previously was shown to be closely related to the effective dimension of the underlying process and also to the fundamental limits of compressed sensing. The relation between RDD and ID is illustrated for a piecewise constant process.
Two maximization problems of Renyi entropy rate are investigated: the maximization over all stochastic processes whose marginals satisfy a linear constraint, and the Burg-like maximization over all stochastic processes whose autocovariance function begins with some given values. The solutions are related to the solutions to the analogous maximization problems of Shannon entropy rate.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
