1. Problem formulation

Let $(\Omega, \mathcal{F}, \mathbb{P}_{\pi})$ be a probability space hosting a Brownian motion W and an independent random variable $\Theta$ having distribution $\mathbb{P}_{\pi}\{\Theta=0\}=\pi$ , $\mathbb{P}_{\pi}\{\Theta>t\}=(1-\pi)\textrm{e}^{-\lambda t}$ ( $t \geq 0$ ), where $\pi\in[0,1]$ . We assume that the observation process $(X_t)_{t\geq 0}$ is given by $X_t=\alpha(t-\Theta)^++W_t$ , i.e. a Brownian motion which after the random (disorder) time $\Theta$ drifts at rate $\alpha$ . Our objective is to detect the unknown disorder time $\Theta$ based on the observations of $X_t$ as quickly after its occurrence as possible, but at the same time with a small proportion of false alarms. A classical Bayes risk associated with a stopping strategy $\tau$ (where $\tau$ is a stopping time with respect to some appropriate filtration) is given by

(1.1) \begin{equation} \mathbb P_\pi(\tau<\Theta) + c\mathbb{E}_\pi[(\tau-\Theta)^+],\end{equation}

where $c>0$ is a cost associated with the detection delay.

In the classical version of the detection problem [Reference Shiryaev14], observations of the underlying process are costless, and a solution can be obtained by making use of the associated formulation in terms of a free-boundary problem. Subsequent literature has, among different things, focused on the case of costly observations. In [Reference Balmer1] and [Reference Dalang and Shiryaev7], a version of the problem was considered in which observations of increments of the underlying process are costly, and where the cost is proportional to the length of the observation time. An alternative set-up was considered in [Reference Bayraktar and Kravitz4], where the number of observations of the underlying process is limited.

In the current article we consider a model in which observations of X are unrestricted, but where each observation is associated with an observation cost $d>0$ . We stress that we assume that the controller observes values of the process X, as opposed to increments of X as in [Reference Balmer1] and [Reference Dalang and Shiryaev7].

Due to the discrete cost of each observation, our observation strategies will consist of finitely many samples; this motivates the following definition.

A useful result regarding the structure of the stopping times is the following, which is presented as [Reference Bayraktar and Kravitz4, Proposition 2.1].

We generalize the Bayes risk defined in (1.1) by formulating the quickest detection problem with observation costs as

(1.2) \begin{equation}\begin{split}V(\pi)&=\inf_{\hat{\tau}\in\mathcal{T}}\inf_{\tau\in \mathcal{S}^{\hat{\tau}} } \left\{\mathbb P_{\pi}({\tau}<\Theta)+\mathbb E_{\pi}\left[c\, ({\tau}-\Theta)^++d\sum_{k=1}^{\infty}\textbf{1}_{\{\tau_k\leq \tau\}}\right]\right\}.\end{split}\end{equation}

Here, the positive constant c represents the cost of detection delay, and the positive constant d represents the cost for each observation. Note that the observer has two controls: they control the observation sequence $\hat{\tau}$ , and also need to decide when the change happened, which is the role of $\tau$ . We should point out that we can extend our results to cover “expected miss” criteria using the results of [Reference Shiryaev15], by choosing the cost parameters appropriately. We can also consider the exponential delay penalty as in [Reference Gapeev and Shiryaev11], but in this case we need to use additional sufficient statistics. This would change the nature of the problem, but we expect the structure of the solution to be qualitatively similar. For further discussion on different criteria and the derivation of sufficient statistics, see also [Reference Bayraktar, Dayanik and Karatzas2].

Problem (1.2) can be formulated as a control problem in terms of the a posteriori probability process $\Pi^{\hat{\tau}}_t:=\mathbb P_{\pi}(\Theta\leq t \mid \mathcal{F}^{\hat{\tau}}_t)$ as $V(\pi)=\inf_{\hat{\tau}\in\mathcal{T}}\inf_{{\tau}\in\mathcal{S}^{\hat{\tau}}}\rho^{\pi}(\hat{\tau},\tau)$ , where

\[ \rho^{\pi}(\hat{\tau},\tau):=\mathbb{E}_\pi\left[1-\Pi^{\hat{\tau}}_{\tau}+c \int_0^{\tau}\Pi^{\hat{\tau}}_s \, \textrm{d} s + d\sum_{k=1}^{\infty}\textbf{1}_{\{\tau_k\leq \tau\}}\right].\]

The computations are analogous to, e.g., [Reference Poor and Hadjiliadis13, Proposition 5.8]. Observe that we can restrict ourselves to stopping times with $\mathbb E[\tau]<\infty$ .

For $\pi=1$ , the a posteriori probability process $\Pi^{\hat{\tau}}_{t}$ is constantly equal to 1. If $\pi\in[0,1)$ , then $\Pi^{\hat{\tau}}_{t}$ can [Reference Bayraktar and Kravitz4, Reference Dayanik9] be expressed recursively as

(1.3) \begin{equation} \Pi^{\hat{\tau}}_t= \left\{ \begin{array}{l@{\quad}l} \pi & t=0,\\[4pt] 1-(1-\Pi^{\hat{\tau}}_{\tau_{k-1}})\textrm{e}^{-\lambda(t-\tau_{k-1})} & \tau_{k-1} < t< \tau_{k}, \\[4pt] \frac{j(\tau_{k}-\tau_{k-1},\Pi^{\hat{\tau}}_{\tau_{k-1}},X_{\tau_{k}}-X_{\tau_{k-1}})}{1+j(\tau_{k}-\tau_{k-1},\Pi^{\hat{\tau}}_{\tau_{k-1}},X_{\tau_k}-X_{\tau_{k-1}})} & t=\tau_{k}, \end{array}\right.\end{equation}

where $k\geq 1$ , $\tau_0:=0$ , and

\begin{align*}j(t,\pi,x)=\exp\left\{\alpha x+\bigg(\lambda-\frac{\alpha^2}{2}\bigg)t \right\}\frac{\pi}{1-\pi}+\lambda\int_0^t\exp\left\{\bigg(\lambda+\frac{\alpha x}{t}\bigg)u-\frac{\alpha^2u^2}{2t} \right\} \textrm{d} u.\end{align*}

Thus, at an observation time $\tau_k$ , the process $\Pi^{\hat{\tau}}$ jumps from $1-(1-\Pi^{\hat{\tau}}_{\tau_{k-1}})\textrm{e}^{-\lambda(\tau_k-\tau_{k-1})}$ to

\[ \frac{j(\tau_{k}-\tau_{k-1},\Pi^{\hat{\tau}}_{\tau_{k-1}},X_{\tau_{k}}-X_{\tau_{k-1}})}{1+j(\tau_{k}-\tau_{k-1},\Pi^{\hat{\tau}}_{\tau_{k-1}},X_{\tau_k}-X_{\tau_{k-1}})}.\]

Moreover, $(t, \Pi^{\hat{\tau}}_t)$ with respect to $\mathbb{F}^{\hat\tau}$ is a piecewise-deterministic Markov process in the sense of [Reference Davis8, Section 2], and therefore has the strong Markov property.

At time $t=0$ , the observer could decide that they will not be making any observations (by setting $\tau_1=\infty$ ). Then $\Pi^{\hat{\tau}}$ evolves deterministically, see (1.3), and the corresponding cost of following that strategy is thus given by

\begin{align*} F(\pi) & = \inf_{t\geq 0}\left\{1-\Pi^{\hat{\tau}}_{t}+c \int_0^{t}\Pi^{\hat{\tau}}_s \textrm{d} s\right\} \\[3pt] & = \inf_{t\geq 0}\left\{(1-\pi)\textrm{e}^{-\lambda t}+ct-c(1-\pi)\frac{1-\textrm{e}^{-\lambda t}}{\lambda} \right\} \\[3pt] & = \left\{ \begin{array}{l@{\quad}l} \frac{c}{\lambda} \left(\pi+\log\frac{(\lambda+c)(1-\pi)}{c}\right) & \pi < \frac{\lambda}{c+\lambda} , \\[6pt] 1-\pi & \pi \geq \frac{\lambda}{c+\lambda}. \end{array}\right.\end{align*}

Moreover, the optimizer $t^*$ is given by

\begin{equation*} t^*(\pi)=\left\{ \begin{array}{l@{\quad}l} \frac{1}{\lambda}\log\frac{(\lambda+c)(1-\pi)}{c} & \pi < \frac{\lambda}{c+\lambda} , \\[6pt] 0 & \pi \geq \frac{\lambda}{c+\lambda}. \end{array}\right.\end{equation*}

For a given sequence $\hat\tau\in\mathcal T$ of observations, let $\mathcal S^{\hat\tau}_0\subseteq \mathcal S^{\hat\tau}$ denote the set of $\mathbb F^{\hat\tau}$ -stopping times $\tau$ such that $\mathbb P_\pi$ -a.s. (almost surely) $\tau=\tau_k$ for some $k=k(\omega)$ .

Proposition 1.1. The quickest detection problem with costly observations $V(\pi)$ in (1.2) can be represented as

\begin{align*} V(\pi) & = \inf_{\hat{\tau}\in\mathcal{T}}\inf_{\tau\in \mathcal S^{\hat\tau}_0} \mathbb E_{\pi}\Bigg[F(\Pi^{\hat{\tau}}_{\tau})+c\tau \\[4pt] & \qquad \qquad \qquad \quad -\frac{c}{\lambda}\sum_{k=0}^{\infty}(1-\Pi^{\hat{\tau}}_{\tau_k})(1-\textrm{e}^{-\lambda(\tau_{k+1}-\tau_k)})\textbf{1}_{\{\tau_{k+1}\leq \tau\}} +d\sum_{k=1}^{\infty}\textbf{1}_{\{\tau_k\leq \tau\}}\Bigg],\end{align*}

i.e. the value function is a combined optimal stopping and impulse control problem.

Proof. It follows from Lemma 1.1 that any stopping time $\bar{\tau}\in \mathcal{S}^{\hat{\tau}}$ can be written as $\bar{\tau}=\tau+\bar{t}$ , for $\tau\in \mathcal S^{\hat\tau}_0$ and for some $\mathbb F^{\hat\tau}_\tau$ -measurable random variable $\bar{t}$ . Then, by conditioning at $\tau$ first, optimizing over the stopping times in $\mathcal{S}^{\hat{\tau}}$ , and then taking expectations, we obtain

(1.4) \begin{equation}V(\pi)=\inf_{\hat{\tau}\in\mathcal{T}}\inf_{\tau\in \mathcal S^{\hat\tau}_0}\mathbb{E}_\pi\left[F(\Pi_{\tau})+c \int_0^{\tau}\Pi^{\hat{\tau}}_s \textrm{d} s+d\sum_{k=1}^{\infty}\textbf{1}_{\{\tau_k\leq \tau\}}\right].\end{equation}

The rest of the proof involves using (1.3) and partitioning the integral into integrals over $[\tau_i,\tau_{i+1})$ .

In a related work [Reference Dyrssen and Ekström10], the sequential hypothesis testing problem for the drift of a Wiener process was considered under the same assumption of costly observations. In the sequential hypothesis testing problem, the nature of the data remains the same and the goal is to determine the nature of the data as soon as possible. In contrast, in the quickest detection problem the nature of the data changes at a given time and the goal is to determine the change time as soon as it happens by balancing detection delay and false alarm frequency. As a result of this difference, the evolution of the sufficient statistic $\Pi$ and the pay-off function are different. This leads, for example, to a different functional operator in the next section. Although both papers use monotone functional operators that preserve concavity, because of the form of our operator the proof of preservation of concavity is far more difficult in our case and requires a new idea. We will also see that the solution structure is different. For example, in the quickest detection problem, although there are no observation rights left, the decision maker still does not declare the decision and waits longer; see Section 3.

2. A functional characterization of the value function

In this section we study the value function V and show that it is a fixed point of a monotone operator $\mathcal{J}$ , in effect proving the so-called dynamic programming principle. This will then be used in the next section to construct an optimal strategy.

To define the operator $\mathcal{J}$ , let $\mathbb F:=\{f \colon [0,1]\to[0,1]$ measurable and such that $f(\pi)\leq 1-\pi\}$ , and set $\mathcal{J}f(\pi)=\min\{F(\pi),\inf_{t>0}\mathcal{J}_0f(\pi,t)\}$ for $f\in\mathbb F$ , where

\[\mathcal{J}_0f(\pi,t)=d+\mathbb{E}_\pi\left[f\left(\frac{j(t,\pi,X_t)}{1+j(t,\pi,X_t)}\right) + c(t-\Theta)^+\right].\]

Note that

\[\mathbb{E}_\pi\left[(t-\Theta)^+\right]= t-(1-\pi)\frac{1-\textrm{e}^{-\lambda t}}{\lambda},\]

so

(2.1) \begin{equation}\mathcal{J}_0f(\pi,t)=d+\mathbb{E}_\pi\left[f\left(\frac{j(t,\pi,X_t)}{1+j(t,\pi,X_t)}\right) + c t-c(1-\pi)\frac{1-\textrm{e}^{-\lambda t}}{\lambda} \right].\end{equation}

Proof. (i) and (iii) are immediate. For (ii), let $f_1,f_2\in\mathbb F$ and let $a\in[0,1]$ . Then

\begin{align*}\mathcal{J}(af_1+(1-a)f_2) & = \min\left\{F, \inf_{t>0} \left\{ a\mathcal{J}_0f_1 +(1-a)\mathcal{J}_0f_2\right\}\right\}\\&\geq \inf_{t>0}\left\{ a\min\{F,\mathcal{J}_0 f_1\} + (1-a)\min\{F,\mathcal{J}_0 f_2\}\right\}\\&\geq a \mathcal{J} f_1 +(1-a)\mathcal{J} f_2.\end{align*}

For (iv), we argue as in [Reference Davis8, Lemma 54.21]: assume that there exist two distinct fixed points of $\mathcal{J}$ , i.e. $f_1=\mathcal{J} f_1$ and $f_2=\mathcal{J} f_2$ for $f_1,f_2\in\mathbb F$ such that $f_1(\pi)<f_2(\pi)$ (without loss of generality) for some $\pi\in[0,1)$ . Let $a_0:=\sup\{a\in[0,1]: af_2\leq f_1\}$ , and note that $a_0\in[0,1)$ . From (iii), it follows that there exists $\kappa>0$ such that $\kappa \mathcal{J} 0\geq 1-\pi$ , $\pi\in[0,1]$ , so using (i) and (ii) we get $f_1 = \mathcal{J} f_1 \geq \mathcal{J}(a_0f_2) \geq a_0\mathcal{J} f_2 + (1-a_0)\mathcal{J} 0 \geq (a_0+(1-a_0)\kappa^{-1})f_2$ , which contradicts the definition of $a_0$ .

For (v), first note that F is concave. Since the infimum of a concave function is again concave, it therefore follows from (2.1) that it suffices to check that

\[\mathbb{E}_\pi\left[f\left(\frac{j(t,\pi,X_t)}{1+j(t,\pi,X_t)}\right)\right]\]

is concave in $\pi$ for any $t>0$ given and fixed. To do that, define measures $\mathbb Q_{\pi}$ , $\pi\in[0,1)$ , on $\sigma(X_t)$ by

\[\textrm{d}\mathbb Q_\pi := \frac{\textrm{e}^{\lambda t}}{(1-\pi)(1+j(t,\pi,X_t))} \textrm{d} \mathbb P_\pi.\]

Then,

\[\mathbb{E}_\pi\left[\frac{\textrm{d}\mathbb Q_\pi}{\textrm{d}\mathbb P_\pi}\right]=\frac{\textrm{e}^{\lambda t}}{1-\pi}\int_{\mathbb R} \frac{1}{1+j(t,\pi,y)}\mathbb P_{\pi}(X_t\in \textrm{d} y).\]

Denoting by $\varphi$ the density of the standard normal distribution, we have

\begin{align*} \frac{ \mathbb P_{\pi}(X_t\in \textrm{d} y) }{1-\pi} & = \frac{\pi}{1-\pi} \mathbb{P}_\pi(X_t \in \textrm{d} y \mid \Theta=0) + \lambda\int_0^{t} \mathbb{P}_\pi(X_t \in \textrm{d} y \mid \Theta=s)\textrm{e}^{-\lambda s} \, \textrm{d} s \\ &\quad + \mathbb{P}_{\pi}(X_t \in \textrm{d} y \mid \Theta>t)\textrm{e}^{-\lambda t} \\ &= \frac{\pi}{(1-\pi){\sqrt t}\,} \varphi\left(\frac{y-\alpha t}{\sqrt t}\,\right) + \frac{\lambda}{{\sqrt t}\,}\int_0^t\textrm{e}^{-\lambda s}\varphi\left(\frac{y-\alpha (t-s)}{\sqrt t}\right)\textrm{d} s \\ & \quad + \frac{\textrm{e}^{-\lambda t}}{\sqrt t}\varphi\left(\frac{y}{{\sqrt t}\,}\right) \\ &= \textrm{e}^{-\lambda t}(1+j(t,\pi,y))\varphi\left(\frac{y}{{\sqrt t}\,}\right).\end{align*}

Thus,

\[\mathbb{E}_\pi\left[\frac{\textrm{d}\mathbb Q_\pi}{\textrm{d}\mathbb P_\pi}\right]=\frac{1}{{\sqrt t}\,}\int_\mathbb R\varphi\left(\frac{y}{{\sqrt t}\,}\right)\textrm{d} y = 1,\]

so $\mathbb Q_\pi$ is a probability measure. Furthermore, the random variable $X_t$ is N(0,t)-distributed under $\mathbb Q_\pi$ ; in particular, the $\mathbb Q_\pi$ -distribution of $X_t$ does not depend on $\pi$ .

Since $j(t,\pi,x)$ is affine in $\pi/(1-\pi)$ , the function

\[\pi\mapsto (1-\pi)f\left(\frac{j(t,\pi,x)}{1+j(t,\pi,x)}\right)(1+j(t,\pi,x))\]

is concave if f is concave. It thus follows from

\begin{align*} \\[-8pt]\mathbb{E}_\pi\left[f\left(\frac{j(t,\pi,X_t)}{1+j(t,\pi,X_t)}\right)\right] = (1-\pi)\exp\{-\lambda t\} \mathbb{E}^{\mathbb Q_\pi}\left[f\left(\frac{j(t,\pi,X_t)}{1+j(t,\pi,X_t)}\right)(1+j(t,\pi,X_t))\right]\\[-8pt]\end{align*}

and (2.1) that $\pi\mapsto \mathcal J_0f(\pi,t)$ is concave, which completes the proof.

Next, we define a sequence $\{f_n\}_{n=0}^{\infty}$ of functions on [0,1] by setting $f_0(\pi)=F(\pi)$ , $f_{n+1}(\pi)=\mathcal{J}f_n(\pi)$ , $n\geq 0$ .

Proof. Clearly, $f_1 \leq F=f_0$ , so Proposition 2.1(i) and a straightforward induction argument show that $f_n$ is decreasing in n. Hence, the pointwise limit $f_{\infty}:=\lim_{n\to\infty}f_n$ exists. Furthermore, since F is concave, each $f_n$ is concave by Proposition 2.1(v).

Thus, the pointwise limit $f_{\infty}:=\lim_{n\to\infty}f_n$ exists. Since the pointwise limit of concave functions is concave, it follows that $f_\infty$ is also concave.

Proposition 2.3. Let $f\in\mathbb F$ be continuous. For fixed $\pi\in[0,1]$ , the function $t \mapsto \mathcal{J}_0f(\pi,t)$ attains its minimum for some point $t \in [0,\infty)$ . Denote the first of these minimums by $t(\pi,f)$ , i.e.

(2.2) \begin{equation}t(\pi,f):= \inf \{t \geq 0: \inf_s \mathcal{J}_0f(\pi,s) = \mathcal{J}_0f(\pi,t) \}.\end{equation}

Then, $\pi \mapsto t(\pi,f)$ is measurable.

Proof. Observe that $(t,\pi) \mapsto \mathcal{J}_0f(\pi,t)$ is a finite continuous function which approaches $\infty$ as $t \to \infty$ . It follows that $t (\pi,f)$ is finite.

We will prove the measurability of $\pi \mapsto t(\pi,f)$ by showing that it is lower semi-continuous. Let $\pi_i \to \pi_{\infty}$ and let $t_i=t(\pi_i,f)$ . Because $t \to ct$ is the dominating term in $t \mapsto \mathcal{J}_0 f(\pi,t)$ , it is clear that the sequence $\{t_i\}_{i \in \mathbb{N}}$ is bounded. It follows that $t_{\infty}:=\liminf t_i<\infty$ ; let $\{t_{i_j}\}_{j=1}^\infty$ be a subsequence such that $t_{i_j}\to t_\infty$ . Then, by the Fatou lemma, $\mathcal{J}_{0}f(\pi_{\infty}, t_{\infty}) \leq \liminf_{j \to \infty} \mathcal{J}_0f(\pi_{i_j}, t_{i_j}) =\lim_{j \to \infty} \mathcal{J}_0 f(\pi_{i_j},t_{i_j}) = \mathcal{J}_{0} f(\pi_{\infty},t_\infty)$ . Thus, $t(\pi_{\infty},f) \leq t_{\infty} = \liminf_{i\to\infty}t (\pi_i,f)$ , which establishes the desired lower semi-continuity.

Proof. Since the operator $\mathcal{J}$ is monotone and $f_{n} \geq f_{\infty}$ , it is clear that $f_{\infty} \geq \mathcal{J} f_{\infty}$ . On the other hand, $f_{n+1}(\pi)= \mathcal{J} f_n(\pi) \leq \min\{F(\pi), \mathcal{J}_0 f_n(\pi, t(\pi,f_\infty))\}$ , where $t(\pi,f_\infty)$ is defined as in (2.2). Letting $n \to \infty$ and using the monotone convergence theorem, we obtain that $f_{\infty}$ is a fixed point. Since uniqueness is established in Proposition 2.1, this completes the proof.

Next, we introduce the problem of an agent who is allowed to make at most n observations: $V_n(\pi):=\inf_{\hat{\tau}\in\mathcal{T}}\inf_{\tau\in \mathcal S_0^{\hat\tau},\tau\leq \tau_n}\rho^{\pi}(\hat{\tau},\tau)$ . These functions can be sequentially generated using the integral operator $\mathcal{J}$ .

Proof. First, note that $V_0=f_0=F$ . Now assume that $V_{n-1}=f_{n-1}$ for some $n\geq 1$ .

Step 1: $V_n(\pi)\geq f_n(\pi)$ For any $\hat{\tau}\in\mathcal{T}$ and $\tau\in \mathcal S_0^{\hat\tau}$ ,

(2.3) \begin{align} & \mathbb E_{\pi}\Bigg[F(\Pi_{\tau\wedge\tau_n})+c \int_0^{\tau \wedge \tau_n }\Pi^{\hat{\tau}}_s \, {\textrm{d}} s + d\sum_{k=1}^{\infty}\textbf{1}_{\{\tau_k\leq \tau\wedge\tau_n\}}\Bigg] \notag \\ & = \mathbb E_{\pi}\left[\textbf{1}_{\{\tau_1=0\}}F(\pi)\right] + \mathbb E_{\pi}\Bigg[\textbf{1}_{\{\tau_1>0\}}\Bigg(F(\Pi_{\tau\wedge\tau_n})+c \int_0^{\tau \wedge \tau_n }\Pi^{\hat{\tau}}_s \, {\textrm{d}} s + d\sum_{k=1}^{\infty}\textbf{1}_{\{\tau_k\leq \tau\wedge\tau_n\}}\Bigg)\Bigg] \notag \\[3pt] & \geq \textbf{1}_{\{\tau_1=0\}}F(\pi) + \textbf{1}_{\{\tau_1>0\}} \mathbb E_{\pi}\left[ \left(d+c \int_{0}^{\tau_1} \Pi^{\hat{\tau}}_s \, {\textrm{d}} s +V_{n-1}(\Pi_{\tau_1})\right)\right] \notag \\[3pt] & = \textbf{1}_{\{\tau_1=0\}}F(\pi) + \textbf{1}_{\{\tau_1>0\}}\mathbb E_{\pi}\left[\left(d+c \int_{0}^{\tau_1} \Pi^{\hat{\tau}}_s \, {\textrm{d}} s +f_{n-1}(\Pi_{\tau_1})\right)\right] \notag \\[3pt] & \geq {\mathcal{J}} f_{n-1}(\pi)=f_n(\pi), \end{align}

where we used the fact that $\tau_1$ is deterministic and the Markov property of $\Pi^{\hat{\tau}}$ . We obtain the desired result from (2.3) by taking the infimum over strategy pairs $(\hat\tau,\tau)$ .

Step 2: $V_n(\pi)\leq f_n(\pi)$ We only need to prove this for the case $\mathcal{J} f_{n-1}(\pi) < F(\pi)$ (otherwise, $f_{n}(\pi) = \mathcal{J} f_{n-1}(\pi)=F(\pi) \geq V_n(\pi)$ already).

Note that $V_{0}=F=f_0$ . We will assume that the assertion holds for $n-1$ and then prove it for n. We will follow ideas used in the proof of [Reference Bouchard and Touzi5, Theorem 4.1]. Denoting $t_{n}:=t(\pi, f_{n-1})$ , let us introduce a sequence $\hat\tau$ of stopping times, $\tau_1=t_n$ , $\tau_{i+1}= \sum_{k}\tau^k_i \circ \theta_{t_n} \textbf{1}_{\{\Pi^{\hat{\tau}}_{t_n} \in B_k\}}$ , $i=1,\ldots,$ $n-1$ , where $(B_k)_k$ is a finite partition of [0,1) by intervals, and $\tau^k$ are $\epsilon$ -optimal observation times for when the process $\Pi$ starts from the centre of these intervals. Here, $\theta$ is the shift operator in the Markov process theory [Reference Çınlar6].

Since $V_{n-1}$ is continuous, and the expected value (before optimizing) is a continuous function of the initial starting point for any strategy choice (due to the continuity of $\Pi$ with respect to its starting point), the above sequence is $O(\varepsilon)$ if the intervals are chosen to be fine enough.

Now, we can write

\begin{align*} & f_n(\pi) = ct_n +d-\frac{c}{\lambda} (1-\pi) (1-\textrm{e}^{-\lambda t_n})+\mathbb E_{\pi}\left[V_{n-1}\left(\Pi^{\hat{\tau}}_{t_n}\right)\right] \\ & \geq ct_n+d-\frac{c}{\lambda}(1-\pi)(1-\textrm{e}^{-\lambda t_n})-O(\epsilon) \\ & \quad + \mathbb E_{\pi}\left\{\mathbb E_{\pi}\left[\left(F(\Pi^{\hat{\tau}}_{\tau\wedge\tau_{n-1}}) + \int_0^{\tau_{n-1} \wedge \tau} \Pi^{\hat{\tau}}_s \, \textrm{d} s + d\sum_{k=1}^{\infty}\textbf{1}_{\{\tau_k\leq \tau\wedge\tau_{n-1}\}}\right) \circ \theta_{t_n} \, \Big| \, \mathcal{F}^{\hat{\tau}}_{t_n}\right] \right\} \\ & = \mathbb E_{\pi}\Bigg[F(\Pi^{\hat{\tau}}_{\tau\wedge\tau_n}) + \int_0^{\tau \wedge \tau_n}\Pi^{\hat{\tau}}_s \, \textrm{d} s + d\sum_{k=1}^{\infty}\textbf{1}_{\{\tau_k\leq \tau\wedge\tau_n\}}\Bigg] -O(\epsilon) \geq V_n(\pi)-O(\epsilon),\end{align*}

where we used the fact that $c\int_0^{t_n}\Pi^{\hat{\tau}}_s \, \textrm{d} s = ct_n -\frac{c}{\lambda} (1-\pi) (1-\textrm{e}^{-\lambda t_n})$ . Since $\epsilon>0$ can be made arbitrary small, this shows that $V_n(\pi)\leq f_n(\pi)$ .

Proof. Since $V_n=f_n\to f_\infty$ , it suffices to show $\lim_{n\to\infty}V_n=V$ . It follows by definition that $V(\pi)\leq V_n(\pi)$ for any $n\geq 1$ and $\pi\in[0,1]$ . We thus only need to prove that $\lim_{n}V_n(\pi) \leq V(\pi)$ . Assume that a pair $(\hat\tau, \tau)$ where $\hat{\tau}\in\mathcal{T}$ and $\tau\in\mathcal{S}^{\hat{\tau}}_0$ is an $\epsilon$ -optimizer for (1.4). Then,

(2.4) \begin{align}V_n(\pi) &\leq \mathbb E\left[F(\Pi^{\hat{\tau}}_{\tau\wedge\tau_n})+\int_0^{\tau \wedge \tau_n}\Pi^{\hat{\tau}}_s \, \textrm{d} s + d\sum_{k=1}^{\infty}\textbf{1}_{\{\tau_k\leq \tau\wedge\tau_n\}}\right] \notag \\&\leq \mathbb E\left[F(\Pi^{\hat{\tau}}_{\tau\wedge\tau_n})+\int_0^{\tau}\Pi^{\hat{\tau}}_s \, \textrm{d} s + d\sum_{k=1}^{\infty}\textbf{1}_{\{\tau_k\leq \tau\}}\right].\end{align}

Note that since $\tau(\omega)= \tau_k(\omega)$ for some $k=k(\omega)$ , we have $\Pi^{\hat{\tau}}_{\tau \wedge \tau_n}(w)= \Pi^{\hat{\tau}}_{\tau}(\omega)$ if $n\geq k(\omega)$ . As a result, and since F is bounded and continuous, the bounded convergence theorem applied to (2.4) gives $\lim_{n\to\infty} V_n(\pi)\leq V(\pi)+\epsilon$ . Since $\epsilon>0$ is arbitrary, this completes the proof.

This approach to proving the Poisson disorder problem in the context of quickest detection problems goes back to [Reference Bayraktar, Dayanik and Karatzas3]. There, the observations were coming from a process with jumps, and the operator was defined through jump times of the observation process. On the other hand, the operator is defined through the observation times (which are now also part of the decision maker’s choice set).

3. The optimal strategy

In this section we study the optimal strategy for the detection problem with costly observations. More precisely, we seek to determine an optimal distribution of observation times $\hat\tau$ and an optimal stopping time $\tau$ . The optimal strategy is determined in terms of the continuation region $\mathcal{C}:=\{\pi \in [0,1]: V(\pi)< F(\pi)\}$ . Note that for $\pi\in \mathcal{C}$ we have $V(\pi)=\inf_{t\ge 0}\mathcal{J}_0 V(\pi,t)$ thanks to our main result from the last section. Denote by $t(\pi):=t(\pi,f_\infty)=t(\pi,V)$ , and note that since $\mathcal J_0V(\pi,0)=d+V(\pi)$ , we have $t(\pi)>0$ on $\mathcal{C}$ .

Moreover, define $t^*$ by

\[t^*(\pi)= \left\{\begin{array}{l@{\quad}l} t(\pi) &\mbox{for }\pi\in \mathcal{C} , \\[5pt]\infty& \mbox{for }\pi\notin \mathcal{C} . \end{array}\right.\]

Using the function $t^*$ , we recursively construct an observation sequence $\hat\tau^*$ and a stopping time $\tau^*$ as follows.

Denote $\tau_0^*=0$ and $\Pi_0=\pi$ . For $k= 1,2,\ldots$ , recursively define $\tau^*_{k}:=\tau^*_{k-1}+t^*\big(\Pi_{\tau^*_{k-1}}\big)$ and

\[\Pi_{\tau^*_k} :=\frac{j(\tau^*_{k}-\tau^*_{k-1},\Pi_{\tau^*_{k-1}},X_{\tau^*_{k}}-X_{\tau^*_{k-1}})}{1+j(\tau^*_{k}-\tau^*_{k-1},\Pi_{\tau^*_{k-1}},X_{\tau^*_k}-X_{\tau^*_{k-1}})}.\]

Then, $\hat\tau^*:=\{\tau_k^*\}_{k=1}^{\infty}\in\mathcal{T}$ . Moreover, let $n^*:= \min\{k\geq 0: \Pi_{\tau^*_{k}}\notin \mathcal{C}\}= \min\{k\geq 0:\tau^*_{k}=\infty\}$ , and define $\tau^*:=\tau^*_{n^*}$ . Then, $\tau^*\in\mathcal S^{\hat\tau^*}$ , and $n^*$ is the total number of finite observation times in $\hat\tau^*$ .

Proof. Denote

\begin{equation*}V^*(\pi)=\mathbb E_{\pi}\Bigg[F(\Pi_{\tau^*})+c\tau^*-\frac{c}{\lambda}\sum_{k=0}^{n^*-1}\big(1-\Pi_{\tau^*_k}\big)\big(1-\textrm{e}^{-\lambda(\tau^*_{k+1}-\tau^*_k)}\big)+dn^*\Bigg] . \end{equation*}

Clearly, by the definition of V, we have $V^*(\pi)\ge V(\pi)$ . It thus remains to show that $V\ge V^*(\pi)$ .

For $n\geq 0$ , let $\tau_n^\prime := \tau^*_n\wedge\tau^*=\tau^*_{n\wedge n^*}$ . We claim that

(3.1) \begin{align} V(\pi) & = \mathbb E_{\pi}\left[V(\Pi_{\tau^\prime_n})+c\tau^\prime_{n}-\frac{c}{\lambda}\sum_{k=0}^{n\wedge n^*-1}\big(1-\Pi_{\tau^*_k}\big)\big(1-\textrm{e}^{-\lambda(\tau^*_{k+1}-\tau^*_k)}\big)\right]\nonumber\\[3pt]& \quad + \mathbb{E}_\pi\left[d(n\wedge n^*)\right]\nonumber\\[3pt]& =\!:\, \textit{RHS}(n)\end{align}

for all $n\geq 0$ .

To prove the claim, first note that $\tau_0^\prime=0$ , so $V(\pi)=\textit{RHS}(0)$ . Furthermore, by the Markov property we have

\begin{align*} \textit{RHS}(n+1) - \textit{RHS}(n) & = \mathbb E_{\pi}\bigg[\bigg(V(\Pi_{\tau^*_{n+1}})-V(\Pi_{\tau^*_n}) +c(\tau^*_{n+1}-\tau^*_n) \\ & \qquad \qquad - \frac{c}{\lambda}(1-\Pi_{\tau^*_n})(1-\textrm{e}^{-\lambda(\tau^*_{n+1}-\tau^*_n)})+d\bigg)\textbf{1}_{\{n^*\ge n+1\}}\bigg] \\ & = \mathbb E_{\pi}\bigg[\bigg(\mathbb E_{\Pi_{\tau_n^*}}\left[V(\Pi_{\tau_1^*}) + c\tau_1^* \right]- V(\Pi_{\tau^*_n}) \\ & \qquad \qquad - \frac{c}{\lambda}(1-\Pi_{\tau_n^*}) \mathbb E_{\Pi_{\tau_n^*}}\left[ 1-\textrm{e}^{-\lambda \tau_1^*} \bigg] +d \right)\textbf{1}_{\{n^*> n\}}\bigg] \\ & = 0,\end{align*}

which shows that (3.1) holds for all $n\geq 0$ .

Note that it follows from (3.1) that $n^*<\infty$ a.s. (since otherwise the term $\mathbb{E}_\pi[d(n\wedge n^*)]$ would explode as $n\to\infty$ ). Therefore, letting $n\to\infty$ in (3.1), using bounded convergence and monotone convergence, we find that

\begin{align*}V(\pi) &= \mathbb E_{\pi}\left[V(\Pi_{\tau^*})+c\tau^*-\frac{c}{\lambda}\sum_{k=0}^{ n^*-1}\big(1-\Pi_{\tau^*_k}\big)\big(1-\textrm{e}^{-\lambda(\tau^*_{k+1}-\tau^*_k)}\big) + d n^*\right]\\[3pt]&= \mathbb E_{\pi}\left[F(\Pi_{\tau^*})+c\tau^*-\frac{c}{\lambda}\sum_{k=0}^{ n^*-1}\big(1-\Pi_{\tau^*_k}\big)\big(1-\textrm{e}^{-\lambda(\tau^*_{k+1}-\tau^*_k)}\big) + d n^*\right]\\[3pt]&= V^*(\pi),\end{align*}

which completes the proof.

Our approach, which relies on the dynamic programming principle, should be contrasted with the verification approach used in [Reference Peskir and Shiryaev12, Reference Poor and Hadjiliadis13, Reference Shiryaev16] which first finds a smooth enough solution to a free boundary problem and then uses Itô’s formula to verify that this solution is the value function. Another useful outcome of our approach due to its iterative nature is its usefulness for a numerical approximation.

4. Numerical examples

Figure 1 illustrates Proposition 2.2. We use the same parameters as for [Reference Bayraktar and Kravitz4, Figure 2], where $d=0$ .

Figure 1. $c=0.01$ , $\lambda=0.1$ , $\alpha=1$ , $d=0.001$ , $n=0,1,\ldots,10$ .

Figure 2. $c=0.1$ , $\lambda=0.1$ , $\alpha=1$ , $d=0.001$ , $n=0,1,\ldots,10$ .

Clearly, the value functions $V_n$ increase in the cost parameters. Figure 2 displays the value functions $V_1,\ldots,V_{10}$ for the same parameters as Figure 1 but for a larger cost c. Similarly, the sensitivity with respect to the observation cost parameter d is pictured in Figure 3.

Figure 3. $c=0.1$ , $\lambda=0.1$ , $\alpha=1$ .

In Figure 4 we compute the function t defined in (2.2) when f in the definition is replaced by $V_n$ , for various values of n. While it appears that $t(\pi,V_n)$ is decreasing in n (the more observation rights one has, the more inclined one is to make early observations) and decreasing in $\pi$ , we have not been able to prove these monotonicities.

Figure 4. $c=0.01$ , $\lambda=0.1$ , $\alpha=1$ , $d=0.001$ .

Finally, in Figure 5 we determine $\pi^*(n)=\inf\{\pi: t^*(\pi,V_n)=\infty\}$ . Our observations consistently indicate that the continuation region for taking observations is an interval of the form $[0, \pi^*(n))$ ; here also, an analytical proof of this remains to be found.

Figure 5. $c=0.01$ , $\lambda=0.1$ , $\alpha=1$ , $d=0.001$ .