Convergence of Binarized Context-tree Weighting for Estimating Distributions of Stationary Sources

Abstract

This work investigates the convergence rate of learning the stationary distribution of finite-alphabet stationary ergodic sources using a binarized context-tree weighting approach. The binarized context-tree weighting (overline mathbf Cmathbf Tmathbf W) algorithm estimates the stationary distribution of a symbol as a product of conditional distributions of each component bit, which are determined in a sequential manner using the well known binary context-tree weighting method. We establish that overline mathbf Cmathbf Tmathbf W algorithm is a consistent estimator of the stationary distribution, and that the worst-case L- 1 -prediction error between the overline pmb text CTW and frequency estimates using n source symbols each of which when binarized consists of k > 1 bits decays as Θleft(sqrt 2 kfrac log n nright) · Show more