Redundancy of Markov Family with Unbounded Memory

02/01/2018

∙

by   Changlong Wu, et al.

∙

0

∙

share

We study the redundancy of universally compressing strings X_1,..., X_n generated by a binary Markov source p without any bound on the memory. To better understand the connection between compression and estimation in the Markov regime, we consider a class of Markov sources restricted by a continuity condition. In the absence of an upper bound on memory, the continuity condition implies that p(X_0|X^-1_-m) gets closer to the true probability p(X_0|X_-∞^-1) as m increases, rather than vary around arbitrarily. For such sources, we prove asymptotically matching upper and lower bounds on the redundancy. In the process, we identify what sources in the class matter the most from a redundancy perspective.