  A decision maker records measurements of a finite-state Markov chain
corrupted by noise. The goal is to decide when the Markov chain hits a specific
target state. The decision maker can choose from a finite set of sampling
intervals to pick the next time to look at the Markov chain. The aim is to
optimize an objective comprising of false alarm, delay cost and cumulative
measurement sampling cost. Taking more frequent measurements yields accurate
estimates but incurs a higher measurement cost. Making an erroneous decision
too soon incurs a false alarm penalty. Waiting too long to declare the target
state incurs a delay penalty. What is the optimal sequential strategy for the
decision maker? The paper shows that under reasonable conditions, the optimal
strategy has the following intuitive structure: when the Bayesian estimate
(posterior distribution) of the Markov chain is away from the target state,
look less frequently; while if the posterior is close to the target state, look
more frequently. Bounds are derived for the optimal strategy. Also the
achievable optimal cost of the sequential detector as a function of transition
dynamics and observation distribution is analyzed. The sensitivity of the
optimal achievable cost to parameter variations is bounded in terms of the
Kullback divergence. To prove the results in this paper, novel stochastic
dominance results on the Bayesian filtering recursion are derived. The
formulation in this paper generalizes quickest time change detection to
consider optimal sampling and also yields useful results in sensor scheduling
(active sensing).
