The effects of randomization on finite-memory decision schemes
- 1 July 1972
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 18 (4) , 499-502
- https://doi.org/10.1109/tit.1972.1054846
Abstract
This paper is concerned with the differences between deterministic and randomized finite-memory decision rules. It is shown that for any hypothesis-testing problem there exists a b < CO such that, for any B, the optimal deterministic rule with B + b bits in memory has a lower error probability than the optimal randomized rule with B bits in memory. Suboptimal deterministic rules with this property are de- monstrated. These deterministic rules lose at most b bits. Thus for large memories the fraction of memory, measured in bits, lost by deterministic rules is negligible.Keywords
This publication has 5 references indexed in Scilit:
- On Memory Saved by RandomizationThe Annals of Mathematical Statistics, 1971
- Reply to 'Finite memory hypothesis testing - Comments on a critique' by Cover, T.M., and Hellman, M.E.IEEE Transactions on Information Theory, 1971
- Finite-memory hypothesis testing--Comments on a critique (Corresp.)IEEE Transactions on Information Theory, 1970
- Finite-memory hypothesis testing--A critique (Corresp.)IEEE Transactions on Information Theory, 1970
- Learning with Finite MemoryThe Annals of Mathematical Statistics, 1970