Redundancy of the Krichevsky–Trofimov estimator with a finite window for a Markov source

✍ Scribed by Tsutomu Kawabata; Naohisa Tasaki

• Publisher: John Wiley and Sons
• Year: 2000
• Tongue: English
• Weight: 223 KB
• Volume: 83
• Category: Article
• ISSN: 1042-0967
• DOI: 10.1002/(sici)1520-6440(200011)83:11<56::aid-ecjc6>3.0.co;2-l

✦ Synopsis

The KrichevskyTrofimov estimator can be implemented as an arithmetic data compressor based on a finite window. We analyze the redundancy of this estimator for the Markov source of finite order. The per-letter redundancy behaves with near certainty as (the number of effective states) u (alphabet size)/2 (window size) when the window size is large. Our analysis applies the renewal theory.