On the optimal asymptotic performance of universal ordering and discrimination of individual sequences
M.J. Weinberger, J. Ziv, Abraham Lempel · 2002
The authors consider the problem of ordering of strings of a fixed length over a discrete alphabet, according to decreasing probabilities of having been emitted by an unknown finite-state source. Data compression is applied to derive a universal algorithm that solves this problem with an optimal asymptotic performance. The result is applied to discriminate an individual sequence as emitted by an i.i.d. random source or as a signal corrupted by noise. Tight lower and upper bounds on the asymptotic performance of finite-state discriminators are given.>