A QUICKEST DETECTION PROBLEM WITH FALSE NEGATIVES TIZIANO DE ANGELIS JHANVI GARG AND QUAN ZHOU Abstract. We formulate and solve a variant of the quickest detection problem which fea-

2025-04-27 0 0 1.44MB 35 页 10玖币

侵权投诉

A QUICKEST DETECTION PROBLEM WITH FALSE NEGATIVES

TIZIANO DE ANGELIS, JHANVI GARG, AND QUAN ZHOU

Abstract. We formulate and solve a variant of the quickest detection problem which fea-

tures false negatives. A standard Brownian motion acquires a drift at an independent expo-

nential random time which is not directly observable. Based on the observation in continuous

time of the sample path of the process, an optimizer must detect the drift as quickly as possi-

ble after it has appeared. The optimizer can inspect the system multiple times upon payment

of a ﬁxed cost per inspection. If a test is performed on the system before the drift has appeared

then, naturally, the test will return a negative outcome. However, if a test is performed after

the drift has appeared, then the test may fail to detect it and return a false negative with

probability ϵ∈(0,1). The optimisation ends when the drift is eventually detected. The

problem is formulated mathematically as an optimal multiple stopping problem, and it is

shown to be equivalent to a recursive optimal stopping problem. Exploiting such connection

and free boundary methods we ﬁnd explicit formulae for the expected cost and the optimal

strategy. We also show that when ϵ= 0 our expected cost is an aﬃne transformation of the

one in Shiryaev’s classical optimal detection problem with a rescaled model parameter.

1. Introduction

1.1. Classical quickest detection. The classical quickest detection problem can be stated

as follows. Let Bbe a Brownian motion and θbe an independent exponentially distributed

random variable. An optimizer observes the sample path of a stochastic process Xwhose

evolution is described by

(1.1) dXt=dBt,for t∈[0, θ),

µdt+ dBt,for t∈[θ, ∞).

Here µ∈Ris known to the observer but θand Bare not directly observable, and the aim

is to detect the appearance of the drift µas quickly as possible. This problem was originally

motivated by the operation of radar systems, where Xmodels the real-time signal emitted

by the radar (cf. Shiryaev [24] for a detailed historical account of the genesis of this problem

and its various formulations). More generally, model (1.1) can be viewed as a continuous-time

approximation of a discrete-time sequence of independent observations whose mean changes

at an unknown time point. Such models have found numerous applications in real-world

change-point detection scenarios; see, e.g., the monographs by Poor and Hadjiliadis [20] and

by Tartakovsky et al. [25].

Mathematically, the observer has access to the ﬁltration (FX

t)t≥0generated by the process

X, i.e., FX

t=σ(Xs, s ≤t). In the classical setting, the observer chooses one FX

t-stopping

time τin order to minimise a cost function

(1.2) E[α1{τ<θ}+β(τ−θ)+] = αP(τ < θ) + βE[(τ−θ)+],

where Pis a suitable probability measure on a suitable sample space (Ω,F), α > 0 measures

the cost of a false alarm, and β > 0 measures the cost of delay in detection. The literature

on this class of problems is very vast and it dates back to Shiryaev’s work in 1960’s (e.g.,

Date: February 28, 2025.

Key words and phrases. quickest detection, progressive enlargement of ﬁltrations, recursive optimal stop-

ping, optimal multiple stopping, free boundary problems.

Mathematics Subject Classiﬁcation 2020: 60G40, 35R35, 60G35.

arXiv:2210.01844v2 [math.OC] 26 Feb 2025

2 T. DE ANGELIS, J. GARG, Q. ZHOU

[21], [22]), where the problem above was formulated and solved for the ﬁrst time. The ﬁnite-

horizon version of the problem was studied by Gapeev and Peskir [12], general one dimensional

diﬀusions were considered by Gapeev and Shiryaev [13] and, in particular, quickest detection

for Bessel and Ornstein-Uhlenbeck processes was studied by Peskir with Johnson [15] and

with Glover [14], respectively. Recently, Peskir and Ernst [11] studied the detection of a drift

in a coordinate of a multi-dimensional Brownian motion. Further references on this subject

and the related “disorder problem” can be found in [19, Chapter VI] and in Shiryaev’s survey

paper [24].

1.2. Motivating examples for our study. To motivate our study and explain how it

extends the classical quickest detection problem, it is convenient to think of the process X

as a signal emitted by a system and of θas the time at which the operating mode of the

system changes (e.g., because of a mechanical failure or because of an external disturbance).

The interpretation of the payoﬀ in (1.2) is as follows: at time τthe appearance of a drift is

“declared”; if τ < θ the cost of a “false alarm” is α, whereas if τ > θ the cost of a “delayed

alarm” is β(τ−θ). In order to calculate such costs, some sort of test must be performed on the

system that reveals without error whether the drift has appeared or not. Upon observing a

negative outcome from the test, in some applications one resumes monitoring the system until

the next stopping decision is made (e.g. in the radar operation problem discussed in [24]).

In reality, a “perfect” inspection of the system is often impossible, particularly when the

underlying disorder is challenging to identify, due to the possibility of false negatives resulting

from the test. In those cases, it makes sense to allow multiple (costly) inspections of the

system. Problems of this kind naturally arise in the healthcare context, where we may think

of Xas an indicator of the general health condition of an individual and of θas the time of

the onset of some disease. The appearance of the drift µin the dynamics of Xmodels the

appearance of some symptoms, which may be diﬃcult to detect at ﬁrst or perhaps could be

mistaken for some normal tiredness or stress. Indeed, it is well known that the detection of

complex diseases, like cancer in early stages, may require multiple tests and false negatives

are not uncommon (see, e.g., Bartlett et al. [3] and Verbeek et al. [26]). Another example is

suggested by the extensive use of COVID-19 tests that we witnessed in recent years. In that

case, early symptoms could vary wildly across diﬀerent individuals, and it is not easy to tell

them apart from those of a normal cold. Testing was key but the false negative rate of the

PCR test can be as high as 10%, according to Kanji et al. [16].

Variants of the classical quickest detection problem accounting for imperfect inspections

could also cover situations in which a device which is positioned in a remote location sends

signals in continuous time to headquarters (e.g., a satellite). A change in the form of the

signal may indicate a faulty part in the device. However, at least initially the inspections

would be carried out “remotely” and would therefore be subject to error.

It turns out that the mathematical literature has not yet considered quickest detection

problems in such situations, and this work represents the ﬁrst attempt in this direction. For

simplicity, we do not consider false positives in our analysis, but in Section 6we point to

several generalizations of our model. This simpliﬁcation is not overly restrictive, because in

many applications where a statistical hypothesis testing procedure is used to determine 1{τ <θ},

the false positive rate is controlled at a minimum level (for example, in the aforementioned

work on COVID-19 testing [16], the false positive rate is assumed to be zero).

1.3. Our model and mathematical contribution. To account for false negatives, we

propose a new variant of the quickest detection problem. We describe it informally here and

we will rigorously formulate the problem in Section 2. We still assume the observed system’s

dynamics be modeled by the process Xgiven in (1.1). Unlike the classical formulation, we

assume that at the chosen stopping time τ, the optimizer performs an imperfect inspection on

A QUICKEST DETECTION PROBLEM WITH FALSE NEGATIVES 3

the system. The outcome of such inspection is modeled as a binary random variable Z∈ {0,1},

where Z= 1 means that the drift is detected and Z= 0 means otherwise. The conditional

distribution of Zis given according to P(Z= 0|θ > τ) = 1 and P(Z= 0|θ≤τ) = ϵ, where

ϵ∈[0,1) is referred to as the false negative rate and assumed known. Each inspection has a

ﬁxed cost assumed to be 1, and thus the optimizer wants to wisely choose when to perform

the inspection. Upon observing Z= 0 (which will be referred to as a negative outcome),

the optimizer suitably adjusts her posterior belief of the presence of a drift, before resuming

the observation of the system and choosing the next stopping time. If Z= 1 (i.e., a positive

outcome), then the drift is successfully detected, and the optimization ends. Letting Ndenote

the number of tests needed to detect the drift and τNdenote the N-th stopping time, the

cost function to be minimized in our problem is

(1.3) E[N+β(τN−θ)+].

Compared to the classical cost function (1.2), which penalizes false alarms directly through

the false alarm probability, our cost (1.3) penalizes them using E[N]. One key diﬀerence

between our model formulation and the classical one is that in the classical quickest detection

the optimization ends at the ﬁrst time the alarm is declared, irrespective of whether or not

the drift has actually appeared. In our formulation, instead, the optimization ends when the

drift is detected for the ﬁrst time, as a result of one of many possible inspections. Other

versions of the problem, which combine “inspecting the system” and “declaring the alarm”

are discussed in Section 6. Although in this work we primarily focus on how to minimize

the cost function (1.3), in Section 6we also discuss how to further generalize this problem to

allow for false positives.

At the mathematical level the problem is formulated as an optimal multiple stopping prob-

lem (in the spirit of Kobylanski et al. [18]) combined with a progressive enlargement of ﬁl-

tration occurring at the stopping times when the inspections are performed. Moreover, at

the stopping times when the system’s inspection returns a negative outcome, jumps are in-

troduced to the posterior’s dynamics. To solve the problem, we show its equivalence to a

recursive optimal stopping problem (somewhat in the spirit of Colaneri and De Angelis [8]).

The recursive problem has a natural link to a free boundary problem with recursive boundary

conditions at the (unkown) optimal stopping boundary. We are able to solve explicitly the

free boundary problem and fully identify both the optimal sequence of stopping times and

the optimal cost in the quickest detection problem. Our results are summarized in Theorem

2.5.

The structure of the mathematical problem is completely diﬀerent from the one in the

classical quickest detection framework. As a result, we obtain optimal strategies that cannot

be derived simply by iterating the ones from Shiryaev’s original work. However, when ϵ= 0, we

are able to characterize a linear relationship between our expected cost and that in Shiryaev’s

classical optimal detection problem, up to a scaling of the cost coeﬃcient β, and show the

equivalence between the two optimal policies. We would like to emphasize that the explicit

solution of a recursive optimal stopping problem is a signiﬁcantly more challenging task than

the solution of its non-recursive counterpart, and we believe it has never been accomplished

in the literature. In particular, Colaneri and De Angelis [8] and Carmona and Touzi [7]

(see [7, Section 4]) deal, for diﬀerent reasons, with optimal stopping problems with recursive

structure but neither of them obtains an explicit formula for the optimal strategy or for the

value function.

Recent work by Bayraktar et al. [4] considers a closely related quickest detection problem

with costly observations. Unlike our setting, the optimizer in [4] does not observe the sample

path of Xin continuous time but only at discrete (stopping) times, upon paying a ﬁxed cost

per observation (in Bayraktar and Kravitz [5] the optimizer can make ndiscrete observations

4 T. DE ANGELIS, J. GARG, Q. ZHOU

at no cost). Based on such discrete observations of the sample path, the optimizer must choose

when to declare the appearance of the drift and, at that point, the optimisation terminates

and it is revealed whether θhas occurred or not. The key conceptual diﬀerence is that in our

setup the “observation” of the system is for free but the “inspection” of the presence of a drift

is costly, with limited accuracy and it can be repeated multiple times. In the setup of [4] the

observation of the system is costly and its close inspection can be performed only once but

with perfect accuracy. The methodology in [4] relies on an iterative construction of a ﬁxed

point for the cost function. A characterisation of an optimal sequence of observation times is

given in terms of a continuation region that cannot be found explicitly and whose geometry

is investigated only numerically. For completeness, we also mention that quickest detection

problems with costly observations of the increments of Xwere considered by Antelman and

Savage [1], Balmer [2] and Dalang and Shiryaev [9]. The cost depends on the length of the

observation, and the problems take the form of stochastic control with discretionary stopping;

that leads to a framework completely diﬀerent from ours.

1.4. Structure of the paper. Our paper is organized as follows. In Section 2we introduce

the mathematical model in its optimal multiple stopping formulation, with a progressively

enlarging ﬁltration, and we describe the dynamics of the posterior process (which includes

jumps). In Section 2.2 we state our main result (Theorem 2.5) containing the explicit form

of the value function of our problem and the optimal multiple stopping rule. In Section 3, we

deﬁne a suitable recursive optimal stopping problem and we show the equivalence between

the original optimal multiple stopping problem and the recursive one. In Section 4we obtain

the explicit solution of the recursive problem via the solution of a free boundary problem

with recursive boundary conditions at the free boundary. In Section 5we give the formal

proof of our main result. We discuss properties of the optimal strategy and illustrate its

dependence on various model parameters also with the support of a detailed numerical study.

Section 6contains a short discussion about possible generalizations of our model. The paper

is completed by a technical Appendix.

2. Setting

We consider a probability space (Ω,F,Pπ) suﬃciently rich to host a Brownian motion

(Bt)t≥0, a random variable θ∈[0,∞) and an inﬁnite sequence of i.i.d. random variables

(Uk)∞

k=1 with U1∼U(0,1), the uniform distribution on [0,1]. The process (Bt)t≥0and the

random variables θand (Uk)∞

k=1 are mutually independent. The law of θis parametrised by

π∈[0,1] and we have Pπ(θ= 0) = πand Pπ(θ > t|θ > 0) = e−λt for λ > 0. In keeping with

the standard approach to quickest detection problems, for any A∈ F

Pπ(A) = πP0(A) + (1 −π)Z∞

λe−λsPs(A)ds,

where Pt(A) := Pπ(A|θ=t). Given a sub-σ-algebra G ⊂ F and any two events A, B ∈ F we

use the notation Pπ(A|G, B) = Pπ(A∩B|G)/Pπ(B|G).

On this space we consider the stochastic dynamics

Xt=x+µ(t−θ)++σBt,for t≥0,

where x∈R,µ∈R,σ > 0 and ( ·)+denotes the positive part. The ﬁltration generated by

the sample paths of the process is denoted by FX

t=σ(Xs, s ≤t), and it is augmented with

Pπ-null sets.

Given random times ρ≤τ, we denote open and closed intervals respectively by ((ρ, τ))

and [[ρ, τ]]. Given a ﬁltration (Gt)t≥0, we denote by T(Gt) the class of stopping times for that

ﬁltration. Let Nbe the set of natural numbers excluding zero. We say that a sequence (τn)∞

n=0

of random times is increasing if:

A QUICKEST DETECTION PROBLEM WITH FALSE NEGATIVES 5

(i) τ0= 0 and τnis Pπ-a.s. ﬁnite for all n∈N,

(ii) τn≤τn+1 for all n∈Nand

lim

n→∞ τn=∞,Pπ-a.s.(2.1)

Given an increasing sequence (τn)∞

n=0 we introduce random variables (Zn)∞

n=0 which will be

used to model the output of the tests that the optimizer runs on the system for the detection

of θ. More precisely, we set Z0= 0 and, for k∈Nand ϵ∈[0,1), we deﬁne

Zk=(1,if θ≤τkand Uk∈[0,1−ϵ],

0,otherwise.

(2.2)

It is important to notice that the sequence (Zn)∞

n=0 depends on the increasing sequence

(τn)∞

n=0, so we should actually write Zn=Zn(τn). However, we prefer to keep a simpler

notation as no confusion shall arise.

Given an increasing sequence (τk)∞

k=0 and the associated sequence (Zk)∞

k=0, we deﬁne the

processes

Ct:=

∞

i=0

1{t≥τi}and Yt:=

∞

i=0

Zi1{t≥τi},

and their natural ﬁltration FC,Y

t=σ((Cs, Ys), s ≤t). The process Cis the counter of the

number of tests, whereas the process Yacts as a counter of the number of positive tests.

Letting G0

t=FX

t, we deﬁne recursively a progressive enlargement of the initial ﬁltration by

setting

t:= Gk−1

t∨σ(Zk1{s≥τk}, s ≤t)∨σ(1{s≥τk}, s ≤t),for k∈N.

Notice that (G∞

t)t≥0is the ﬁltration generated by the triplet (Ct, Xt, Yt)t≥0with G∞

t=FX

t∨

FC,Y

t. Moreover, Gk

t=FX

t∨ FC,Y

t∧τkfor every k∈N.

By construction, each τkis a (Gk

t)t≥0-stopping time. However, for the formulation of our

optimisation problem we further restrict the class of increasing sequences as explained in the

next deﬁnition.

Deﬁnition 2.1 (Admissible sequence). We say that an increasing sequence (τn)∞

n=0 of

random times is admissible if τk∈ T (Gk−1

t)for each k∈N. We denote by T∗the class of

admissible sequences of random times.

Now we are ready to state the quickest detection problem we are interested in. Given an

admissible sequence (τn)∞

n=0 ∈ T∗, the associated sequence (Zn)∞

n=0 and the process (Yt)t≥0,

we set

NY(τn)∞

n=0=NY:= inf{n∈N:Yτn= 1}.(2.3)

Here, NYis the number of system inspections until the drift is detected and

τNY:= inf{t≥0 : Yt= 1}

is the time at which the drift is detected. It is clear that on {NY=j}we have τNY=τj.

The cost function associated to a sequence (τn)∞

n=0 ∈ T∗is deﬁned as

Jπ(τn)∞

n=0:=EπhNY+β(τNY−θ)+i,

where β > 0 is a given constant. The interpretation is as follows: the optimizer pays one unit

of capital each time she inspects the system; moreover, she also pays a penalty proportional

to the delay with which the drift is detected. The problem ends upon drift detection.

The value function of the optimisation problem reads

V(π) := inf

(τn)∞

n=0∈T∗

Jπ(τn)∞

n=0.(2.4)

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

AQUICKESTDETECTIONPROBLEMWITHFALSENEGATIVESTIZIANODEANGELIS,JHANVIGARG,ANDQUANZHOUAbstract.Weformulateandsolveavariantofthequickestdetectionproblemwhichfea-turesfalsenegatives.AstandardBrownianmotionacquiresadriftatanindependentexpo-nentialrandomtimewhichisnotdirectlyobservable.Basedontheobservation...

展开>> 收起<<

A QUICKEST DETECTION PROBLEM WITH FALSE NEGATIVES TIZIANO DE ANGELIS JHANVI GARG AND QUAN ZHOU Abstract. We formulate and solve a variant of the quickest detection problem which fea-.pdf

共35页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

A QUICKEST DETECTION PROBLEM WITH FALSE NEGATIVES TIZIANO DE ANGELIS JHANVI GARG AND QUAN ZHOU Abstract. We formulate and solve a variant of the quickest detection problem which fea-

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: