4.1. Countable state space

When considering a countable finite state space, Dynkin’s formula (as used in the proofs of Lemmas 3.2 and 3.3) is not directly available, because nothing prevents the payoff taking arbitrarily large values. Nevertheless, we will adapt the strategy used in the case of a finite state space to build a monotone dynamic approach to the value function in the case of a countable finite state space.

Hereafter, we set some payoff function $\phi\in{\bar{\mathcal{F}}}_+\setminus\{0\}$ and $r>0$. We will construct a subset $\mathcal{D}_\infty\subset V$ and a function $u_\infty\in{\bar{\mathcal{F}}}_+$ by the following recursive algorithm.

We begin by taking $\mathcal{D}_0\,:\!=\, V$ and $u_0\,:\!=\, \phi$. Next, let us assume that $\mathcal{D}_n\subset V$ and $u_n\in{\bar{\mathcal{F}}}_+$ have been built for some $n\in\mathbb{Z}_+$ such that

(4.1) \begin{align} (r+L(x))u_n(x) = \mathcal{K}[ u_n](x) &\qquad\text{for all} \ x \in V\setminus \mathcal{D}_n , \end{align}

(4.2) \begin{align} u_n(x) = \phi(x) &\qquad\textrm{for\;all} \ x \in \mathcal{D}_n.\end{align}

Observe that this is trivially true for $n=0$. Then, we define the subset $\mathcal{D}_{n+1}$ as

(4.3) \begin{eqnarray}\mathcal{D}_{n+1} \,:\!=\, \{x\in \mathcal{D}_n\;:\;\mathcal{K}[u_n](x)\leq (r +L(x))u_n(x)\},\end{eqnarray}

where the inequality is understood in ${\bar{\mathbb{R}}}_+$.

Next, we consider the stopping time

(4.4) \begin{equation} \tau_{n+1} \,:\!=\, \inf\{t\geq 0\;:\;X_t\in \mathcal{D}_{n+1}\}\end{equation}

with the usual convention that $\inf \emptyset =+\infty$. For $m\in\mathbb{Z}_+$, define the stopping time $\tau_{n+1}^{(m)} \,:\!=\, \sigma_m\wedge\tau_{n+1}$ and the function $u_{n+1}^{(m)}\in{\bar{\mathcal{F}}}_+$ given by

(4.5) \begin{eqnarray}u_{n+1}^{(m)}(x) \,:\!=\, \mathbb{E}_x\left[\exp\big(-r \tau_{n+1}^{(m)}\big)u_n\left(X_{\tau_{n+1}^{(m)}}\right)\right]\qquad \text{for all} \ x \in V .\end{eqnarray}

Remark 4.1. The non-negative random variable $\exp\big({-}r \tau_{n+1}^{(m)}\big)u_n\Big(X_{\tau_{n+1}^{(m)}}\Big)$ is well defined, even if $\tau_{n+1}^{(m)}=+\infty$, since the convention $0\times (+\infty)=0$ imposes

\begin{equation*}\exp\big({-}r \tau_{n+1}^{(m)}\big)u_n\Big(X_{\tau_{n+1}^{(m)}}\Big)=0\end{equation*}

regardless of the value of $X_{\tau_{n+1}^{(m)}}$. The occurrence of $\tau_{n+1}^{(m)}=+\infty$ should be quite exceptional: we have $\big\{\tau_{n+1}^{(m)}=+\infty\big\} = \Big\{\tau_{n+1}=+\infty$ and $L\Big(X_{\tau_{n+1}^{(m)}}\Big)=0\Big\}$; in particular, it never happens if $L(x)>0$ for all $x\in V$, i.e. when $\triangle$ is the only possible absorbing point for X.

Our first result shows that the sequence $\big(u^{(m)}_{n+1}\big)_{m\in\mathbb{Z}_+ }$ is non-decreasing.

Proof. We first compute

(4.6) \begin{align} u_{n+1}^{(m+1)}(x) & \,:\!=\, \mathbb{E}_x\left[\exp\left(-r \tau_{n+1}^{(m+1)}\right)u_n\left(X_{\tau_{n+1}^{(m+1)}}\right)\right] \nonumber \\ & = \mathbb{E}_x\left[\textbf{1}_{\tau_{n+1}\leq \sigma_m}\exp\left(-r \tau_{n+1}^{(m+1)}\right)u_n\left(X_{\tau_{n+1}^{(m+1)}}\right)\right] \nonumber \\ & \quad +\mathbb{E}_x\left[\textbf{1}_{\tau_{n+1}> \sigma_m}\exp\left(-r \tau_{n+1}^{(m+1)}\right)u_n\left(X_{\tau_{n+1}^{(m+1)}}\right)\right]. \end{align}

On the event $\{\tau_{n+1}\leq \sigma_m\}$, we have that $\tau_{n+1}^{(m+1)}=\tau_{n+1}=\tau_{n+1}^{(m)}$, so the first term on the right-hand side of (4.6) is

(4.7) \begin{multline} \mathbb{E}_{x}\left[\textbf{1}_{\tau_{n+1}\leq \sigma_m}\exp\left(-r \tau_{n+1}^{(m+1)}\right)u_n\left(X_{\tau_{n+1}^{(m+1)}}\right)\right]\\ = \mathbb{E}_x\left[\textbf{1}_{\tau_{n+1}\leq \sigma_m}\exp\left(-r \tau_{n+1}^{(m)}\right)u_n\left(X_{\tau_{n+1}^{(m)}}\right)\right].\end{multline}

On the event $\{\tau_{n+1}> \sigma_m\}$, we have that $\tau_{n+1}^{(m+1)}=\tau_{n+1}^{(m)}+\sigma_1\circ \theta_{\tau_{n+1}^{(m)}}$, where $ \theta_{t}$, for $t\geq 0$, is the shift operator by time $t\geq 0$ on the underlying canonical probability space $\mathbb{D}(\mathbb{R}_+,\bar V)$ of right-continuous with left limits trajectories. Using the strong Markov property of X, we get that

(4.8) \begin{multline} \mathbb{E}_x\left[\textbf{1}_{\tau_{n+1}> \sigma_m}\exp\left(-r \tau_{n+1}^{(m+1)}\right)u_n\left(X_{\tau_{n+1}^{(m+1)}}\right)\right]\\ = \mathbb{E}_x\left[\textbf{1}_{\tau_{n+1}> \sigma_m}\exp\left(-r \tau_{n+1}^{(m)}\right)\mathbb{E}_{X_{\tau_{n+1}^{(m)}}}\big[\exp(-r \sigma_1)u_n(X_{\sigma_1})\big]\right].\end{multline}

For $y\in V$, we consider two situations:

• • if $L(y)=0$, we have a.s. $\sigma_1=+\infty$ and, as in Remark 4.1, we get

  \begin{equation*}\mathbb{E}_y[\exp(-r \sigma_1)u_n(X_{\sigma_1})] = 0;\end{equation*}

• • if $L(y)>0$, we compute, in ${\bar{\mathbb{R}}}_+$,

  \begin{align*} \mathbb{E}_y[\exp(-r \sigma_1)u_n(X_{\sigma_1})] & = \int_0^{+\infty} \!\!\!\! \exp(-rs) L(y)\exp(-L(y)s) \!\! \sum_{z\in V\setminus\{y\}} \frac{L(y,z)}{L(y)}u_n(z)\,\textrm{d} s \\ & = \int_0^{+\infty} \exp(-rs) \exp(-L(y)s)\,\textrm{d} s\sum_{z\in V\setminus\{y\}} L(y,z)u_n(z) \\ & = \frac1{r+L(y)}\mathcal{K}[u_n](y). \end{align*}

By our conventions, the equality

(4.9) \begin{eqnarray}\mathbb{E}_y[\exp(-r \sigma_1)u_n(X_{\sigma_1})] = \frac1{r+L(y)}\mathcal{K}[u_n](y)\end{eqnarray}

is then true for all $y\in V$.

For $y\in \mathcal{D}_n$, due to (4.1), the right-hand side of (4.9) is equal to $u_n(y)$. For $y\in \mathcal{D}_n\setminus \mathcal{D}_{n+1}$, by the definition of $\mathcal{D}_{n+1}$ in (4.3), the right-hand side of (4.9) is bounded below by $u_n(y)$. It follows that, for any $y\not\in \mathcal{D}_{n+1}$, $\mathbb{E}_y[\exp(-r \sigma_1)u_n(X_{\sigma_1})] \geq u_n(y)$. On the event $\{\tau_{n+1}> \sigma_m\}$, we have $X_{\tau_{n+1}^{(m)}}\not\in \mathcal{D}_{n+1}$ and thus

\begin{eqnarray*}\mathbb{E}_{X_{\tau_{n+1}^{(m)}}}[\exp(-r \sigma_1)u_n(X_{\sigma_1})] \geq u_n\left(X_{\tau_{n+1}^{(m)}}\right).\end{eqnarray*}

Coming back to (4.8), we deduce that

\begin{eqnarray*}\mathbb{E}_x\!\left[\textbf{1}_{\tau_{n+1}> \sigma_m}\exp\!\left(-r \tau_{n+1}^{(m+1)}\right)\!u_n\!\left(X_{\tau_{n+1}^{(m+1)}}\right)\!\right] \geq\mathbb{E}_x\!\left[\textbf{1}_{\tau_{n+1}> \sigma_m}\exp\!\left(-r \tau_{n+1}^{(m)}\right)\!u_n\!\left(X_{\tau_{n+1}^{(m)}}\right)\!\right]\end{eqnarray*}

and, taking into account (4.7), we conclude that

\begin{align*} u_{n+1}^{(m+1)}(x) & \geq \mathbb{E}_x\left[\textbf{1}_{\tau_{n+1}\leq \sigma_m}\exp\left(-r \tau_{n+1}^{(m)}\right)u_n\left(X_{\tau_{n+1}^{(m)}}\right)\right] \\ & \quad + \mathbb{E}_x\left[\textbf{1}_{\tau_{n+1}> \sigma_m}\exp\left(-r \tau_{n+1}^{(m)}\right)u_n\left(X_{\tau_{n+1}^{(m)}}\right)\right] \\ & = \mathbb{E}_x\left[\exp\left(-r \tau_{n+1}^{(m)}\right)u_n\left(X_{\tau_{n+1}^{(m)}}\right)\right] \\ & = u_{n+1}^{(m)}(x). \end{align*}

The monotonicity property of Lemma 4.1 enables us to define the function $u_{n+1}\in{\bar{\mathcal{F}}}_+$ via $u_{n+1}(x) \,:\!=\, \lim_{m\rightarrow\infty} u_{n+1}^{(m)}(x)$ for all $x \in V$, ending the iterative construction of the pair $(\mathcal{D}_{n+1}, u_{n+1})$ from $(\mathcal{D}_{n}, u_{n})$. It remains to check that:

Proof. Consider $x\in V\setminus \mathcal{D}_{n+1}$ for which $\tau^{(m+1)}_{n+1} \ge \sigma_1$, $\mathbb{P}_x$-a.s. For the Markov process X starting from x, we have, for any $m\in\mathbb{Z}_+$, $\tau^{(m+1)}_{n+1} = \sigma_1+\tau^{(m)}_{n+1}\circ \sigma_1$. The strong Markov property of X then implies that

\begin{align*} u_{n+1}^{(m+1)}(x) & = \mathbb{E}_x\left[\exp(-r\sigma_1)\mathbb{E}_{X_{\sigma_1}}\left[\exp\left(-r\tau^{(m)}_{n+1}\right)u_n\left(X_{\tau^{(m)}_{n+1}}\right)\right]\right] \\ & = \mathbb{E}_x\left[\exp(-r\sigma_1)u_{n+1}^{(m)}(X_{\sigma_1})\right] \\ & = \frac{1}{r+L(x)}\mathcal{K}[u_{n+1}^{(m)}](x) \end{align*}

by resorting again to the computations of the proof of Lemma 4.1. Monotone convergence ensures that $\lim_{m\rightarrow\infty}\mathcal{K}[u_{n+1}^{(m)}](x) = \mathcal{K}[u_{n+1}](x)$. Thus, for $x\in V\setminus \mathcal{D}_{n+1}$, $(r+L(x))u_{n+1}(x) = \mathcal{K}[u_{n+1}](x)$, as required.

The sequence $(\mathcal{D}_n)_{n\in\mathbb{Z}_+}$ is non-increasing by definition. As a consequence, we can define $\mathcal{D}_\infty \,:\!=\, \bigcap_{n\in\mathbb{Z}_+}\mathcal{D}_n$.

From Lemma 4.1, we deduce that, for any $n\in\mathbb{Z}_+$, $u_{n+1}(x) \geq u_{n+1}^{(0)}(x) = u_n(x)$ for all $x \in V$. It follows that we can define the function $u_\infty\in{\bar{\mathcal{F}}}_+$ as the non-decreasing limit of $u_n$: for all $x\in V$, $u_\infty(x) = \lim_{n\rightarrow\infty}u_n(x) \in {\bar{\mathbb{R}}}_+$.

The next two propositions establish notable properties of the pair $(\mathcal{D}_\infty,u_\infty)$.

Proposition 4.1.

\begin{eqnarray*}\mathit{For\ all}\ x \in \mathcal{D}_\infty,\quad\left\{\begin{array}{l} u_\infty(x) = \phi(x) , \\\mathcal{K}[u_\infty](x) \leq (r+L(x))u_\infty(x) . \end{array}\right.\\\mathit{For\ all}\ x \in V \setminus \mathcal{D}_\infty,\quad\left\{\begin{array}{l} u_\infty(x) \geq \phi(x) , \\\mathcal{K}[u_\infty](x) = (r+L(x))u_\infty(x).\end{array}\right.\end{eqnarray*}

Proof. Since $u_0=\phi$, the fact that $(u_n)_{n\in\mathbb{Z}_+}$ is a non-decreasing sequence implies that $u_\infty\geq \phi$. To show there is an equality on $\mathcal{D}_\infty$, it is sufficient to show that $u_n(x) = \phi(x)$ for all $n\in\mathbb{Z}_+$, $x\in \mathcal{D}_n$. This is proved by an iterative argument on $n\in\mathbb{Z}_+$. For $n=0$, it corresponds to the equality $u_0=\phi$. Assume that $u_n=\phi$ on $\mathcal{D}_n$ for some $n\in\mathbb{Z}_+$. For $x\in \mathcal{D}_{n+1}$ we have $\tau_{n+1}=0$, and thus for any $m\in\mathbb{Z}_+$ we get $\tau_{n+1}^{(m)}=0$. From (4.5), we deduce that $u^{(m)}_{n+1} = u_n(x) = \phi(x)$ for all $x\in \mathcal{D}_{n+1}$. Letting m go to infinity yields $u_{n+1}=\phi$ on $\mathcal{D}_{n+1}$.

Consider $x\in V\setminus \mathcal{D}_\infty$. There exists $N(x)\in\mathbb{Z}_+$ such that, for any $n\geq N(x)$, we have $x\in V\setminus \mathcal{D}_n$. Then, passing at the limit for large n in (4.1), we get, via another use of monotone convergence, that $(r+L(x))u_\infty(x)=\mathcal{K}[u_\infty](x)$ for all $x\in V\setminus \mathcal{D}_{\infty}$. For $x\in \mathcal{D}_\infty$ we have $x\in \mathcal{D}_{n+1}$ for any $n\in \mathbb{Z}_+$, and thus from (4.3) we have $ \mathcal{K}[u_{n}](x)\leq (r+L(x))u_{n}(x)$. Letting n go to infinity, we deduce that $\mathcal{K}[u_{\infty}](x)\leq (r+L(x))u_{\infty}(x)$ for all $x\in \mathcal{D}_\infty$.

In fact, $u_\infty$ is a strict majorant of $\phi$ on $V\setminus \mathcal{D}_\infty$, as proved in the following.

Proof. Consider $x\in V\setminus \mathcal{D}_\infty$. There exists a first integer $n\in\mathbb{Z}_+$ such that $x\in \mathcal{D}_n$ and $x\not\in \mathcal{D}_{n+1}$. From (4.1) and $x\in V\setminus \mathcal{D}_{n+1}$, we deduce that $\mathcal{K}[u_{n+1}](x) = (r+L(x))u_{n+1}(x)$. From (4.3) and $x\in V\setminus \mathcal{D}_{n+1}$, we get $\mathcal{K}[u_{n}](x) > (r+L(x))u_{n}(x)$. Putting these two inequalities together, along with the fact that $\mathcal{K}[u_{n+1}]\geq \mathcal{K}[u_n]$, we end up with $(r+L(x))u_{n+1}(x) > (r+L(x))u_{n}(x)$, which implies that $\phi(x) \leq u_{n}(x) < u_{n+1}(x) \leq u_\infty(x)$, namely $\phi(x)<u_\infty(x)$.

This argument shows that $\{x\in V: u_\infty(x)=\phi(x)\} \subset \mathcal{D}_\infty$. The reverse inclusion is deduced from Proposition 4.1.

Another formulation of the functions $u_n$, for $n\in\mathbb{N}$, will be very useful for the characterization of their limit $u_\infty$. For $n,m\in\mathbb{Z}_+$, let us modify the definition in (4.5) to define a function $\widetilde u_{n+1}^{(m)}$ as

(4.10) \begin{eqnarray}\widetilde u_{n+1}^{(m)}(x) \,:\!=\, \mathbb{E}_x\left[\exp\left(-r \tau_{n+1}^{(m)}\right)\phi\left(X_{\tau_{n+1}^{(m)}}\right)\right] \qquad \text{for all } x\in V. \end{eqnarray}

A priori, there is no monotonicity with respect to m, so we define

\begin{equation*}\widetilde u_{n+1}(x) \,:\!=\, \liminf_{m\rightarrow\infty} \widetilde u_{n+1}^{(m)}(x) \qquad \text{for all } x\in V.\end{equation*}

A key observation is the following lemma.

Proof. Since, for any $n\in\mathbb{Z}_+$, we have $u_n\geq \phi$, from a direct comparison between (4.5) and (4.10) we get that, for any $m\in\mathbb{Z}_+$, $\widetilde u_{n+1}^{(m)}\leq u_{n+1}^{(m)}$; letting m go to infinity, we deduce that

(4.11) \begin{eqnarray}\widetilde u_{n+1} \leq u_{n+1}.\end{eqnarray}

The reverse inequality is proved by an iteration over n. More precisely, since $u_0=\phi$, we get by definition that $\widetilde u_1= u_1$.

Assume that the equality $\widetilde u_n= u_n$ is true for some $n\in\mathbb{N}$; we will show that $\widetilde u_{n+1}= u_{n+1}$. For any $m\in\mathbb{Z}_+$, we have, for all $x \in V$,

\begin{align*} u_{n+1}^{(m)}(x) & = \mathbb{E}_x\left[\exp\left(-r \tau_{n+1}^{(m)}\right)u_n\left(X_{\tau_{n+1}^{(m)}}\right)\right] \\ & = \mathbb{E}_x\left[\exp\left(-r \tau_{n+1}^{(m)}\right)\widetilde u_n\left(X_{\tau_{n+1}^{(m)}}\right)\right] \\ & = \mathbb{E}_x\left[\exp\left(-r \tau_{n+1}^{(m)}\right)\liminf_{l\rightarrow\infty}\widetilde u_n^{(l)}\left(X_{\tau_{n+1}^{(m)}}\right)\right] \\ & \leq \liminf_{l\rightarrow\infty}\mathbb{E}_x\left[\exp\left(-r \tau_{n+1}^{(m)}\right)\widetilde u_n^{(l)}\left(X_{\tau_{n+1}^{(m)}}\right)\right], \end{align*}

where we used Fatou’s lemma. From (4.10) and the strong Markov property, we deduce that

\begin{align*} \mathbb{E}_x\!\left[\exp\!\left(-r \tau_{n+1}^{(m)}\right)\!\widetilde u_n^{(l)}\!\left(X_{\tau_{n+1}^{(m)}}\right)\right] & = \mathbb{E}_x\!\left[\exp\!\left(-r \tau_{n+1}^{(m)}\right)\!\mathbb{E}_{X_{\tau_{n+1}^{(m)}}}\!\left[\exp\!\left(-r \tau_{n+1}^{(l)}\right)\!\phi\!\left(X_{\tau_{n+1}^{(l)}}\right)\right]\right] \\ & = \mathbb{E}_x\left[\exp\left(-r \tau_{n+1}^{(m+l)}\right)\phi\left(X_{\tau_{n+1}^{(m+l)}}\right)\right]. \end{align*}

It follows that $u_{n+1}^{(m)}(x) \leq \liminf_{l\rightarrow\infty}\mathbb{E}_x\left[\exp\left(-r \tau_{n+1}^{(m+l)}\right)\phi\left(X_{\tau_{n+1}^{(m+l)}}\right)\right] = \widetilde u_{n+1}(x)$. It remains to let m go to infinity to get $u_{n+1}\leq \widetilde u_{n+1}$ and $u_{n+1}= \widetilde u_{n+1}$, taking into account (4.11).

Let $\mathcal{T}$ be the set of ${\bar{\mathbb{R}}}_+$-valued stopping times with respect to the filtration generated by X. For $\tau\in \mathcal{T}$ and $m\in \mathbb{Z}_+$, we define $\tau^{(m)} \,:\!=\, \sigma_m\wedge \tau$. Extending the observation of Remark 4.1, it appears that, for any $m\in\mathbb{Z}_+$, the quantity defined for all $x \in V$ by

(4.12) \begin{eqnarray}u^{(m)}(x) \,:\!=\, \sup_{\tau\in \mathcal{T}}\mathbb{E}_x\left[\exp\big(-r\tau^{(m)}\big)\phi(X_{\tau^{(m)}})\right]\end{eqnarray}

is well defined in ${\bar{\mathbb{R}}}_+$. It is non-decreasing with respect to $m\in\mathbb{Z}_+$ since, for any $\tau\in\mathcal{T}$ and any $m\in\mathbb{Z}_+$, $\tau^{(m)}$ can be written as $\widetilde\tau^{(m+1)}$, with $\widetilde \tau\,:\!=\, \tau^{(m)}\in\mathcal{T}$. Thus, we can define a function $\hat u$ by $\hat u(x) \,:\!=\, \lim_{m\rightarrow \infty} u^{(m)}(x)$ for all $x\in V$. By the definition of the value function u in (2.1), we have $u^{(m)}(x) \le u(x)$ for every $m \in \mathbb{Z}_+$ and thus $\hat u(x) \le u(x)$ for every $x \in V$. To show the reverse inequality, consider any stopping time $\tau \in \mathcal{T}$ and apply Fatou’s lemma to get

\begin{align*} \mathbb{E}_x\left[ \exp(-r\tau)\phi(X_{\tau})\right] & = \mathbb{E}_x\left[ \liminf_{m\to \infty} \exp\big(-r\tau^{(m)}\big)\phi\big(X_{\tau^{(m)}}\big)\right] \\ & \le \liminf_{m\to \infty} \mathbb{E}_x\left[ \exp\big(-r\tau^{(m)}\big)\phi\big(X_{\tau^{(m)}}\big)\right] \\ & \le \liminf_{m\to \infty} u^{(m)}(x)\\ & \le \hat u(x).\end{align*}

Therefore, the value function u coincides with the limit of the sequence $(u^{(m)})_{m \in \mathbb{Z}_+}$. At this stage, we recall the definition of the stopping region,

(4.13) \begin{eqnarray}D \,:\!=\, \{x\in V\;:\;u(x)=\phi(x)\}.\end{eqnarray}

We are now in a position to state our main result.

Proof. It is sufficient to show that $u_\infty=u$, since $\mathcal{D}_\infty=D$ will then follow from Proposition 4.2 and (4.13).

We begin by proving the inequality $u_\infty\leq u$. Fix some $x\in V$. By considering in (4.12) the stopping time $\tau\,:\!=\,\tau_{n+1}$ defined in (4.4), we get, for any given $m\in \mathbb{Z}_+$,

\begin{eqnarray*}u^{(m)}(x) \geq \mathbb{E}_x\left[\exp\left(-r\tau_{n+1}^{(m)}\right)\phi\left(X_{\tau_{n+1}^{(m)}}\right)\right] = \widetilde u_{n+1}^{(m)}(x)\end{eqnarray*}

considered in (4.10). Taking Lemma 4.3 into account, we deduce that $u^{(m)}(x) \geq u_{n+1}^{(m)}(x)$ and, letting m go to infinity, we get $u(x)\geq u_{n+1}(x)$. It remains to let n go to infinity to show that $u(x)\geq u_{\infty}(x)$.

To prove the reverse inequality $u_\infty\geq u$, we will show by induction that for every $x \in V$, every $m \in \mathbb{Z}_+$, and every $\tau \in \mathcal{T}$, we have

(4.14) \begin{eqnarray}\mathbb{E}_x \left[ \exp(-r(\sigma_m \wedge \tau)u_\infty(X_{\sigma_m \wedge \tau}) \right] \le u_\infty(x).\end{eqnarray}

For $m=1$, because $u_\infty(X_\tau)=u_\infty(x)$ on the set $\{\tau < \sigma_1\}$,

\begin{align*} \mathbb{E}_x \left[ \exp(-r(\sigma_1 \wedge \tau)u_\infty(X_{\sigma_1 \wedge \tau}) \right] & = \mathbb{E}_x \left[ \exp(-r\sigma_1)u_\infty(X_{\sigma_1})\textbf{1}_{\sigma_1\le \tau} \right] \\ & \quad + \mathbb{E}_x \left[ \exp(-r \tau)u_\infty(X_{ \tau})\textbf{1}_{\tau < \sigma_1} \right] \\ & = \mathbb{E}_x \left[ \exp(-r \sigma_1)u_\infty(X_{\sigma_1})\textbf{1}_{\sigma_1\le \tau} \right] \\ & \quad + u_\infty(x)\mathbb{E}_x \left[ \exp(-r \tau)\textbf{1}_{\tau < \sigma_1} \right] \\ & = \mathbb{E}_x \left[ \exp(-r \sigma_1)u_\infty(X_{\sigma_1}) \right]+u_\infty(x) \mathbb{E}\left[ \exp(-r \tau)\textbf{1}_{\sigma_1 > \tau}\right] \\ & \quad -\mathbb{E}\left[ \exp(-r \sigma_1)u_\infty(X_{\sigma_1})\textbf{1}_{\sigma_1 >\tau}\right].\end{align*}

Focusing on the third term in the final equality, we observe that on the set $\{\tau < \sigma_1\}$ we have $\sigma_1=\tau+\hat\sigma_1 \circ\theta_\tau$, where $\hat\sigma_1$ is an exponential random variable with parameter L(x) independent of $\tau$. Therefore, the strong Markov property yields

\begin{align*} \mathbb{E}\left[ \exp(-r \sigma_1)u_\infty(X_{\sigma_1})\textbf{1}_{\sigma_1 >\tau}\right]&=\mathbb{E}_x\left[ \exp(-r \tau)\mathbb{E}_x \left[ \exp(-r \hat\sigma_1)u_\infty(X_{\hat\sigma_1}) \right]\textbf{1}_{\sigma_1 >\tau}\right]\\ &=\frac{\mathcal{K}[u_\infty](x)}{r+L(x)}\mathbb{E}_x\left[ \exp(-r \tau)\textbf{1}_{\sigma_1 > \tau}\right].\end{align*}

Hence,

\begin{align*} \mathbb{E}_x \left[ \exp(-r(\sigma_1 \wedge \tau)u_\infty(X_{\sigma_1 \wedge \tau}) \right] & = \frac{\mathcal{K}[u_\infty](x)}{r+L(x)}\left( 1- \mathbb{E}_x\left[ \exp(-r \tau)\textbf{1}_{\sigma_1 > \tau}\right]\right) \\ & \quad + u_\infty(x) \mathbb{E}_x\left[ \exp(-r \tau)\textbf{1}_{\sigma_1 > \tau}\right] \\&\le u_\infty(x) ,\end{align*}

where the last inequality follows from Proposition 4.1. This proves the assertion for $m=1$. Assume now that for every $x \in V$ and every $\tau \in \mathcal{T}$,

\begin{eqnarray*}\mathbb{E}_x \left[ \exp(-r(\sigma_m \wedge \tau))u_\infty(X_{\sigma_m \wedge \tau}) \right] \le u_\infty(x).\end{eqnarray*}

Observing that $\sigma_{m+1}\wedge \tau=\sigma_{m}\wedge \tau+(\sigma_{1}\wedge \tau)\circ \theta_{\sigma_{m}\wedge \tau}$, we get

\begin{align*} \mathbb{E}_x [ \exp(-r(\sigma_{m+1} & \wedge \tau))u_\infty(X_{\sigma_{m+1} \wedge \tau}) ] \\ & = \mathbb{E}_x \left[ \exp(-r(\sigma_m \wedge \tau))\mathbb{E}_{X_{\sigma_m \wedge \tau}}\left( \exp(-r(\sigma_1 \wedge \tau))u_\infty(X_{\sigma_1 \wedge \tau}) \right) \right] \\ & \le \mathbb{E}_x \left[ \exp(-r(\sigma_m \wedge \tau)) u_\infty(X_{\sigma_m \wedge \tau} )\right] \\ & \le u_\infty(x),\end{align*}

which ends the argument by induction. To conclude, we take the limit of the right-hand side of inequality (4.14) to obtain $u(x) \le u_\infty(x)$ for every $x \in V$.

We close this section by giving a very simple example on the countable state space $\mathbb{Z}$ with a bounded reward function $\phi$ such that the recursive algorithm does not stop in finite time because it only eliminates one point at each step.

Example 4.1 Let $(X_t)_{t\geq 0}$ be a birth–death process with the generator on $\mathbb{Z}$

\begin{eqnarray*}\left\{\begin{array}{cc}L(x,x+1)&=\lambda \ge 0,\\L(x,x-1)&=\mu \ge 0, \\L(x)&=\lambda + \mu.\end{array}\right.\end{eqnarray*}

We define the reward function as

\begin{eqnarray*}\phi(x)=\left\{\begin{array}{c}0 \hbox{ for } x \le 0 , \\1 \hbox{ for } x = 1 , \\2 \hbox{ for } x \ge 2.\end{array}\right.\end{eqnarray*}

We assume $r=0$ and $\lambda \ge \mu$. Therefore, $\mathcal{D}_1=\mathbb{Z}\setminus \{1\}$. It is easy to show that $u_1(1) = \frac{2\lambda}{\lambda+\mu}$ and thus $\mathcal{L}[u_1](0) = \lambda u_1(1)>0$. Therefore, $\mathcal{D}_2=\mathbb{Z}\setminus \{1,0\}$. At each step $n \in \mathbb{Z}_+$, because $u_n(1-n)>0$ the algorithm will only remove the integer $1-n$ in the set $\mathcal{D}_n$. Therefore, it will not reach the stopping region $\mathcal{D}=\{2,3,\ldots\}$ in finite time.

4.2. Measurable state space

Up to now we have only considered continuous-time Markov chains with a discrete state space. It is not difficult to see that the results of the previous section can be extended to the case where the state space of the Markov chain is a measurable space. More formally, we consider a non-negative finite kernel K on a measurable state space $(V,\mathcal{V})$. It is a mapping $K: V\times\mathcal{V} \ni (x,S) \mapsto K(x,S)\in\mathbb{R}_+$ such that

• • for any $x\in V$, $K(x,\cdot)$ is a non-negative finite measure on $(V,\mathcal{V})$ (because $K(x,V)\in \mathbb{R}_+$);

• • for any $S\in \mathcal{V}$, $K(\cdot,S)$ is a non-negative measurable function on $(V,\mathcal{V})$.

For any probability measure m on V, let us associate with K a continuous-time Markov process $X\,:\!=\,(X_t)_{t\geq 0}$ whose initial distribution is m. First we set $\sigma_0\,:\!=\,0$, and $X_0$ is sampled according to m. Then, we consider an exponential random variable $\sigma_1$ of parameter $K(X_0)\,:\!=\, K(X_0,V)$. If $K(X_0)=0$, we have a.s. $\sigma_1=+\infty$ and we take $X_t\,:\!=\, X_0$ for all $t> 0$, as well as $\sigma_n\,:\!=\,+\infty$ for all $n\in\mathbb{N}$, $n\geq 2$. If $K(X_0)>0$, we take $X_t\,:\!=\, X_0$ for all $t\in(0,\sigma_1)$ and we sample $X_{\sigma_1}$ on $V\setminus\{X_0\}$ according to the probability distribution $K(X_0,\cdot)/K(X_0)$. Next, still in the case where $\sigma_1<+\infty$, we sample an inter-time $\sigma_2-\sigma_1$ as an exponential distribution of parameter $K(X_{\sigma_1})$. If $K(X_{\sigma_1})=0$, we have a.s. $\sigma_2=+\infty$ and we take $X_t\,:\!=\, X_{\sigma_1}$ for all $t\in(\sigma_1,+\infty)$, as well as $\sigma_n\,:\!=\,+\infty$ for all $n\in\mathbb{N}$, $n\geq 3$. If $K(X_{\sigma_1})>0$, we take $X_t\,:\!=\, X_0$ for all $t\in(\sigma_1,\sigma_2)$ and we sample $X_{\sigma_2}$ on $V\setminus\{X_{\sigma_1}\}$ according to the probability distribution $K(X_{\sigma_1},\cdot)/K(X_{\sigma_1}))$. We continue by following the same procedure.

In particular, we get a non-decreasing family $(\sigma_n)_{n\in\mathbb{Z}_+}$ of jump times taking values in ${\bar{\mathbb{R}}}_+\,:\!=\,\mathbb{R}_+\sqcup\{+\infty\}$. Denote the corresponding exploding time $\sigma_{\infty} \,:\!=\, \lim_{n\rightarrow\infty} \sigma_n \in {\bar{\mathbb{R}}}_+$. When $\sigma_\infty<+\infty$, we must still define $X_t$ for $t\geq \sigma_\infty$. So introduce $\triangle$ as a cemetery point not belonging to V and denote $\bar V\,:\!=\, V\sqcup\{\triangle\}$. We take $X_t\,:\!=\, \triangle$ for all $t\geq \sigma_\infty$ to get a $\bar V$-valued process X.

Let $\mathcal{B}$ be the space of bounded and measurable functions from V to $\mathbb{R}$. For $f \in \mathcal{B}$, the infinitesimal generator of $X=(X_t)_{t\geq 0}$ is given by

\begin{eqnarray*}\mathcal{L}[f](x) = \int_V f(y)K(x,\textrm{d} y)-K(x)f(x) \,:\!=\, \mathcal{K}[f](x)-K(x)f(x).\end{eqnarray*}

As in Section 4.1, we set some payoff function $\phi\in{\bar{\mathcal{F}}}_+\setminus\{0\}$ and $r>0$. We will construct a subset $\mathcal{D}_\infty\subset V$ and a function $u_\infty\in{\bar{\mathcal{F}}}_+$ by our recursive algorithm as follows.

We begin by taking $\mathcal{D}_0\,:\!=\, V$ and $u_0\,:\!=\, \phi$. Next, let us assume that $\mathcal{D}_n\subset V$ and $u_n\in{\bar{\mathcal{F}}}_+$ have been built for some $n\in\mathbb{Z}_+$ such that $(r+L(x))u_n(x) = \mathcal{K}[ u_n](x)$ for all $x\in V\setminus \mathcal{D}_n$, and $u_n(x) = \phi(x)$ for all $x \in \mathcal{D}_n$. Observe that it is trivially true for $n=0$. Then, we define the subset $\mathcal{D}_{n+1} \,:\!=\, \{x\in \mathcal{D}_n: \mathcal{K}[u_n](x) \leq (r +K(x))u_n(x)\}$, where the inequality is understood in ${\bar{\mathbb{R}}}_+$. Next, we consider the stopping time $\tau_{n+1} \,:\!=\, \inf\{t\geq 0: X_t\in \mathcal{D}_{n+1}\}$ with the usual convention that $\inf \emptyset =+\infty$. It is easy to check that the proofs of Section 4.1 are directly extendable to this setting.

5.1. Optimal stopping with random intervention times

We revisit [Reference Dupuis and Wang7], which considers a class of optimal stopping problems that can only be stopped at Poisson jump times. (We also mention two recent generalizations of the problem in [Reference Lempa17,Reference Menaldi and Robin18] for which the forward algorithm is applicable.) Consider a probability space $(\Omega,\mathcal{F}\,:\!=\,(\mathcal{F}_t)_{t\geq 0},\mathbb{P})$ satisfying the usual conditions. For $x>0$, let $(S_t^x)_{t\geq 0}$ be a geometric Brownian motion solving the stochastic differential equation

(5.1) \begin{equation} \frac{\textrm{d} S_t^x}{S_t^x} = b\,\textrm{d} t+\sigma\,\textrm{d} W_t,\qquad S^x_0 = x,\end{equation}

where $W=(W_t)_{t\geq 0}$ is a standard $\mathcal{F}$-Brownian motion and b and $\sigma>0$ are constants. When $x=0$ we take $S^0_t=0$ for all times $t\geq 0$. The probability space is rich enough to carry an $\mathcal{F}$-Poisson process $N=(N_t)_{t\geq 0}$ with intensity $\lambda>0$ that is assumed to be independent of W. The jump times of the Poisson process are denoted by $T_n$, with $T_0=0$.

In [Reference Dupuis and Wang7] the optimal stopping problem $u(0,x) = \sup_{\tau \in \mathcal{S}_0} \mathbb{E}\left[ \textrm{e}^{-r\tau}(S^x_\tau-K)_+\right]$ is considered, where $r >b$ and $\mathcal{S}_0$ is the set of $\mathcal{F}$-adapted stopping times $\tau$ for which $\tau(\omega)=T_n(\omega)$ for some $n\in \mathbb{Z}_+$. Similarly to [Reference Dupuis and Wang7], let us define $\mathcal{G}_n=\mathcal{F}_{T_n}$ and the $\mathcal{G}_n$-Markov chain $Z_n=(T_n,S^x_{T_n})$ to have $u(0,x) = \sup_{N \in \mathcal{N}_0} \mathbb{E}\left[ \psi(Z_N) \mid Z_0=(0,x)\right]$, where $\psi(t,x) = \textrm{e}^{-rt}(x-K)_+$ and $\mathcal{N}_0$ is the set of $\mathcal{G}$-stopping times with values in $\mathbb{Z}_+ $. To enter the continuous-time framework of the previous sections and start our recursive approach, we need to compute the infinitesimal generator $\widetilde{\mathcal{L}}$ of the continuous Markov chain $\widetilde Z=(\widetilde Z_t)_{t \ge 0}$ with $\Big(\widetilde Z_t=\sum_{i=0}^{\widetilde N_t} Z_n\Big)_{t\geq 0}$, an independent Poisson process $\widetilde N=(\widetilde N_t)_{t \ge 0}$ with intensity 1, and state space $V=\mathbb{R}_+\times\mathbb{R}_+$ in order to define $\widetilde{\mathcal{D}}_1\,:\!=\,\{(t,x)\in V:\widetilde{\mathcal{L}}[\psi](t,x) \le 0\}$. To do this we use the following remark.

Remark 5.1. Our methodology also applies for discrete Markov chains according to the Poissonization technique that we recall briefly. Consider a Poisson process $N=(N_t)_{t\ge 0}$ of intensity $\lambda$ and a discrete Markov chain $(X_n)_{n\in \mathbb{Z}_+}$ with transition matrix or kernel P. Assume that $(X_n)_{n\in \mathbb{Z}_+}$ and $N=(N_t)_t$ are independent. Then, the process $\widetilde X_t=\sum_{n=0}^{N_t} X_n$ is a continuous-time Markov chain with generator $\mathcal{L} \,:\!=\, \lambda (P-\textrm{Id})$, where Id is the identity operator.

Let f be a bounded and measurable function on V. According to Remark 5.1, the infinitesimal generator $\widetilde{\mathcal{L}}$ of the continuous Markov chain $\widetilde Z=(\widetilde Z_t)_{t \ge 0}$ is

\begin{eqnarray*}\widetilde{\mathcal{L}}[f](t,x) = \lambda \int_0^{+\infty} \mathbb{E}\left[ f(t+u,S_u^x )\right]\textrm{e}^{-\lambda u}\,\textrm{d} u-f(t,x).\end{eqnarray*}

Because $\psi(t,x)=\textrm{e}^{-rt}\phi(x)$ with $\phi(x)=(x-K)_+$, we have

\begin{eqnarray*}\widetilde{\mathcal{L}}[\psi](t,x) = \textrm{e}^{-rt}\left( \lambda R_{r+\lambda}[\phi](x)-\phi(x)\right),\end{eqnarray*}

where $R_{r+\lambda}[\phi](x) = \int_0^{+\infty} \mathbb{E}[\phi(S_u^x)]\textrm{e}^{-(r+\lambda)u}\,\textrm{d} u$ is the resolvent of the continuous Markov process $S^x=(S_t^x)_{t\geq 0}$. Therefore, we have $\widetilde{\mathcal{D}}_1=\mathbb{R}_+\times\mathcal{D}_1$, with

\begin{eqnarray*}\mathcal{D}_1 \,:\!=\, \{x \in \mathbb{R}_+,\, \lambda R_{r+\lambda}[\phi](x)-\phi(x)\le 0\}.\end{eqnarray*}

First, we observe that $\mathcal{D}_1$ is the interval $[x_1,+\infty[$. Indeed, let us define $\eta(x) \,:\!=\, \lambda R_{r+\lambda}[\phi](x)-\phi(x)$. Clearly, $\eta(x)>0$ for $x\le K$. Moreover, for $x>K$,

\begin{eqnarray*}\eta^\prime(x) = \left(\lambda\int_0^{+\infty} \partial_x\mathbb{E}[\phi(S_u^x)]\textrm{e}^{-(r+\lambda)u}\,\textrm{d} u\right)-\phi'(x).\end{eqnarray*}

It is well known that $\partial_x \mathbb{E}[\phi(S_u^x)] \le \textrm{e}^{bu}$ for any $x\geq K$ and thus, because $r>b$,

\begin{eqnarray*}\eta^\prime(x)\le \frac{\lambda}{r-b+\lambda}-1 < 0,\end{eqnarray*}

which implies that $\eta$ is a decreasing function on $[K,+\infty)$. It follows that if $\mathcal{D}_1$ is not empty, then it will be an interval of the form $[x_1,+\infty)$. Now,

\begin{eqnarray*}\eta(x) = x\left(\lambda\int_0^{+\infty}\frac{ \mathbb{E}[\phi(S_u^x)]}{x}\textrm{e}^{-(r+\lambda)u}\,\textrm{d} u\right)-\phi(x).\end{eqnarray*}

Because $\displaystyle{\frac{ \mathbb{E}[\phi(S_u^x)]}{x}} \le \textrm{e}^{bu}$ we have $\eta(x) \le \left(\frac{\lambda}{r-b+\lambda}-1\right)x+K$, and therefore $\eta(x)\le 0$ for $x \ge \left(1+\frac{\lambda}{r-b}\right)K$, which proves that $\mathcal{D}_1$ is not empty.

We will now prove by induction that for every $n \in \mathbb{N}$, $\widetilde{\mathcal{D}}_n=\mathbb{R}_+\times\mathcal{D}_n$ with $\mathcal{D}_n=[x_n,+\infty)$ and $x_n > K$. Assume that it is true for some $n\in\mathbb{N}$. Following our monotone procedure with Remark 4.2, we define the solution $u_{n+1}:\mathbb{R}_+\times\mathbb{R}_+\rightarrow\mathbb{R}$ of the equation

\begin{eqnarray*}\left\{\begin{array}{ll} \widetilde{\mathcal{L}} [u_{n+1}] = 0 & \quad\hbox{ on } \widetilde{\mathcal{D}}_{n}^{\textrm{c}} , \\ u_{n+1} = \psi & \quad\hbox{ on } \widetilde{\mathcal{D}}_n\end{array}\right.\end{eqnarray*}

and define $\widetilde{\mathcal{D}}_{n+1} \,:\!=\, \{ (t,x) \in \widetilde{\mathcal{D}}_n,\, \widetilde{\mathcal{L}}[ u_{n+1}] \le 0 \}$. Let us check that $\widetilde{\mathcal{D}}_{n+1}=\mathbb{R}_+\times\mathcal{D}_{n+1}$ with $\mathcal{D}_{n+1}=[x_{n+1},+\infty)$ and $x_{n+1} \ge x_n$.

To do this, we look for a function of the form $u_{n+1}(t,x) = \exp(-rt)v_{n+1}(x) $ for all $(t,x)\in\mathbb{R}_+\times\mathbb{R}_+$. We end up with the following equation on $v_{n+1}$:

\begin{eqnarray*} \left\{\begin{array}{rl} \lambda R_{r+\lambda}[v_{n+1}]-v_{n+1} = 0 & \quad \hbox{ on $ \mathcal{D}_n^{\textrm{c}}$} , \\ v_{n+1} = \phi & \quad\hbox{ on $\mathcal{D}_n$}\end{array}\right.\end{eqnarray*}

or, equivalently (see [Reference Ethier and Kurtz10, Proposition 2.1, p. 10]),

\begin{eqnarray*}\left\{\begin{array}{rl} \mathcal{L}^S[v_{n+1}]-r v_{n+1} = 0 & \quad \hbox{ on $ \mathcal{D}_n^{\textrm{c}}$} , \\ v_{n+1} = \phi & \quad\hbox{ on $\mathcal{D}_n$} ,\end{array}\right.\end{eqnarray*}

where $\mathcal{L}^S$ is the infinitesimal generator of $S^x=(S_t^x)_{t\geq 0}$, that is, acting on any $f\in\mathcal{C}^2(\mathbb{R}_+)$ via $\mathcal{L}^S[f](x) = \frac{\sigma^2x^2}{2}f^{\prime\prime}(x)+bxf^{\prime}(x)$. With this formulation we see that $v_{n+1}(x) = \mathbb{E}_x\big[\exp$$\big(-r\tau_{x_n}^x\big)\phi\big(S^x_{\tau_{x_n}}\big)\big]$ for all $x\in\mathbb{R}_+$, where $\tau_{x_n}$ is the first hitting time of $\mathcal{D}_n=[x_n,+\infty[$ by our induction hypothesis.

By definition, we have

\begin{align*} \widetilde{\mathcal{D}}_{n+1} & \,:\!=\, \{(t,x)\in\widetilde{\mathcal{D}}_n\;:\; \widetilde{\mathcal{L}} [u_{n+1}](t,x)\leq 0\} \\ & = \mathbb{R}_+\times\{x\in\mathcal{D}_n\;:\; \lambda R_{r+\lambda}[v_{n+1}](x)-v_{n+1}(x)\leq 0\} \\ & = \mathbb{R}_+\times\{x\in\mathcal{D}_n\;:\; \lambda R_{r+\lambda}[v_{n+1}](x)-\phi(x)\leq 0\} ,\end{align*}

and thus $\widetilde{\mathcal{D}}_{n+1}=\mathbb{R}_+\times\mathcal{D}_{n+1}$ where $\mathcal{D}_{n+1} \,:\!=\, \{x\in\mathcal{D}_n\;:\;\zeta_{n+1}(x)\leq 0\}$ with $\zeta_{n+1}(x) \,:\!=\, \lambda R_{r+\lambda}[v_{n+1}](x)-\phi(x)$ for all $x\geq 0$.

To prove that $\mathcal{D}_{n+1}$ is of the form $[x_{n+1},+\infty)$, we begin by showing that, for all $y \geq x \geq x_n$,

(5.2) \begin{eqnarray}\zeta_{n+1}(x)=0 \ \Rightarrow\ \zeta_{n+1}(y)\leq 0.\end{eqnarray}

To do so, we introduce the hitting time $\tau_x^y \,:\!=\, \inf\{t\geq 0: S_t^y=x\}$. Recall that the solution of (5.1) is given by $S_t^x = x\exp\left(\sigma W_t-\frac{\sigma^2}{2}t +bt\right)$ for all $x\in\mathbb{R}_+$ and $t\geq 0$. It follows that $\tau_x^y = \inf\big\{t\geq 0\;:\;W_t-\frac{\sigma^2}{2}t +bt=\ln(x/y)\big\}$. In particular, $\tau^y_x$ takes the value $+\infty$ with a positive probability when $b>\sigma^2/2$, but otherwise $\tau^y_x$ is a.s. finite. Nevertheless, taking into account that for any $z\geq x_n$ we have $v_{n+1}(z)=\phi(z)$, we can always write, for $ y\geq x\geq x_n$,

\begin{align*} R_{r+\lambda}[v_{n+1}](y) & = \mathbb{E}\left[\int_0^\infty v_{n+1}(S_u^y)\textrm{e}^{-(r+\lambda) u}\, \textrm{d} u\right] \\ & = \mathbb{E}\left[\int_0^{\tau_{x}^y}v_{n+1}(S_u^y)\textrm{e}^{-(r+\lambda) u}\, \textrm{d} u+\int_{\tau_{x}^y}^\infty v_{n+1}(S_u^y)\textrm{e}^{-(r+\lambda) u}\, \textrm{d} u\right] \\ & = \mathbb{E}\left[\int_0^{\tau_{x}^y}\phi(S_u^y)\textrm{e}^{-(r+\lambda) u}\, \textrm{d} u\right] + \mathbb{E}\left[\textrm{e}^{-(r+\lambda)\tau_{x}^y}\!\!\int_{0}^\infty\!\!\!\!\!\! v_{n+1}(S_{\tau_{x}^y+u}^y)\textrm{e}^{-(r+\lambda) u}\, \textrm{d} u\right] \\ & = \mathbb{E}\left[\int_0^{\tau_{x}^y}\phi(S_u^y)\textrm{e}^{-(r+\lambda) u}\, \textrm{d} u\right] + \mathbb{E}\left[\textrm{e}^{-(r+\lambda)\tau_{x}^y}\right]R_{r+\lambda}[v_{n+1}](x), \end{align*}

where we use the strong Markov property with the stopping time $\tau_{x}^y$. Reversing the same argument, with $v_{n+1}$ replaced by $\phi$, we deduce that

\begin{align*} R_{r+\lambda}[v_{n+1}](y) & = \mathbb{E}\left[\int_0^{\tau_{x}^y}\phi(S_u^y)\textrm{e}^{-(r+\lambda) u}\, \textrm{d} u\right] + \mathbb{E}\left[\textrm{e}^{-(r+\lambda)\tau_{x}^y}\right]R_{r+\lambda}[\phi](x) \\ & \quad + \mathbb{E}\left[\textrm{e}^{-(r+\lambda)\tau_{x}^y}\right]\big(R_{r+\lambda}[v_{n+1}](x)-R_{r+\lambda}[\phi](x)\big) \\ & = R_{r+\lambda}[\phi](y)+\mathbb{E}\left[\textrm{e}^{-(r+\lambda)\tau_{x}^y}\right]\big(R_{r+\lambda}[v_{n+1}](x)-R_{r+\lambda}[\phi](x)\big). \end{align*}

Thus, $\zeta_{n+1}(y) = \lambda R_{r+\lambda}[\phi](y)-\phi(y)+\lambda\mathbb{E}\left[\textrm{e}^{-(r+\lambda)\tau_{x}^y}\right](R_{r+\lambda}[v_{n+1}](x)-R_{r+\lambda}[\phi](x))$. In the first part of the above proof, to get the existence of $x_1$ we showed that the mapping $\zeta_1\,:\!=\, R_{r+\lambda}[\phi]-\phi$ is non-increasing on $[x_1,+\infty)\supset [x_n,+\infty)$, and in particular $\lambda R_{r+\lambda}[\phi](y)-\phi(y) \leq \lambda R_{r+\lambda}[\phi](x)-\phi(x) = \zeta_1(x)$, so we get

\begin{eqnarray*}\zeta_{n+1}(y) \leq \zeta_1(x)\mathbb{E}\left[\textrm{e}^{-(r+\lambda)\tau_{x}^y}\right]\big(\lambda R_{r+\lambda}[v_{n+1}](x)-\lambda R_{r+\lambda}[\phi](x)\big).\end{eqnarray*}

Assume now that $\zeta_{n+1}(x)=0$. This means that $\lambda R_{r+\lambda}[v_{n+1}](x) = \phi(x)$, implying that

\begin{align*} \zeta_{n+1}(y) & \leq \zeta_1(x)+ \mathbb{E}\left[\textrm{e}^{-(r+\lambda)\tau_{x}^y}\right]\big(\phi(x)-\lambda R_{r+\lambda}[\phi](x)\big) \\ & \leq \left(1-\mathbb{E}\left[\textrm{e}^{-(r+\lambda)\tau_{x}^y}\right]\right) \zeta_1(x) \\ & \leq 0, \end{align*}

since $x\geq x_n\geq x_1$, so that $\zeta_1(x)\leq 0$. This proves (5.2) and ends the induction argument.

According to Proposition 4.1 and Theorem 4.1 (more precisely its extension given in Section 4.2), the value function u and the stopping set $\mathcal{D}=\{x \in \mathbb{R}_+,\,u(x)=\phi(x)\}$ satisfy $u(t,x)=\textrm{e}^{-rt}v(x)$, where $v(x) = \lambda R_{r+\lambda}[v](x)$ on $\mathbb{R}_+ \setminus \mathcal{D}$, $v = \phi$ on $\mathcal{D}$, and $\mathcal{D} = {\bigcap_{n\in \mathbb{N}}} [x_n,+\infty[$. The stopping set is the interval $[x^*,+\infty[$, which may be empty if $x^*$ is not finite. Using [Reference Ethier and Kurtz10, Proposition 2.1] again, we obtain $\mathcal{L}^S[v](x)-rv(x) = 0$ for all $x \in \mathbb{R}_+ \setminus \mathcal{D}$. Therefore, the function w given by $w(x)\,:\!=\, \lambda R_{r+\lambda}[v](x)$ for any $x\in(0,+\infty)$ also satisfies $\mathcal{L}^S[w](x)-rw(x) = 0$ for all $x \in \mathbb{R}_+ \setminus \mathcal{D}$. Moreover, $(-\mathcal{L}^S+(r+\lambda))[w](x) = \lambda v(x) = \lambda \phi(x)$ for all $x \in \mathcal{D}$, which yields $\mathcal{L}^S[w](x)-rw(x)+\lambda (\phi(x)-w(x)) = 0$ for all $x \in \mathcal{D}$. This corresponds to the variational inequalities (3.4)–(3-9) solved in [Reference Dupuis and Wang7, p. 6], establishing that $\mathcal{D}$ is non-empty.

5.2. Stochastic time constraints

Our last example builds on [Reference Egloff and Leippold8]. Let us consider a standard Brownian motion $B\,:\!=\,(B_t)_{t\geq 0}$ on a filtered probability space $(\Omega,\mathcal{F},\mathcal{F}_t,\mathbb{P})$, and denote by $\mathcal{T}_0$ the set of all $\mathcal{F}_t$-stopping times. We are interested in the following optimal stopping problem with stochastic constraints:

(5.3) \begin{equation}v(x)=\sup_{\tau \in \mathcal{T}_{\mathbb{Z}_+}} \mathbb{E}\left[ \phi(X^x_{\tau \wedge \tau_0}) \right],\end{equation}

where $x\geq 0$, $X^x_t=x+B_t$ for all $t\ge 0$, $\phi$ is a positive function defined on $\mathbb{Z}_+$, $\tau_0=\inf\{t \ge 0 : X^x_t=0\}$, and $\mathcal{T}_{\mathbb{Z}_+}=\{\tau \in \mathcal{T}_0 : X^x_\tau \in {\mathbb{Z}_+} \}$. In words, the holder of such an American option can only exercise when the Brownian motion has integer values, and this as long as the Brownian motion remains non-negative. The idea is to embed the constrained optimal stopping problem (5.3) into an unconstrained stopping problem written on a birth–death process killed at 0. To do this, let us define the continuous increasing process

(5.4) \begin{eqnarray}L_t \,:\!=\, \sum_{n\in {\mathbb{Z}_+}} L_t^{(n)}(X),\end{eqnarray}

where $L_t^{(n)}(X)$ is the local time of X at $n\in\mathbb{Z}_+$, and its pseudo-inverse $A_t=\inf\{ s>0 : L_s>t \}$.

Let us define the process $Y\,:\!=\,(Y_t)_{t\geq 0}\,:\!=\,(X^x_{A_t})_{t\ge 0}$ starting from $X_{A_0}^x\in\mathbb{Z}_+$. The process $(Y_t)_{t\geq 0}$ is a continuous-time Markov chain with values in ${\mathbb{Z}_+}$ whose generator is denoted by $\mathcal{L}$. Observe that when $x\notin\mathbb{Z}_+$ we can suppose that Y has immediately jumped from the entrance state x at $0_-$ to $\lfloor x\rfloor$ or $\lfloor x\rfloor+1$, where $\lfloor x\rfloor$ is the integer part of x. Because the Brownian motion has continuous paths, it is clearly a birth–death process. By the strong Markov property and the translation invariance of the Brownian motion, the infinitesimal generator of X is fully determined by the two numbers $\mathcal{L}(n,n+1)=\mathcal{L}(1,2)$ and $\mathcal{L}(n,n-1)=\mathcal{L}(1,0)$ for all $n \ge 1$. Moreover, by symmetry we have $\mathcal{L}(1,2)=\mathcal{L}(1,0)$.

Proposition 5.1. Let $T\,:\!=\,\inf\{t \ge 0 : \vert B_t\vert=1\}$ be the hitting time of $\{-1,1\}$ by the Brownian motion. Then

\begin{equation*}\mathcal{L}(1)=\frac1{\mathbb{E}\big(L^{(0)}_{T}(B)\big)}=1,\end{equation*}

where we recall that $\mathcal{L}(1)=\mathcal{L}(1,2)+\mathcal{L}(1,0)$ is the total jump rate of Y from 1 (and from all $n \ge 1$). We deduce that $\mathcal{L}(1,2)=\mathcal{L}(1,0)=\frac{1}{2}$.

Proof. Take any $n \ge 1$ and consider $\sigma\,:\!=\,\inf\{t\geq 0: \vert Y_t-n\vert=1\}$ when $Y_0=n=X_0^n$. Note that, for any $t\geq 0$, on the right-hand side of (5.4) there is only a finite number of terms which are non-zero (this statement, like the following ones, are to be understood a.s.). It follows that the mapping $\mathbb{R}_+\ni t \mapsto L_t$ is continuous, by continuity of each of the local times $(L^{(n)}_t)_{t\geq 0}$, for $n\in{\mathbb{Z}_+}$. As a consequence, $L_{A_t}=t$ for any $t\geq 0$. Thus, $\sigma = \inf\{L_{A_t}\geq 0: \vert B_{A_t}\vert=1\} = L_{\inf\{A_t: \vert B_{A_t}\vert=1\}}$. A priori, we only have $ \inf\{A_t: \vert B_{A_t}\vert=1\}\geq \inf\{s\geq 0: \vert B_s\vert=1\}$, because the former infimum is on a smaller set than the latter. We deduce that $\sigma \geq L_{\inf\{s\geq 0: \vert B_s\vert=1\}} = L_T$.

Conversely, note that by the strong Markov property applied to T we have, for any $\epsilon>0$, $L_{T+\epsilon}>L_T$, because any level set of the Brownian motion has no isolated point, so that $A_{L_T}=T$ and $\vert B_{A_{L_T}}\vert =\vert B_T\vert =1$. In particular, we get $\tau = \inf\{L_{A_t}\geq 0: \vert B_{A_t}\vert=1\} \leq L_{A_{L_T}} = L_T$.

Putting together these two inequalities, we obtain $\tau =L_T$. It is clear on one hand that $L_T=L^{(0)}_T(B)$ by the definition of T, and on the other hand that the total jump rate from n of Y satisfies $\mathcal{L}(n)=1/\mathbb{E}[\sigma]$. These facts lead to the first equality.

Next, observe that the process $(M_t)_{t\geq 0}\,:\!=\,\big(|B_t|-L_t^{(0)}(B)\big)_{t\geq 0}$ is a Brownian motion by Tanaka’s formula. Because the stopping time T is integrable, the optional sampling theorem gives $\mathbb{E}\big(L^{(0)}_{T}(B)\big)=\mathbb{E}\big(|B_{T}|\big)=1$, which completes the proof.

We are in a position to embed the constrained optimal stopping problem (5.3) in the setting of unconstrained optimal stopping problems on a birth–death process killed at 0. We first build on [Reference Egloff and Leippold8, Theorem 3.3] to characterize the optimal stopping time for (5.3). Let us consider the hitting time $ H_{\mathbb{Z}_+} \,:\!=\, \inf\{ t \ge 0 : X^x_t \in {\mathbb{Z}_+}\}$ and the function h given by $h(x) \,:\!=\, \mathbb{E}\left[\phi\left(X^x_{H_{\mathbb{Z}_+}}\right)\right]$ for all $x\in\mathbb{R}_+$. Note that h is harmonic on $\mathbb{R}_+\setminus\mathbb{Z}_+$. Finally, let us define $\hat v(x) \,:\!=\, \sup_{\tau \in \mathcal{T}_0} \mathbb{E}\left[ h(X^x_{\tau \wedge \tau_0}) \right]$ for all $x\in\mathbb{R}_+$ and the associated stopping set $S\,:\!=\, \{x\geq 0,\, \hat v(x)=h(x) \}$. Observe that $0 \in S$. Using the strong Markov property, [Reference Egloff and Leippold8, Theorem 3.3] proves both $v=\hat v$ and that the entrance time in S is the smallest optimal time for $\hat v$, because h is bounded. The next lemma is key to showing our result.

Proof. According to optimal stopping theory (see [Reference Peskir and Shiryaev21, Theorem 2.4, p. 35]), the value function $\hat v$ is sub-harmonic on $(0,\infty)$ and harmonic on $(0,\infty)\setminus S$.

Let $x \in (0,\infty)\setminus S$ and define $a\,:\!=\, \sup (S\cap[0,x))$ (this supremum is attained, because S is closed and $0\in S$) and $b\,:\!=\,\inf(S\cap(x,+\infty))\leq +\infty$.

Thus, on one hand, $\hat v$ is linear on (a,b). Denote by $\hat p$ the slope of $\hat v$ on (a,b). On the other hand, h is linear both on $(\lfloor a\rfloor,\lfloor a\rfloor+1)$ with slope $p_a$ and on $(\lfloor b\rfloor,\lfloor b\rfloor+1)$ with slope $p_b$.

Assume that $a \notin {\mathbb{Z}_+}$. First, we will show that either a is the unique point of $(\lfloor a\rfloor,b)$ in S or all the interval $[\lfloor a\rfloor,a]$ lies in S. Assume there exists some $ \lfloor a\rfloor \le c <a$ (which is possible because $a \notin {\mathbb{Z}_+}$) that belongs to S. Both functions $\hat v$ and h are linear and coincide on c and a, therefore they are equal everywhere on the interval [c,a] and thus $[\lfloor a\rfloor,a] \subset S$. In that case, because $\hat v(y) > h(y)$ for $y\in(a,b)$ and $\hat v(y)=h(y)$ for $\lfloor a\rfloor \le y \le a$, we have $p_a < \hat p $ which contradicts the sub-harmonicity of $\hat v$.

On the other hand, if a is the unique point of $(\lfloor a\rfloor,b)$ in S, $\hat v$ is linear on both sides of a with slopes $p^-$ for $y < a$ and $\hat p$ for $y > a$. Since h is below or equal to $\hat v$, we must have $p^- \leq p_a \leq \hat p$, yielding the same contradiction of sub-harmonicity, if $p^-<\hat p$. If, on the contrary, $p^-=\hat p$, then h and $\hat v$ coincide on $[\lfloor a\rfloor,a ]$, in contradiction with the assumption that $\{a\}=(\lfloor a\rfloor,b)\cap S$. Therefore, a must be in ${\mathbb{Z}_+}$. By symmetry, the same reasoning applies to prove that $b \in {\mathbb{Z}_+}$.

For $n \in {\mathbb{Z}_+}$, let us define the following optimal stopping problem on the birth–death process Y:

(5.5) \begin{equation} u(n)\,:\!=\,\sup_{\sigma \in \mathcal{T}_0^Y}\mathbb{E}\left[ \phi\left(Y^n_{\sigma\wedge\sigma_0}\right) \right] ,\end{equation}

where $\mathcal{T}_0^Y$ is the set of all $\mathcal{F}^Y$ stopping times and $\sigma_0=\inf\{ t \ge 0 : Y_t=0\}$.

Proof. By definition, $v(0)=u(0)=\phi(0)$; thus, we assume $n \ge 1$ from now. First, we consider the case where $S=\mathbb{R}_+$, which is equivalent to assuming that h is concave with $h(0)=0$. By Jensen’s inequality, for every $\sigma \in \mathcal{T}_0^Y$, $E\left[ \phi\left(Y^n_{\sigma\wedge\sigma_0}\right) \right]=E\left[ h\left(Y^n_{\sigma\wedge\sigma_0}\right) \right] \le h(n)$, which yields $u(n) \le h(n)$. On the other hand, $u(n) \ge \phi(n)=h(n)$ by definition. From now on we assume that $S \neq \mathbb{R}_+$. According to Lemma 5.1, the stopping time $\hat T=\inf\{ t \ge 0 : X_{t} \in S \} \in \mathcal{T}_{\mathbb{Z}_+}$. Note that $\hat T \le \tau_0$, because $0 \in S$ and it is optimal for $v=\hat v$. Moreover, proceeding analogously to the proof of Proposition 5.1, the stopping time $\hat \sigma=L_{\hat T}=\inf\{ t \ge 0 : Y_{t} \in S\} \in \mathcal{T}_0^Y$ and is lower than $\sigma_0$. Therefore, $v(n) = \mathbb{E}\left[\phi\left(X^n_{\hat T}\right) \right] = \mathbb{E}\left[\phi\left(Y^n_{\hat \sigma}\right)\right] \le u(n)$. To prove the converse inequality, let us define $\mathcal{T}_0^Y(M)$ as the set of all Markov stopping times of type $\inf\{t \ge 0 : Y_t \in A \}$ for A a subset of ${\mathbb{Z}_+}$. Optimal stopping theory tells us the smallest optimal time associated with problem (5.5) belongs to $\mathcal{T}_0^Y(M)$. Moreover, if $\sigma \in \mathcal{T}_0^Y(M)$ then $A_\sigma \in \mathcal{T}_{\mathbb{Z}_+}$ and thus $u(n) = \sup_{\sigma \in \mathcal{T}_0^Y(M)}\mathbb{E}\left( \phi(Y^n_\sigma) \right) = \sup_{\sigma \in \mathcal{T}_0^Y(M)}\mathbb{E}\left( \phi(X^n_{A_\sigma}) \right) \le v(n)$, which completes the proof.

We end this section with a numerical illustration. Let us consider the payoff $\phi$ defined on $\mathbb{R}_+$ by $\phi(x)=(\min(x,100)-a)_+$ where $a<100$. Figure 2 illustrates the monotone algorithm by showing the evolution of $\mathcal{D}_n$ for four different values of the parameter a.

Figure 2. (a) The parameter is $a=10$, the sequence $D_n$ converges to the stopping region (in red) after 90 iterations. (b) The parameter is $a=20$, the sequence $D_n$ converges to the stopping region (in red) after 80 iterations. (c) The parameter is $a=50$, the sequence $D_n$ converges to the stopping region (in red) after 50 iterations. (d) The parameter is $a=90$, the sequence $D_n$ converges to the stopping region (in red) after 90 iterations.