Relationship among Complexities of Individual Sequences over Countable Alphabet

Shigeaki KUZUOKA  Tomohiko UYEMATSU  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E89-A   No.7   pp.2047-2055
Publication Date: 2006/07/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e89-a.7.2047
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Information Theory
Keyword: 
empirical entropy,  individual sequence,  Lempel-Ziv algorithm,  universal source coding,  

Full Text: PDF>>
Buy this Article




Summary: 
This paper investigates some relations among four complexities of sequence over countably infinite alphabet, and shows that two kinds of empirical entropies and the self-entropy rate regarding a Markov source are asymptotically equal and lower bounded by the maximum number of phrases in distinct parsing of the sequence. Some connections with source coding theorems are also investigated.