DocumentCode
1538008
Title
The asymptotic redundancy of Bayes rules for Markov chains
Author
Atteson, Kevin
Author_Institution
Dept. of Biol., Yale Univ., New Haven, CT, USA
Volume
45
Issue
6
fYear
1999
fDate
9/1/1999 12:00:00 AM
Firstpage
2104
Lastpage
2109
Abstract
We derive the asymptotics of the redundancy of Bayes rules for Markov chains of fixed order over a finite alphabet, extending the work of Barron and Clarke (1990) on independent and identically distributed (i.i.d.) sources. The asymptotics are derived when the actual source is the class of φ-mixing sources which strictly includes Markov chains. These results can be used to derive minimax asymptotic rates of convergence for universal codes when a Markov chain of fixed order is used as a model
Keywords
Bayes methods; Markov processes; codes; convergence of numerical methods; minimax techniques; φ-mixing sources; Bayes rules; asymptotic redundancy; finite alphabet; fixed order Markov chains; i.i.d. sources; independent identically distributed sources; minimax asymptotic convergence rates; universal codes; Convolutional codes; Decoding; Error probability; Information geometry; Information theory; Linear code; Mathematics; Redundancy; Reliability theory; Viterbi algorithm;
fLanguage
English
Journal_Title
Information Theory, IEEE Transactions on
Publisher
ieee
ISSN
0018-9448
Type
jour
DOI
10.1109/18.782149
Filename
782149
Link To Document