Convergence of Binarized Context-tree Weighting for Estimating Distributions of Stationary Sources
Badri N. Vellambi, Marcus Hütter · 2018
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 (CTW) 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 CTW algorithm is a consistent estimator of the stationary distribution, and that the worst-case L1-prediction error between the CTW and frequency estimates using n source symbols each of which when binarized consists of k > 1 bits decays as Θ(√{2k[logn/n]})·.