# Low-Cost Active Anomaly Detection with Switching Latency
## Appendix A Proof for Theorems
### The Expected Cumulative Cost of DMSC Policy
Then, on the assumption that \(s=0\), these three passage times can be defined as \(T_{1}^{k},T_{2}^{k},T_{3}^{k}\), where \(T_{1}^{k}\) is the last passage time when the process with the highest sum-LLRs is one of the abnormal processes for all \(n\geq T_{1}^{k}\) at stage \(k\); \(T_{2}^{k}\) is the time when the process with the highest sum-LLRs no longer changes for all \(n\geq T_{2}^{k}\); and \(T_{3}^{k}\) is the time when sufficient information for declaring the process \(m^{1}(n)\) as abnormal has been gathered, in another word, \(T_{3}^{k}\) is the time when the sum-LLRs of the process \(m^{1}(n)\) satisfies \(S_{m^{1}(n)}(n)\geq B\) for all \(t\geq T_{3}^{k}\). Hence, according to the definition of \(T_{2}^{k}\), the number of switchings \(N_{s}^{k}\) of a stage is upper bounded by the value of \(T_{2}^{k}\), i.e., \(N_{s}^{k}\leq T_{2}^{k}\) since the switchings occur only during the period from the beginning of the stage to \(T_{2}^{k}\). In addition, the number of observations is upper bounded by \(T_{3}^{k}\) according to the definition of \(T_{3}^{k}\). It should be noted that \(T_{1}^{k},T_{2}^{k},T_{3}^{k}\) are not stopping times, because they are associated with the future, and the decision-maker does not know whether they have arrived since the abnormal processes are unknown. Furthermore, these three last passage times are defined under the condition that the sampling is not stopped. In the following analysis, we say implemented indefinitely to indicate that the decision-maker probes the processes indefinitely. According to the definitions, \(T_{1}^{k}\) represents the earliest time such that process \(m^{1}(n)\) is an abnormal process for all \(n\geq T_{1}^{k}\) in each stage. In addition, it has been proved that \(T_{1}^{k}\) is sufficiently small with high probability (26, Lemma 2) and there exist \(D>0\) and \(\gamma>0\) such that  
\[P(T_{1}^{k}>n)\leq De^{-\gamma n}. \tag{12}\]  
In addition, \(T_{2}^{k}\) is the earliest time such that process \(m^{1}(n)\) no longer changes for all \(n\geq n_{2}^{k}\). We introduce \(n_{2}^{k}\triangleq T_{2}^{k}-T_{1}^{k}\) which denotes the total amount of time between \(T_{1}^{k}\) and \(T_{2}^{k}\). The following lemma shows that \(P(n_{2}^{k})\) decreases exponentially with \(n\). **Lemma 2**. : _Assume that the DMSC is in Case I and is implemented indefinitely. Then, there exist \(D>0\) and \(\gamma>0\) such that_\[P(n_{2}^{k}>n)\leq De^{-\gamma n}\]  
_for each \(k=1,2,...,L\)._  
**Proof. ** Define  
\[\tilde{l}_{m}(n)= \begin{cases}l_{m}(n)-D(g||f),&\text{if process $m$ is abnormal,}\\ l_{m}(n)+D(f||g),&\text{if process $m$ is normal,}\end{cases}  \tag{10}\]  
thus \(E(\tilde{l}_{m}(n))=0\). Note that,  
\[ \begin{split}& P(n_{2}^{k}>n)\\ \leq& P\left(\sup_{l\geq n}S_{m^{2}(t)}(t)-(S_{m^{1}(t)}(t )+l_{m^{1}(t)}(t+1))\geq 0\right)\\ \leq&\sum_{t=n}^{\infty}P\Big{(}S_{m^{2}(t)}(t)-S_{m^{1}(t )}(t)-\tilde{l}_{m^{1}(t)}(t+1)\geq D(g||f)\Big{)}\\ \leq&\sum_{t=n}^{\infty}E\left(\varepsilon^{s(S_{m^{2}(t)}(t) -S_{m^{1}(t)}(t)-\tilde{l}_{m^{1}(t)}(t+1)-\varepsilon)}\right)\cdot e^{-s(D( g||f)-\varepsilon)}\end{split}  \tag{11}\]  
for all \(s>0\) and \(0<\epsilon<D(g||f)\). The last inequality follows by applying the Chernoff bound for each term in the summation. Since \(E\Big{(}S_{m^{2}(t)}(t)-S_{m^{1}(t)}(t)-\tilde{l}_{m^{1}(t)}(t+1)-\epsilon \Big{)}\leq-\epsilon<0\) is strictly negative, differentiating the MGFs of \(S_{m^{2}(t)}(t)-S_{m^{1}(t)}(t)-\tilde{l}_{m^{1}(t)}(t+1)-\epsilon\) with respect to \(s\) yields strictly negative derivatives at \(s=0\). Hence, there exist \(s^{\prime}>0\) and \(\gamma^{\prime}>0\) such that \(E\Big{(}S_{m^{2}(t)}(t)-S_{m^{1}(t)}(t)-\tilde{l}_{m^{1}(t)}(t+1)-\epsilon \Big{)}\) and \(e^{-s(D(g||f)-\epsilon)}\) are strictly less than \(e^{-\gamma^{\prime}t}<1\). Therefore, there exist \(D>0\) and \(\gamma>0\) such that  
\[