Erasure entropy rate differs from Shannon's entropy rate in that the conditioning occurs with respect to both the past and the future, as opposed to only the past (or the future). In this paper, consistent universal algorithms for estimating erasure entropy rate are proposed based on the basic and extended context-tree weighting (CTW) algorithms. Simulation results for those algorithms applied to Markov sources, tree sources, and English texts are compared to those obtained by fixed-order plug-in estimators with different orders.

A sourceXgoes through an erasure channel whose output isZ. The goal is to compress losslesslyXwhen the compressor knowsXandZand the decompressor knowsZ. We propose a universal algorithm based on context-tree weighting (CTW), parameterized by a memory-length parameter. We show that if the erasure channel is stationary and memoryless, andXis stationary and ergodic, then the proposed algorithm achieves a compression rate ofH(X0|X-l-1,Zl) bits per erasure.

Erasure entropy rate (introduced recently by Verdu and Weissman) differs from Shannon's entropy rate in that the conditioning occurs with respect to both the past and the future, as opposed to only the past (or the future). In this paper, universal algorithms for estimating erasure entropy rate are proposed based on the basic and extended context-tree weighting (CTW) algorithms. Consistency results are shown for those CTW based algorithms. Simulation results for those algorithms applied to Markov sources, tree sources and English texts are compared to those obtained by fixed-order plug-in estimators with different orders. An estimate of the erasure entropy of English texts based on the proposed algorithms is about 0.22 bits per letter, which can be compared to an estimate of about 1.3 bits per letter for the entropy rate of English texts by a similar CTW based algorithm

We develop adaptive schemes for bidirectional modeling of unknown discrete stationary sources. These algorithms can be applied to statistical inference problems such as noncausal universal discrete denoising that exploit bidirectional dependencies. Efficient algorithms for constructing those models are developed and we compare their performance to that of the DUDE algorithm for universal discrete denoising