F. Kanaya et J. Muramatsu, AN ALMOST SURE RECURRENCE THEOREM WITH DISTORTION FOR STATIONARY ERGODIC SOURCES, IEICE transactions on fundamentals of electronics, communications and computer science, E80A(11), 1997, pp. 2264-2267
Let (X-k)(k=-infinity)(infinity) be a stationary and ergodic informati
on source, where each X-k takes values in a standard alphabet A with a
distance function d: A x A --> [0, infinity) defined on it. For each
sample sequence x = (...,x(-1),x(0),x(1),...) and D > 0 let the approx
imate D-match recurrence time be defined by R-n(x, D) = min(m greater
than or equal to n : d(n)(X-1(n), X-m+1(m+n)) less than or equal to D}
where X-i(j) denotes the string x(i)x(i+1) ... x(j) and d(n) : A(n) x
A(n) --> [0, infinity) is a metric of A(n) induced by d for each n. L
et R(D) be the rate distortion function of the source (X-k)(k=-infinit
y)(infinity) relative to the fidelity criterion (d(n)). Then it is sho
wn that lim sup(n-->infinity) 1/n log R-n (X, D) less than or equal to
R(D/2) a.s.