Variance estimators for the Lempel-Ziv entropy rate estimator

Lempel and Ziv's 1976 algorithm provides an easy-to-compute way to automatically estimate the entropy rate for symbolic time series, requiring no free parameters. Here we derive an analytical variance estimate for the Lempel-Ziv entropy rate estimator that is easily computable from observations with negligible extra effort beyond the entropy rate itself, and compare to another procedure, a time-series-based bootstrap method. These provide a justified "error bar" quantifying the size of expected fluctuations on the estimate itself, given by the single time series of symbols.