Achievable Error Exponents for Almost Fixed-Length M-Ary Hypothesis Testing

Abstract

We revisit multiple hypothesis testing and propose a two-phase test, where each phase is a fixed-length test and the second-phase proceeds only if a reject option is decided in the first phase. We derive achievable error exponents of error probabilities under each hypothesis and show that our two-phase test bridges over fixed-length and sequential tests in both Neyman-Pearson and Bayesian settings in the similar spirit of Lalitha and Javidi [1] for binary hypothesis testing. Specifically, our test may achieve the performance close to a sequential test with the asymptotic complexity of a fixed-length test and such test is named the almost fixed-length test. Our results generalize the design and analysis of the almost fixed-length test for binary hypothesis testing to account for more than two outcomes.