View PDF HTML (experimental)

Abstract:Quickest change detection concerns estimation of an unknown change time $\tau_a$ from a sequence of partial observations $\{Y_k:k\ge 0\}$. We consider stopping rules of CUSUM form, $$ X_{n+1}
=
\max\{0,X_n+F(Y_{n+1})\},
\qquad
\tau_s=\min\{n\ge 0:X_n\ge \textrm{H}\}, $$ where the function $F$ and threshold $\textrm{H}$ are design parameters.
The observations and change time are modeled jointly through a hidden Markov model, and $ F$ is selected from a prescribed function class $\Psi$ to minimize the weighted criterion $$
\textsf{E}\bigl[
(\tau_s-\tau_a)_+
+
\kappa(\tau_s-\tau_a)_-
\bigr]. $$ When $\Psi$ is a linear function class, the optimizer $F^*$ is characterized by a convex program, whose dual yields extensions of classical likelihood-ratio constructions. This conclusion is based on analysis that is asymptotic in the regime $\kappa\to\infty$. We show that the hidden Markov model admits an asymptotically equivalent conditionally independent approximation of the type commonly used in the quickest change detection literature. We then develop the design and asymptotic theory for a substantially broader class of conditionally independent models, so that the resulting conclusions are not tied to the particular POMDP reduction.
Combining renewal theory and large deviations for reflected random walks, we obtain for each $F\in\Psi$ asymptotically accurate approximations of the optimal threshold and average cost, with error vanishing as $\kappa\to\infty$. Numerical experiments show that the resulting approximations remain accurate for moderate values of $\kappa$.

Submission history

From: Sean Meyn [view email]
[v1] Thu, 12 Sep 2024 11:19:07 UTC (388 KB)
[v2] Tue, 28 Jul 2026 20:31:30 UTC (3,556 KB)