An Almost Sure Recurrence Theorem with Distortion for Stationary Ergodic Sources


IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E80-A   No.11   pp.2264-2267
Publication Date: 1997/11/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section LETTER (Special Section on Information Theory and Its Applications)
Category: Source Coding/Channel Capacity
stationary ergodic sources,  sample sequence,  recurrence time,  approximate string match,  rate distortion function,  

Full Text: PDF>>
Buy this Article

Let {Xk}k=- be a stationary and ergodic information source, where each Xk takes values in a standard alphabet A with a distance function d: A A [0, ) defined on it. For each sample sequence X = (, x-1, x0, x1, ) and D > 0 let the approximate D-match recurrence time be defined by Rn (x, D) = min {m n: dn (Xn1, Xm+nm+1) D}, where Xji denotes the string xixi+1 xj and dn: An An [0, ) is a metric of An induced by d for each n. Let R (D) be the rate distortion function of the source {Xk}k=- relative to the fidelity criterion {dn}. Then it is shown that lim supn-1/n log Rn (X, D) R (D/2) a. s.