Stationary entrophy estimation via string matching
Ioannis Kontoyiannis, Yuri Suhov · 2002
We prove an asymptotic relationship between certain longest match-lengths along a single realization of a stationary process and its entropy rate: Given a process X={X/sub n/;n/spl isin/Z} and a realization x from X, we define A/sub i//sup N/(x) as the length of the shortest substring, starting at x/sub i/, that does not appear as a contiguous substring of (x/sub i-N/,x/sub i-N+1/,...,x/sub i-1/). We consider stationary, ergodic processes that have a discrete (finite or infinite) alphabet and also satisfy the Doeblin condition (Kontoyiannis and Suhov, 1994).