Some remarks on the finite-memory K-hypotheses problems

Abstract

Finite-memory statistical problems typically deal with the situation where the class of statistics is restricted to those taking on a fixed finite number of values. Although a potentially infinite number of samples may be available the statistician is allowed to base his inference only on the current value of such a statistic -- the current state of his finite memory. This is the case for instance when the inference is to be performed by a small size computer. During the past several years a number of results have been obtained concerning a two-hypotheses finite-memory problem. In this report we consider some aspects of the case where the number of hypotheses is greater than two. In particular we derive a bound on the error probability for the 3-hypothesis case, present a counterexample to a recently proposed conjecture and briefly discuss a finite-memory version of the minimax theorem. We also include two appendices containing some results on finite Markov chains. (Author)