Properties of Jeffreys Mixture for Markov Sources

• Published in: IEEE transactions on information theory 2013-01, Vol.59 (1), p.438-457
• Main Authors: Takeuchi, J., Kawabata, T., Barron, A. R.
• Format: Article
• Language: English
• Subjects: Applied sciences; Approximation; Approximation methods; Asymptotic properties; Bayes code; Coding, codes; Context; Data compression; Encoding; Exact sciences and technology; Information theory; Information, signal and communications theory; Jeffreys prior; Markov analysis; Markov models; Markov processes; Mathematical analysis; Mathematical models; Maximum likelihood estimation; minimax regret; Minimax technique; Monte Carlo simulation; Probability; Signal and communications theory; stochastic complexity; Strategy; Telecommunications and information theory; universal source coding; Upper bound; Vectors
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2012.2219171

We discuss the properties of Jeffreys mixture for a Markov model. First, we show that a modified Jeffreys mixture asymptotically achieves the minimax coding regret for universal data compression, where we do not put any restriction on data sequences. Moreover, we give an approximation formula for the prediction probability of Jeffreys mixture for a Markov model. By this formula, it is revealed that the prediction probability by Jeffreys mixture for the Markov model with alphabet {0,1} is not of the form ( nx | s +α)/( ns +β), where nx | s is the number of occurrences of the symbol x following the context s ∈ {0,1} and ns = n 0| s + n 1| s . Moreover, we propose a method to compute our minimax strategy, which is a combination of a Monte Carlo method and the approximation formula, where the former is used for earlier stages in the data, while the latter is used for later stages.