Recurrence times and pointwise lower bounds in data compression
P. Algoet · 2002
Let {X/sub t/} be a stationary ergodic process with values in a finite alphabet /spl Xscr/. For s/spl les/t let X/sub s//sup t/=(X/sub s/,...,X/sub t/). The first recurrence time of X/sup k/=(X/sub 0/,...,X/sub k-l/ is defined as the number of shifts back until X/sup 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.