Finite-memory classification of Bernoulli sequences using reference samples (Corresp.)

It is shown that in two-way Bernoulli classification problems deterministic machines can perform as well as optimal randomized machines if their memory is increased by less than one bit. This is accomplished by allowing the algorithm to observe samples from both classes, thus in effect using the data source itself to provide the necessary randomization. An application to a simple communication problem is indicated.