Faster sequential universal coding via block partitioning

Rissanen provided a sequential universal coding algorithm based on a block partitioning scheme, where the source model is estimated at the beginning of each block. This approach asymptotically approaches the entropy at the fastest possible rate of 1/2 log (n) bits per unknown parameter. We show that the complexity of this algorithm is Ω (n log (n)), which is comparable to existing sequential universal algorithms. We provide a sequential O(n log (log (n))) algorithm by modifying Rissanen's block partitioning scheme. The redundancy with our approach is greater than with Rissanen's block partitioning scheme by a multiplicative factor 1+ O (1/log(log (n))), hence it asymptotically approaches the entropy at the fastest possible rate.