ON THE ASYMPTOTIC BEHAVIORS OF THE RECURRENCE TIME WITH FIDELITY-CRITERION FOR DISCRETE MEMORYLESS SOURCES AND MEMORYLESS GAUSSIAN SOURCES

The asymptotic behavior of the recurrence time with fidelity criterion is discussed. Let X = {X-i}(i=0)(infinity) be a source and Y = {Y-i}( i=-infinity)(-1) a database. For a Delta > 0 and an integer I > 0 defi ne N-l([B])(Y, X, Delta) as the minimum integer N satisfying d(l)(X-0( l-1), Y(-(N+1)l)(-Nl-1)) less than or equal to Delta subject to a fide lity criterion d(l). In this paper the following two i.i.d. cases are considered: (A) X-i similar to P and Y-i similar to Q, where P and Q a re probability distributions on a finite alphabet, and (B) X-i similar to N(0, 1) and Y-i similar to N(0, 1). In case (A) it is proved that 1/l log(2) N-l([B]) (Y, X, Delta) almost surely converges to a certain constant determined by P, Q and Delta as 1 --> infinity. The Kac's le mma plays an important role in the proof on the convergence. Tn case ( B) it is shown that there is a quantity related to 1/l log(2) N-l([B]) (Y, X, Delta) that converges to the rate-distortion bound in almost s ure sense.