A Linear Programming Approach to Sequential Hypothesis Testing

Abstract

Under some mild Markov assumptions it is shown that the problem of designing optimal sequential tests for two simple hypotheses can be formulated as a linear program. This result is derived by investigating the Lagrangian dual of the sequential testing problem, which is an unconstrained optimal stopping problem depending on two unknown Lagrangian multipliers. It is shown that the derivative of the optimal cost function, with respect to these multipliers, coincides with the error probabilities of the corresponding sequential test. This property is used to formulate an optimization problem that is jointly linear in the cost function and the Lagrangian multipliers and can be solved for both with off-the-shelf algorithms. To illustrate the procedure, optimal sequential tests for Gaussian random sequences with different dependency structures are derived, including the Gaussian AR(1) process.

Keywords:

• Discrete-time Markov process
• Linear programming
• Optimal sequential test
• Optimal stopping
• Sequential hypothesis testing
• Two simple hypotheses

Subject Classifications:

• 62L10
• 62L15
• 90C05

ACKNOWLEDGMENTS

The authors thank the anonymous reviewer and the editor for their time and effort.

Notes

A stopping rule is said to be truncated, if it is guaranteed to stop after at most N time instances; that is, if an integer N ≥ 1 exists such that P(τ ≤N) = 1.

Recommended by Nitis Mukhopadhyay

Color versions of one or more of the figures in the article can be found online at http://www.tandfonline.com/lsqa.