Finite memory multiple hypothesis testing: Close-to-optimal schemes for Bernoulli problems
B. Chandrasekaran, Kiruthika Sri Lakshmanan · IEEE Transactions on Information Theory · 1978
The design of optimal, time-invariant, randomized, finite-state automata forK-hypothesis testing is an open problem forK > 2. A lower bound is constructed on the smallest probability of error achievable bym-state automata solving a three-hypothesis Bernoulli problem. A class of close-to-optimal automata is exhibited that requires at most one extra bit of memory to match the performnnce of an optimal automaton.