Universality of e-detectors for ARL control

Abstract

An e-detector for a pre-change class $\mathcal{P}$ is a nonnegative process $M$ such that ${\mathbb{E}}_P[M_{\tau }]\le {\mathbb{E}}_P[\tau ]$ for all stopping times $\tau$ and all $P\in \mathcal{P}$. Thresholding e-detectors controls the average run length (ARL): declaring a change at the first time $T_b$ when $M$ crosses $b$ ensures that ${\inf }_{P\in \mathcal{P}}{\mathbb{E}}_P[T]\ge b$. But e-detectors do substantially more than control the ARL; they also satisfy a \emph{optional-horizon inequality}: \[ P(T_b\leqσ)\leq \mathbb E_P[σ]/b \] for every data-dependent stopping time (monitoring horizon) \(σ\) and $P\in \mathcal{P}$. In particular, every e-detector-based procedure obeys $P(T\le t)\le t/b$ at each fixed $t$, thus avoiding early false alarms. Remarkably, the converse also holds: every stopping time $T$ that satisfies the optional-horizon inequality must in fact arise from thresholding an e-detector. We also derive a universal representation of stopping times that satisfy (only) ARL control. These are represented by \emph{weak} e-detectors, that only require ${\mathbb{E}}_P[M_{\tau }]\le {\mathbb{E}}_P[\tau ]$ to hold at all threshold stopping times $T_b$. Appendices present universal representations for other (less common) change detection metrics.

47 pages