Recurrence times and pointwise lower bounds in data compression

Let {X_t} be a stationary ergodic process with values in a finite alphabet 𝒳. For s⩽t let X_s^t=(X _s,...,X_t). The first recurrence time of X^k =(X₀,...,X_k-l is defined as the number of shifts back until X^k appears again. We give a simple proof using a lemma developed by Algoet and Cover (1985) to prove the asymptotic optimality of log-optimum selections in convex families