# Delayed Switching Identities and Multi-Marginal Solutions to the Skorokhod
Embedding Problem

Alexander M. G. Cox  Department of Mathematical Sciences, University of Bath
<EMAIL_ADDRESS>and  Annemarie M. Grass  Faculty of Mathematics,
University of Vienna<EMAIL_ADDRESS>
(Date: .)

###### Abstract.

In this article, we consider a generalisation of the Skorokhod embedding
problem (SEP) with a _delayed_ starting time. In the delayed SEP, we look for
stopping times which embed a given measure in a stochastic process, which
occur after a given delay time. Our first contribution is to show that the
switching identities introduced in a recent paper of Backhoff, Cox, Grass and
Huesmann extend to the case with a delay.

We then show that the delayed switching identities can be used to establish an
optimal stopping representation of Root and Rost solutions to the multi-
marginal Skorokhod embedding problem. We achieve this by rephrasing the multi-
period problem into a one-period framework with delay. This not only recovers
the known multi-marginal representation of Root, but also establishes a
previously unknown optimal stopping representation associated to the multi-
marginal Rost solution. The Rost case is more complex than the Root case since
it naturally requires randomisation for general initial measures, and we
develop the necessary tools to develop these solutions. Our work also provides
a comprehensive and complete treatment of _discrete_ Root and Rost solutions,
embedding discrete measures into simple symmetric random walks.

Key words. Skorokhod embedding problem; Root barrier; Rost barrier; optimal
stopping; switching identities.

MSC 2020. Primary 60G40, 60J65, 90C41; secondary 91G20

Funding: A. Grass gratefully acknowledges financial support through FWF
project P 35197 (Grant DOI: 10.55776/P35197)

##  1\. Introduction

We consider the _Skorokhod embedding problem_ , that is given a Brownian
motion $(W_{t})_{t\geq 0}$ started according to an initial distribution
$W_{0}\sim\lambda$, and a probability distribution $\mu$ on $\mathbb{R}$, the
question is to find a stopping time $\tau$ such that

$W_{\tau}\sim\mu\text{ and }(W_{t\wedge\tau})_{t\geq 0}\text{ is uniformly
integrable.}$ (SEP)

While this problem was originally posed and solved by Skorokhod [38, 37] in
the early 60s, it remains an active field of research to the present day. The
2004 survey paper [32] features more than 20 distinct solution to (SEP) and
more recent contributions include [12, 16, 15, 19, 20, 25, 31, 4, 6, 23, 14,
2, 22, 3, 21, 8, 13] among others.

Of primary interest in this article will be an extension of the classical
(SEP) to _multiple marginals_. Given a sequence of measures
$\mu_{1},\dots,\mu_{n}$ on the real line, the _multi-marginal Skorokhod
embedding problem_ is to find an increasing sequence of stopping times
$\tau_{1}\leq\dots\leq\tau_{n}$ such that

$W_{\tau_{k}}\sim\mu_{k},\,k=1,\dots,n\text{ and }(W_{t\wedge\tau_{n}})_{t\geq
0}\text{ is uniformly integrable}.$ (MMSEP)

It is an application of Strassen’s Theorem [39] and a well know fact that
(MMSEP) will admit a solution if and only if the measures are in increasing
convex order, that is $\lambda\leq_{c}\mu_{1}\leq_{c}\cdots\leq_{c}\mu_{n}$.
Throughout the paper we will assume this condition satisfied.

This extension to (MMSEP) is particularly motivated by applications in robust
mathematical finance given the connections between the (SEP) and robust option
pricing first proposed in Hobson’s paper [26]; see also [27] for an extensive
survey. These connections enable the computation of robust bounds on option
prices while considering a market-given marginal distribution at the time of
expiration. Extending this theory to multiple marginals would allow the
incorporation of additional market data into the robust pricing problem. We
develop this approach in a companion paper, [11].

The focal point of this paper are two fundamental and influential solutions to
(SEP) known as Root [34] and Rost [36] barrier solutions. These stopping times
can be represented as hitting times of subsets
$R\subseteq\mathbb{R}_{+}\times\mathbb{R}$, which are subject to some type of
_barrier structure_ , precisely:

$\displaystyle\begin{split}&\,\begin{picture}(-1.0,1.0)(-1.0,-3.0)\circle*{2.0}\end{picture}\
\text{ If }(t,x)\in R^{Root}\text{ then }(s,x)\in R^{Root}\text{ for all
}s>t.\\\ &\,\begin{picture}(-1.0,1.0)(-1.0,-3.0)\circle*{2.0}\end{picture}\
\text{ If }(t,x)\in R^{Rost}\text{ then }(s,x)\in R^{Rost}\text{ for all
}s<t.\end{split}$ (1.1)

See Figure 1 for an illustration.

(a) Root (left) and Rost (right) barriers solving (SEP) for
$\lambda=\delta_{0}$ and $\mu=\mathsf{U}[-2,2]$.

(b) Root (left) and Rost (right) barriers solving (MMSEP) for
$\lambda=\delta_{0}$, $\mu_{1}=\frac{1}{2}(\delta_{-1}+\delta_{1})$ and
$\mu_{2}=\mathsf{U}[-2,2]$.

Figure 1. Single-marginal (a) and multi-marginal (b) Root and Rost solutions
embedding the measure $\mathsf{U}[-2,2]$, one of the examples specifically
mentioned [34] for its previously unknown barrier structure.

Our interest in Root and Rost solutions is twofold. First, there is a
substantial interest in the probability literature on these solutions, see for
example [29, 36, 16, 15, 19, 20, 7, 18, 14, 21, 33, 2, 9]. Second, such
solutions are related to robust bounds on variance options considering
multiple market-given marginal distributions. In [11] we carry out an
empirical exploration of such robust bounds based on the results presented
here. See [30, 10, 16, 15, 28] for related work in the financial context.

While existence results of Root and Rost barriers were shown by their
originators and also an extension to multiple marginals was given in [6], as
was noted in Root’s original work [34], concrete barriers are only known in
the most trivial of situations. To actually construct a concrete barrier $R$
given a probability measure $\mu$ or even more so a sequence barriers given a
sequence of probability measures $\mu_{1},\dots,\mu_{n}$ is a highly non
trivial task.

Prior research in [16, 15, 19, 20, 18, 21] established that Root and Rost
barriers which solve the (single-marginal) (SEP) can be recovered via
solutions to a respective associated PDE in variational form. Solutions to
such PDEs, in turn, are known to have a representation by means of an optimal
stopping problem. While for a long time this optimal stopping representation
of Root and Rost solutions was exclusively accessible through this detour over
PDEs in variational form, a direct proof utilizing time-reversal arguments was
given in [14], notably for the multi-marginal Root case. It was furthermore
the aim of the article [1] to give a simple probabilistic argument connecting
Root and Rost solutions to their respective optimal stopping representations
in the single marginal case by establishing a specific switching identity. To
the best of our knowledge, an optimal stopping representation associated to
the multi-marginal Rost problem remained unknown to this day.

In order to establish such a multi-marginal representation, a crucial first
step is to reduce the multi-step viewpoint to a single-marginal perspective
where the initial marginal is now a space-time law instead of a spatial law at
zero. This approach builds on an approach implicit in [14], and which we make
explicit in our approach. Our solution is computed in terms of a _delay_
stopping time inducing an initial space-time law after which we embed with a
Root or Rost barrier respectively. Given such a representation it becomes
apparent how a multi-marginal solution can be recovered inductively.

An initial step in our process is to extend the results established in [6] as
well as [1] to allow for such a delay. The implications of this extension are
twofold: First, it enables a more concise and intuitive recovery of the multi-
marginal optimal stopping problem given in [14]. Second, we can provide a
novel characterisation of the multi-marginal Rost embedding in terms of the
solution to a given optimal stopping (or multiple stopping) problem. This lays
the foundation for constructing Rost barriers such that their hitting times
solve the (MMSEP) computable as demonstrated in Figure 1.

We briefly review the known results for the single marginal problem and then
proceed to state its multi-marginal extension.

#### Summary of Single Marginal Results

Simple probabilistic arguments justifying the optimal stopping
characterization of the single marginal Root and Rost (SEP) were given in [1].
Let us denote by $\mu^{Root}$ (resp. $\mu^{Rost}$) the law of the Brownian
motion started with distribution $\lambda$ at the time it hits $R^{Root}$
(resp. $R^{Rost}$). By $\mu_{T}^{Root}$ (resp. $\mu_{T}^{Rost}$) we denote the
time this Brownian motion hits the barrier
$R^{Root}\cup\left([T,\infty)\times\mathbb{R}\right)$ (resp.
$R^{Rost}\cup\left([T,\infty)\times\mathbb{R}\right)$). Recall the potential
of a measure $m$, denoted by

$U_{m}(y):=-\int|y-x|\,m(\mathrm{d}x).$

The single-marginal relations of interest, as provided in [16, 15, 1, 21]
among others are

$\displaystyle U_{\mu_{T}^{Root}}(y)$
$\displaystyle=\mathbb{E}_{y}\left[U_{\mu^{Root}}\left(W_{\tau^{*}}\right)\mathbbm{1}_{\tau^{*}<T}+U_{\lambda}\left(W_{\tau^{*}}\right)\mathbbm{1}_{\tau^{*}=T}\right]$
(1.2) $\displaystyle=\sup\limits_{\tau\leq
T}\mathbb{E}_{y}\left[U_{\mu^{Root}}(W_{\tau})\mathbbm{1}_{\tau<T}+U_{\lambda}(W_{\tau})\mathbbm{1}_{\tau=T}\right],$
(1.3)

where the optimizer is $\tau^{*}:=\inf\left\\{t\geq 0:(T-t,W_{t})\in
R^{Root}\right\\}\wedge T$,
and

$\displaystyle U_{\mu^{Rost}}(y)-U_{\mu_{T}^{Rost}}(y)$
$\displaystyle=\mathbb{E}_{y}\left[\left(U_{\mu^{Rost}}-U_{\lambda}\right)(W_{\tau^{*}})\right]$
(1.4) $\displaystyle=\sup\limits_{\tau\leq
T}\mathbb{E}_{y}\left[\left(U_{\mu^{Rost}}-U_{\lambda}\right)(W_{\tau})\right],$
(1.5)

where the optimizer is $\tau^{*}:=\inf\left\\{t\geq 0:(T-t,W_{t})\in
R^{Rost}\right\\}\wedge T$.

#### Multi-Marginal Extensions

We are interested in Equations (1.2) - (1.5) in a multi marginal setting.
While the multi marginal extension of the Root case (1.2) - (1.3) is known due
to [14], the Rost equivalent appears to be novel. The results can be stated as
follows.

Let $R_{1},R_{2},\dots,R_{n}$ denote a sequence of Root (resp. Rost) barriers
as defined in (LABEL:def:BarrierSet). Then consider the associated Root (resp.
Rost) stopping times

$\displaystyle\rho_{1}$ $\displaystyle:=\inf\left\\{t\geq 0:(t,W_{t})\in
R_{1}\right\\},$ $\displaystyle\rho_{k}$
$\displaystyle:=\inf\left\\{t\geq\rho_{k-1}:(t,W_{t})\in R_{k}\right\\},\text{
for }k\in\\{2,\dots,n\\}.$

Define the respective laws $\mu_{i}:=\mathcal{L}^{\lambda}(W_{\rho_{i}})$ and
$\mu_{i,T}:=\mathcal{L}^{\lambda}(W_{\rho_{i}\wedge T})$. More precisely,
$\mu_{i}$ will be the law of the Brownian motion starting with distribution
$\lambda$ at the time it consecutively hit all of the barrier sets
$R_{1},\dots,R_{i}$ respectively, and $\mu_{i,T}$ will be the time it
consecutively hit the barrier sets
$R_{1}\cup\left([T,\infty)\times\mathbb{R}\right),\dots,R_{i}\cup\left([T,\infty)\times\mathbb{R}\right)$.
Then these measures are in convex order, i.e.
$\mu_{1}\leq_{c}\mu_{2}\leq_{c}\cdots\leq_{c}\mu_{n}$ as well as
$\mu_{1,T}\leq_{c}\mu_{2,T}\leq_{c}\cdots\leq_{c}\mu_{n,T}$. Moreover define
the function,

$U_{\mu_{0,T}}(x):=U_{\mu_{0}}(x):=U_{\lambda}(x)\quad\text{ for all }T\geq
0.$ (1.6)

The multi-marginal extension of our relations of interest are given as
follows.

######  Theorem 1.1.

If $(R_{k})$ denotes a sequence of Root barriers, then

$\displaystyle U_{\mu_{k,T}}(y)$
$\displaystyle=\mathbb{E}_{y}\left[U_{\mu_{k-1,T-\tau^{*}_{k}}}(W_{\tau^{*}_{k}})+(U_{\mu_{k}}-U_{\mu_{k-1}})(W_{\tau^{*}_{k}})\text{$11$}_{\\{\tau^{*}_{k}<T\\}}\right]$
(1.7) $\displaystyle=\sup_{\tau\leq
T}\mathbb{E}_{y}\left[U_{\mu_{k-1,T-\tau}}(W_{\tau})+(U_{\mu_{k}}-U_{\mu_{k-1}})(W_{\tau})\text{$11$}_{\\{\tau<T\\}}\right],$
(1.8)

where the optimizer is $\tau^{*}_{k}:=\inf\left\\{t\geq 0:(T-t,W_{t})\in
R_{k}\right\\}\wedge T$.

Moreover, given the interpolating potentials $U_{\mu_{k,T}}(y)$ for all
$(T,y)\in[0,\infty)\times\mathbb{R}$ we can recover the Root barriers
$R_{1},\dots,R_{n}$ embedding the measures $\mu_{1},\dots,\mu_{n}$ in the
following way

$R_{k}=\left\\{(T,y):\left(U_{\mu_{k,T}}-U_{\mu_{k-1,T}}\right)(y)=\left(U_{\mu_{k}}-U_{\mu_{k-1}}\right)(y)\right\\},\,\,k\in\\{1,\dots,n\\}.$

######  Theorem 1.2.

If $(\bar{R}_{k})$ denotes a sequence of Rost barriers, then

$\displaystyle U_{\mu_{k}}(y)-U_{\mu_{k,T}}(y)$
$\displaystyle=\mathbb{E}_{y}\left[U_{\mu_{k}}(W_{\tau^{*}_{k}})-U_{\mu_{k-1,T-\tau^{*}_{k}}}(W_{\tau^{*}_{k}})\right]$
(1.9) $\displaystyle=\sup_{\tau\leq
T}\mathbb{E}_{y}\left[U_{\mu_{k}}(W_{\tau})-U_{\mu_{k-1,T-\tau}}(W_{\tau})\right]$
(1.10)

where the optimizer is $\tau^{*}_{k}:=\inf\left\\{t\geq
0:(T-t,W_{t})\in\bar{R}_{k}\right\\}\wedge T$.

Moreover, given the interpolating potentials $U_{\mu_{k,T}}(y)$ for all
$(T,y)\in[0,\infty)\times\mathbb{R}$ we can recover the Rost barriers
$\bar{R}_{1},\dots,\bar{R}_{n}$ embedding the measures $\mu_{1},\dots,\mu_{n}$
in the following way

$\bar{R}_{k}=\left\\{(T,y):U_{\mu_{k,T}}(y)=U_{\mu_{k-1,T}}(y)\right\\},\,\,k\in\\{1,\dots,n\\}.$

#### Outline of the Paper

In Section 2 we introduce the notion of _delayed_ Skorokhod embeddings, which
contain the multi-marginal Skorokhod embedding as a special case. We will
establish a general existence of such solution following the approach in [6]
and present an optimal stopping representation theorem.

Inspired by the framework proposed in [1], we first provide a analogous
statements for simple symmetric random walks in Section 3. First we show
general existence of delayed Root and Rost solution in this context,
subsequently we state and prove the corresponding respective optimal stopping
representation.

Section 4 is dedicated to providing a suitable discretization of the
continuous-time framework and of the respective optimal stopping
representations such that the results of Section 3 apply. We then take a
Donsker-type limit back to a Brownian motion, recovering the continuous times
results stated in Section 2.

##  2\. Delayed Root and Rost Embeddings

For a more convenient and comprehensive treatment of (MMSEP), but also present
results in greater generality we introduce a relatively recent extension of
the classical (SEP) known as _delayed_ embeddings. Although the concept of
delayed embeddings has been implicitly explored in [14], to best of our
knowledge the specific name was first mentioned in [9].

We consider a _delay stopping time_ $\eta$ and require our solution to (SEP)
to wait for this delay before embedding the measure $\mu$.

Formally, given a measure $\mu$, a Brownian motion $(W_{t})_{t\geq 0)}$
started according to an initial distribution $W_{0}\sim\lambda$ and a
(possibly randomized) delay stopping time $\eta$ the _delayed Skorokhod
embedding problem_ is to find a stopping time $\tau$ such that

$W_{\tau}\sim\mu\text{ where }\tau\geq\eta\text{ and }(W_{\tau\wedge
t})_{t\geq 0}\text{ is uniformly integrable.}$ (dSEP)

We will denote a (dSEP) by the triple $(\lambda,\eta,\mu)$ and assume
throughout the paper that $\eta$ is an integrable stopping time and that $\mu$
dominates $\mathcal{L}^{\lambda}(W_{\eta})$ in the convex order. Trivially,
the (dSEP) has no solution if either of these conditions are violated.

###  2.1. Root and Rost solutions to (dSEP)

We are interested in Root and Rost solutions to (dSEP), that is solutions of
the form

$\rho:=\inf\left\\{t\geq\eta:(t,W_{t})\in R\right\\}$

where $R$ is a Root or Rost barrier as defined in (LABEL:def:BarrierSet).

In [5] the necessary theory and tools were given to identify specific
solutions to (SEP) as stopping times that are optimisers over appropriate
additional optimisation criteria. Such (SEP) with additional optimisation
criteria are denoted by (OptSEP). In [6] this concept was extended to multiple
marginals and denoted by (OptMSEP). Especially multi-marginal Root and Rost
solutions were recovered as solutions to appropriate (OptMSEP).

We can further ask whether we can recover the delayed Root and Rost embeddings
as optimisers over an appropriate optimisation criteria. The answer to this is
positive, and is a relatively simple application of the results of [6]. We
work in the class of _randomised multi-stopping times_ introduced in [6],
$\mathrm{RMST}{}^{1}_{2}$, which we understand to be probability measures on
the space $\mathbb{R}\times C_{0}(\mathbb{R}_{+})\times\Xi^{2}$, where
$\Xi^{2}=\\{(s_{1},s_{2})\in\mathbb{R}^{2}_{+},s_{1}\leq s_{2}\\}$, and where
the measure projected on its first two coordinates is equal to the measure
$\lambda\times\mathbb{W}$, with $\mathbb{W}$ the Brownian path measure on
$C_{0}(\mathbb{R}_{+})$. The $\Xi^{2}$ variables represent the first and
second stopping times respectively. The measure has further constraints on its
structure (see [6], Definition 3.9), which ensure that the stopping time
properties are respected.

We are interested in optimising a functional of the form
$\mathbb{E}[F(W_{\tau_{2}},\tau_{2})]$ over the class of randomised stopping
times $(\tau_{1},\tau_{2})$ which satisfy the embedding constraint,
$W_{\tau_{2}}\sim\mu$, and for which $\tau_{1}=\eta$ is the given (randomised)
delay stopping time embedding $\alpha_{X}=\mathcal{L}^{\lambda}(W_{\eta})$.

Note that $\eta$ can be understood in the sense of randomised multi-stopping
times, see Lemma 3.11 of [6].

Moreover, we argue that for the specific form of $F(x,t)=h(t)$ for a
convex/concave function $h$, then the stopping time recovered as the optimiser
is exactly the delayed Root/Rost stopping time. We can do this using a slight
modification of the arguments in [6].

We proceed as follows:

Let $\mathrm{RMST}{}^{1}_{2}(\eta,\mu)$ denote the subset of
$\mathrm{RMST}{}^{1}_{2}$ such that the projection onto $\mathbb{R}\times
C_{0}(\mathbb{R}_{+})\times\Xi$ is exactly $\eta$. Then:

  1. (1)

$\mathrm{RMST}^{1}_{2}(\eta,\mu)\subseteq\mathrm{RMST}(\lambda,\alpha_{X},\mu)$
as defined as in [6, Definition 3.18] which is a compact set (Proposition
3.19);

  2. (2)

$\mathrm{RMST}^{1}_{2}(\eta,\mu)$ is closed, as the projection map is
continuous, hence it is also compact;

  3. (3)

The proof of a suitably modified version of Theorem 5.2 now goes through
essentially verbatim to give the following theorem.

######  Theorem 2.1.

Assume that $\gamma:S^{\otimes 2}\to\mathbb{R}$ is Borel measurable. Assume
that (OptMSEP) is well posed and that $\xi\in\mathrm{RMST}^{1}_{2}(\eta,\mu)$
is an optimizer. Then there exists a $(\gamma,\xi)$-monotone Borel set
$\Gamma$ such that $r_{1}(\xi)(\Gamma)=1$.

Here, $\Gamma$ being $(\gamma,\xi)$-monotone is as defined in [6, Definition
5.1] , without the constraint on the projections of the respective sets. The
final conclusion of the Theorem can be applied as in [6, Theorem 2.7], [6,
Theorem 2.10] (or more transparently, the corresponding results in [6]) to
recover the Root/Rost forms of the optimisers.

While Root barrier solutions will always be adapted to the filtration
generated by the underlying Brownian motion, it is a well known fact that Rost
barrier solutions will require some form of external randomization in the case
where the initial and the terminal distribution share some mass. The story is
similar for delayed Root and Rost embeddings and will be summed up in the
following two theorems.

######  Theorem 2.2.

Consider a (dSEP) given by $(\lambda,\eta,\mu)$. Then there exists a Root
barrier $R$ such that the stopping time $\rho\geq\eta$ defined via

$\rho=\inf\left\\{t\geq\eta:(t,W_{t})\in R\right\\}$

embeds the measure $\mu$.

The proof of this theorem follow analogously to the proof of [6, Theorem 2.7],
or similarly of [5, Theorem 2.1] heeding the modifications given above.
Moreover, it is an easy application of the standard Loynes argument [29] to
see that such a Root stopping time $\rho$ must be unique in the sense that for
any other Root stopping time $\tilde{\rho}$ solving the (dSEP) we would have
$\mathbb{P}^{\lambda}\left[\rho=\tilde{\rho}\right]=1$. More details on how to
generalize the Loynes uniqueness argument can be found in [24, Section 4].

We proceed to Rost solutions. In order to give better insights on what will
happen in the case of delayed Rost embeddings, we quickly review the case of
an undelayed (SEP) determined by the initial measure $\lambda$ and terminal
measure $\mu$. It is well known that all mass shared between the two measures
$\lambda$ and $\mu$ must be stopped immediately in the following way. Let
$\bar{\rho}$ be a Rost stopping time solving (SEP), then
$\mathbb{P}^{\lambda}\left[\bar{\rho}=0,W_{0}\in
A\right]=(\lambda\wedge\mu)(A)$ where the infimum of measures is defined as

$(\lambda\wedge\mu)(A):=\inf_{\scaleto{B\subseteq A,\,B\text{
measurable}}{4pt}}\big{(}\lambda(B)+\mu(A\setminus B)\big{)}.$

On the set $\\{\bar{\rho}>0\\}$ the stopping time $\bar{\rho}$ will be the
first hitting time of a Rost barrier $\bar{R}$.

On a set where $(\lambda\wedge\mu)(A)<\lambda(A)$ we will have to randomise
our initial stopping rule in $A$ in order stop only sufficiently much mass. If
$(\lambda\wedge\mu)(A)<\mu(A)$ then at least in some points in $A$ we need to
stop all mass and in fact we will need to extend the Rost barrier beyond 0 at
those points to stop more mass later on. But in this case, all mass will stop
immediately in those points _independent_ of the choice of randomisation rule,
as a consequence of the recurrence of Brownian motion. Thus any randomisation
rule will give the same stopping rule although an obvious “maximal” rule is to
stop all paths starting in $A$ due to the randomisation. If
$(\lambda\wedge\mu)(A)=\mu(A)=\lambda(A)$, the randomisation rule that stops
all mass is the only viable stopping rule since there will be no further
barrier in $A$ beyond time 0.

In the delayed framework something similar needs to happen while it is
apparent that things are complicated by the fact that not all mass will be
released at time 0 at once, but rather over time, according to the measure
$\mathcal{L}^{\lambda}(\eta)$. It is, however, clear that such external
randomization in only feasible in the _atoms_ of the measure
$\mathcal{L}^{\lambda}(\eta)$, of which there can only be countably many
$\\{t_{0},t_{1},\dots\\}$. A _delayed, randomized_ Rost solution will
therefore consist of both a Rost barrier $\bar{R}$ and some description of
this randomization in the atoms of the delay stopping time. Hence, we choose
to represent such a solution as follows.

######  Definition 2.3.

A delay stopping time $\eta$ which distribution has atoms in
$\\{t_{0},t_{1},\dots\\}$, a Rost barrier $\bar{R}$ and a family of
probability densities $\\{\varphi_{0},\varphi_{1},\dots\\}$ determine a
_delayed, randomized_ Rost stopping time $\bar{\rho}^{\varphi}$ in the
following way.

$\bar{\rho}^{\varphi}:=\inf\left\\{t\geq\eta:(t,W_{t})\in\bar{R}\right\\}\wedge
Z$

where

$Z=\min_{k\in\mathbb{N}}Z_{k}\,\,\text{ for
}\,\,Z_{k}:=\begin{cases}t_{k}&\text{ with probability
}\,\mathbb{P}^{\lambda}\left[Z_{k}=t_{k}\big{|}W_{\eta},\eta=t_{k}\right]=\varphi_{k}\left(W_{\eta}\right)\\\
\infty&\text{ otherwise. }\end{cases}$

Let

$\alpha:=\mathcal{L}^{\lambda}((\eta,W_{\eta}))\in\mathcal{P}([0,\infty)\times\mathbb{R})$

denote the space-time distribution induced by the delay stopping time $\eta$.
Then we abbreviate by

$\alpha_{t}:=\alpha\left(\\{t\\}\times\cdot\right)$

its spatial marginal at time $t$.

A crucial fact to note about Rost solutions is that at any time point $t\geq
0$ we are able to tell exactly how much mass was already embedded in a given
measurable set $A\subseteq\mathbb{R}$ but more importantly we are furthermore
able to decide that no more mass will be embedded in this set going forward in
time. These properties allow us to define Rost solutions in an iterative
fashion and for this purpose, given a Rost solution $\bar{\rho}$ we define the
following quantity

$\nu_{t}:=\mu-\mathbb{P}^{\lambda}\left[W_{\bar{\rho}}\in\cdot,\bar{\rho}<t\right],$

the ‘mass not embedded before time $t$’

Let $t_{k}$ denote an atom of the measure $\mathcal{L}^{\lambda}(\eta)$, then
note that the quantity $\alpha_{t_{k}}$ is given while the quantity
$\nu_{t_{k}}$ is fully determined by the Rost barrier _before_ time $t_{k}$,
i.e. $\bar{R}\cap([0,t_{k})\times\mathbb{R})$ and the randomization densities
$\\{\varphi_{l}\\}_{t_{l}<t_{k}}$.

We consider

$\psi_{k}(x):=\frac{\mathrm{d}\left(\alpha_{t_{k}}\wedge\nu_{t_{k}}\right)}{\mathrm{d}\left(\alpha_{t_{k}}\right)}(x),$
(2.1)

the Radon-Nikodym density of $\alpha_{t_{k}}\wedge\nu_{t_{k}}$ with respect to
$\alpha_{t_{k}}$ and state the following theorem.

######  Theorem 2.4.

Consider (dSEP) given by $(\lambda,\eta,\mu)$. Let $\\{t_{0},t_{1},\dots\\}$
denote the set of (at most countably many) atoms of
$\mathcal{L}^{\lambda}(\eta)$. Then there exists a Rost barrier $\bar{R}$ such
that the stopping time $\rho\geq\eta$ defined via

$\rho=\inf\left\\{t\geq\eta:(t,W_{t})\in\bar{R}\right\\}\wedge Z$

where

$Z=\min_{k\in\mathbb{N}}Z_{k}\,\,\text{ for
}\,\,Z_{k}:=\begin{cases}t_{k}&\text{ with probability
}\,\mathbb{P}^{\lambda}\left[Z_{k}=t_{k}\big{|}W_{\eta},\eta=t_{k}\right]=\psi_{k}\left(W_{\eta}\right)\\\
\infty&\text{ otherwise }\end{cases}$

is a solution to (dSEP).

As in the Root case, the existence of a Rost barrier will follow analogously
to the proof of [6, Theorem 2.10] or similarly of [5, Theorem 2.4] heeding the
modifications given above.

Outside of the atoms of the delay distribution, more precisely conditional on
the event $\\{\eta\not\in\\{t_{0},t_{1},\dots\\}\\}$, two Rost stopping times
$\bar{\rho}$ and $\tilde{\rho}$ solving the same (dSEP) are given as hitting
times of two Rost barriers, hence the same Loynes argument as mentioned in the
Root case will provide a.s. equality.

The density of the random variables $Z_{k}$ does not necessarily need to be
unique. There is, however, a sort of maximality about the chosen densities
$\psi_{0},\psi_{1},\dots$ in Theorem 2.4 which will be clarified with the
following lemma.

######  Lemma 2.5.

Consider a (dSEP) given by $(\lambda,\eta,\mu)$. Let $\bar{R}$ be a Rost
barrier and $\\{\varphi_{0},\varphi_{1},\dots\\}$ be a family of densities
such that the delayed, randomized Rost stopping time $\bar{\rho}^{\varphi}$
given as in Definition 2.3 solves the (dSEP). Then for any $k\in\mathbb{N}$ we
can replace $\varphi_{k}$ by $\psi_{k}$ given by (2.1) to obtain the stopping
time $\bar{\rho}^{\psi}$ for which we will have
$\mathbb{P}^{\lambda}\left[\bar{\rho}^{\varphi}=\bar{\rho}^{\psi}\right]=1$.

###### Proof.

Let us consider an arbitrary atom $t_{k}$ of the delay distribution
$\mathcal{L}^{\lambda}(\eta)$. First of all we clarify that in order for
$\varphi_{k}$ to be feasible we must have $\varphi_{k}\leq\psi_{k}$, as for
all measurable sets $A\subseteq\mathbb{R}$ we have

$\mathbb{P}^{\lambda}\left[W_{\bar{\rho}^{\varphi}}\in
A,\bar{\rho}^{\varphi}=t_{k},\eta=t_{k}\right]\leq\begin{cases}\mathbb{P}^{\lambda}\left[W_{t_{k}}\in
A,\eta=t_{k}\right]=\alpha_{t_{k}}(A),\\\
\mathbb{P}^{\lambda}\left[W_{\bar{\rho}^{\varphi}}\in
A,\bar{\rho}^{\varphi}=t_{k}\right]\leq\mathbb{P}^{\lambda}\left[W_{\bar{\rho}^{\varphi}}\in
A,\bar{\rho}^{\varphi}\geq t_{k}\right]=\nu_{t_{k}}(A).\end{cases}$

Denote by
$A_{k}:=\bigcap_{\varepsilon>0}\\{x:(t_{k}+\varepsilon,x)\in\bar{R}\\}$ all
spatial points in the barrier $\bar{R}$ at time $t_{k}$. Then clearly we have

$\mathbb{P}^{\lambda}\left[\bar{\rho}^{\varphi}=t_{k}\big{|}\eta=t_{k},W_{t_{k}}\in
A_{t_{k}}\right]=1=\mathbb{P}^{\lambda}\left[\bar{\rho}^{\psi}=t_{k}\big{|}\eta=t_{k},W_{t_{k}}\in
A_{t_{k}}\right]$

since both stopping times are hitting times of the barrier $\bar{R}$. Hence,
the specific values of $\varphi$ and $\psi$ are irrelevant and we might
replace $\varphi(x)$ with $\psi(x)$ for all $x\in A_{k}$.

Due to the Rost barrier structure, on the set $A_{k}^{c}$, no mass will be
embedded at a later time point,

$\mathbb{P}^{\lambda}\left[W_{\bar{\rho}^{\varphi}}\in
A_{t_{k}}^{c},\bar{\rho}^{\varphi}>t_{k}\right]=0=\mathbb{P}^{\lambda}\left[W_{\bar{\rho}^{\psi}}\in
A_{t_{k}}^{c},\bar{\rho}^{\psi}>t_{k}\right].$ (2.2)

Consider now the set $B_{k}:=\\{x:\varphi_{k}(x)<\psi_{k}(x)\\}\cap
A_{k}^{c}$. Let us assume that $\alpha_{t_{k}}(B_{k})>0$ as otherwise both
$\varphi_{k}(x)$ and $\psi_{k}(x)$ must be 0 for all $x\in B_{k}$ anyway. Our
claim is then proven if we are able to establish
$\int_{B_{k}}\varphi(x)\mathrm{d}x=\int_{B_{k}}\psi(x)\mathrm{d}x$.

It is a consequence of (2.2) that

$\displaystyle\mu(B_{k})=\mathbb{P}^{\lambda}\left[W_{\bar{\rho}^{\varphi}}\in
B_{k},\bar{\rho}^{\varphi}<t_{k}\right]+\mathbb{P}^{\lambda}\left[W_{\bar{\rho}^{\varphi}}\in
B_{k},\bar{\rho}^{\varphi}=t_{k}\right],$

or equivalently that

$\displaystyle\nu_{t_{k}}(B_{k})$
$\displaystyle=\mathbb{P}^{\lambda}\left[W_{\bar{\rho}^{\varphi}}\in
B_{k},\bar{\rho}^{\varphi}=t_{k}\right]$
$\displaystyle=\mathbb{P}^{\lambda}\left[W_{\bar{\rho}^{\varphi}}\in
B_{k},\bar{\rho}^{\varphi}=t_{k},\eta=t_{k}\right].$

Here the second equality follows from the specific structure of Rost
solutions, as all mass that is already released before time $t_{k}$ and
stopped in $B_{k}$ will have done so _before_ time $t_{k}$ almost surely. Then

$\displaystyle\nu_{t_{k}}(B_{k})=\mathbb{P}^{\lambda}\left[W_{\bar{\rho}^{\varphi}}\in
B_{k},\bar{\rho}^{\varphi}=t_{k},\eta=t_{k}\right]$
$\displaystyle=\mathbb{P}^{\lambda}\left[W_{t_{k}}\in
B_{k},\bar{\rho}^{\varphi}=t_{k},\eta=t_{k}\right]$
$\displaystyle=\alpha_{t_{k}}(B_{k})\int_{B_{k}}\varphi(x)\mathrm{d}x$
$\displaystyle\leq\alpha_{t_{k}}(B_{k})\int_{B_{k}}\psi(x)\mathrm{d}x=(\alpha_{t_{k}}\wedge\nu_{t_{k}})(B_{k})$

In particular, this implies that

$(\alpha_{t_{k}}\wedge\nu_{t_{k}})(B_{k})=\nu_{t_{k}}(B_{k}),$

hence we must have
$\int_{B_{k}}\varphi(x)\mathrm{d}x=\int_{B_{k}}\psi(x)\mathrm{d}x$. ∎

Here we observe that if the set of atoms ${t_{0},t_{1},\dots}$ is either
finite or infinite but can be ordered we can assume $t_{0}\leq
t_{1}\leq\cdots$ and construct the densities $\psi_{k}$ consecutively. When
this is not the case, meaning ${t_{0},t_{1},\dots}$ is infinite and cannot be
ordered, while our result will still hold, we cannot expect to derive an
explicit formula for the functions $\psi_{k}$ in this scenario.

An explicit Root solution to (MMSEP) is clear given Theorem 2.2 while an
explicit Rost solution can be recovered from Theorem 2.4 in the following way.

######  Corollary 2.6.

Consider a starting measure $\lambda$ and a sequence of measures
$\mu_{1},\dots,\mu_{n}$ such that
$\lambda\leq_{c}\mu_{1}\leq_{c}\cdots\leq_{c}\mu_{n}$. Then there exists a
sequence or Rost barriers $R_{1},\dots,R_{n}$ such that the stopping times
$\rho_{1}\leq\rho_{2}\leq\cdots\leq\rho_{n}$ defined in the following way are
a solution to (MMSEP).

$\rho_{0}:=0\,\text{ and }\,\rho_{k}:=\inf\left\\{t\geq\rho_{k-1}:(t,W_{t})\in
R_{k}\right\\}\wedge Z_{k}\,\text{ for }\,k\geq 1$

where

$Z_{k}:=\begin{cases}0&\text{ with probability
}\,\mathbb{P}^{\lambda}\left[Z_{k}=0\big{|}W_{0},\rho_{k-1}=0\right]=\frac{\mathrm{d}\left(\mu^{0}_{k-1}\wedge\mu_{k}\right)}{\mathrm{d}\mu^{0}_{k-1}}\left(W_{0}\right)\\\
\infty&\text{ otherwise }\end{cases}$

for
$\mu^{0}_{k}:=\mathbb{P}^{\lambda}\left[\rho_{k-1}=0,W_{0}\in\cdot\right]$.

###### Proof.

Note that for $k=1$ this exact structure of the Rost solution $\rho_{1}$ has
already been established in [35]. Observing that
$\rho_{1}\leq\dots\leq\rho_{n}$ are hitting times of inverse barriers, we can
establish that $\mathcal{L}^{\lambda}(\rho_{1})$ and consequently any
$\mathcal{L}^{\lambda}(\rho_{k})$, $k\geq 2$, do not possess atoms beyond time
$0$.

Inductively recovering the multi-marginal Rost solutions from Theorem 2.4
becomes feasible by considering the single atom $t_{0}=0$. Thus, for $k\geq
2$, set $\eta=\rho_{k-1}$ and $\mu=\mu_{k}$, with $\nu_{0}=\mu_{k}$ and
$\tilde{\alpha}_{0}=\mu^{0}_{k}$. Subsequently, invoking Theorem 2.4, we
establish the existence of a Rost barrier $R:=R_{k}$, ensuring that
$\rho_{k}\geq\rho_{k-1}$ is of the desired structure with $Z_{k}:=Z_{0}$. ∎

###  2.2. Optimal Stopping Representation of (dSE) and (MMSEP)

We will derive the multi marginal Root optimal stopping problem (1.7) - (1.8)
resp. the multi marginal Rost optimal stopping problem (1.9) - (1.10) as a
special case of a _delayed_ Root resp. Rost representation.

For this purpose we consider a starting distribution $\lambda$ for a Brownian
motion and an integrable delay stopping time $\eta$. Recall the space time
distribution induced by the delay

$\alpha:=\mathcal{L}^{\lambda}((\eta,W_{\eta}))\in\mathcal{P}([0,\infty)\times\mathbb{R}).$

We denote the $\mathbb{P}^{\lambda}$-potential of $W_{\eta\wedge T}$ by

$V^{\alpha}_{T}(x)=-\mathbb{E}^{\lambda}\left[\left|W_{\eta\wedge
T}-x\right|\right]$

and the spatial marginal of $\alpha$ by

$\alpha_{X}(A):=\alpha([0,\infty)\times
A)=\mathcal{L}^{\lambda}(W_{\eta})(A)\quad\text{ for
}A\subseteq\mathbb{R}\text{ measurable.}$

Let now $R\subseteq[0,\infty)\times\mathbb{R}$ denote a Root (resp. Rost)
barrier, then we can define the (delayed) Root (resp. Rost) stopping time

$\rho_{\eta}:=\inf\left\\{t\geq\eta:(t,W_{t})\in R\right\\}.$

These stopping times induce the following measures

$\beta^{\alpha}:=\mathcal{L}^{\lambda}\left(W_{\rho^{\eta}}\right)\text{ as
well as }\beta^{\alpha}_{T}:=\mathcal{L}^{\lambda}\left(W_{\rho^{\eta}\wedge
T}\right)\text{ for }T\geq 0$

and the (stopped) potential

$U_{\beta^{\alpha}_{T}}(x)=-\mathbb{E}^{\lambda}\left[\left|W_{\rho^{\eta}\wedge
T}-x\right|\right].$

The extension of the Root optimal stopping problem (1.2)-(1.3) will then be
given in the following theorem.

######  Theorem 2.7.

Let $R$ denote a _Root_ barrier inducing the potentials $U_{\beta^{\alpha}}$
and $U_{\beta^{\alpha}_{T}}$. Then for every
$(T,x)\in[0,\infty)\times\mathbb{R}$ we have the representation

$\displaystyle U_{\beta^{\alpha}_{T}}(x)$
$\displaystyle=\mathbb{E}^{x}\left[V^{\alpha}_{T-\tau^{*}}(W_{\tau^{*}})+(U_{\beta^{\alpha}}-U_{\alpha_{X}})(W_{\tau^{*}})\text{$11$}_{\tau^{*}<T}\right]$
(2.3) $\displaystyle=\sup_{\tau\leq
T}\mathbb{E}_{y}\left[V^{\alpha}_{T-\tau}(W_{\tau})+(U_{\beta^{\alpha}}-U_{\alpha_{X}})(W_{\tau})\text{$11$}_{\tau<T}\right].$
(2.4)

where the optimizer is given by $\tau^{*}:=\inf\\{t\geq 0:(T-t,W_{t})\in
R\\}\wedge T$.

Moreover, given the interpolating potentials $U_{\beta^{\alpha}_{T}}(x)$ for
all $(T,x)\in[0,\infty)\times\mathbb{R}$ we can recover the Root barrier $R$
embedding the measure $\beta^{\alpha}$ in the following way

$R=\left\\{(T,x):\left(U_{\beta^{\alpha}_{T}}-V^{\alpha}_{T}\right)(x)=\left(U_{\beta^{\alpha}}-U_{\alpha_{X}}\right)(x)\right\\}.$

Analogously we can give an optimal stopping representation for delayed Rost
embeddings extending (1.4)-(1.5) in the following way.

######  Theorem 2.8.

If $\bar{R}$ denotes a _Rost_ barrier inducing the potentials
$U_{\beta^{\alpha}}$ and $U_{\beta^{\alpha}_{T}}$. Then for every
$(T,x)\in[0,\infty)\times\mathbb{R}$ we have the representation

$\displaystyle U_{\beta^{\alpha}}(x)-U_{\beta^{\alpha}_{T}}(x)$
$\displaystyle=\mathbb{E}^{x}\left[U_{\beta^{\alpha}}(W_{\sigma_{*}})-V^{\alpha}_{T-\sigma_{*}}(W_{\sigma_{*}})\right]$
(2.5) $\displaystyle=\sup_{\sigma\leq
T}\mathbb{E}^{x}\left[U_{\beta^{\alpha}}(W_{\sigma})-V^{\alpha}_{T-\sigma}(W_{\sigma})\right],$
(2.6)

where the optimizer is given by $\sigma_{*}:=\inf\\{t\geq
0:(T-t,W_{t})\in\bar{D}\\}\wedge T$.

Moreover, given the interpolating potentials $U_{\beta^{\alpha}_{T}}(x)$ for
all $(T,x)\in[0,\infty)\times\mathbb{R}$ we can recover the Rost barrier
$\bar{R}$ embedding the measure $\beta^{\alpha}$ in the following way

$\bar{R}=\left\\{(T,x):U_{\beta^{\alpha}_{T}}(x)=V^{\alpha}_{T}(x)\right\\}.$

First we want to observe that for the choice of $\eta=0$ the single marginal
identities can easily be recovered. Indeed,

  * $\beta^{\alpha}=\mu$ and $\beta^{\alpha}_{T}=\mu_{T}$ as in Section 1

  * $\alpha=\delta_{0}\times\lambda$ thus $\alpha_{X}=\lambda$

  * $V^{\alpha}_{T}(y)=-\mathbb{E}^{\lambda}\left[\left|W_{0}-y\right|\right]=U_{\lambda}(y)$ for any $T\geq 0$

hence

$\displaystyle\mathbb{E}_{y}\left[V^{\alpha}_{T-\tau}(W_{\tau})+(U_{\mu}-U_{\alpha_{X}})(W_{\tau})\text{$11$}_{\tau<T}\right]$
$\displaystyle=\mathbb{E}_{y}\left[U_{\lambda}(W_{\tau})+(U_{\mu}-U_{\lambda})(W_{\tau})\text{$11$}_{\tau<T}\right]$
$\displaystyle=\mathbb{E}_{y}\left[U_{\mu}(W_{\tau})\text{$11$}_{\tau<T}+U_{\lambda}(W_{\tau})\text{$11$}_{\tau=T}\right].$

in the Root case, and

$\mathbb{E}^{x}\left[U_{\beta^{\alpha}}(W_{\sigma})-V^{\alpha}_{T-\sigma}(W_{\sigma})\right]=\mathbb{E}^{x}\left[U_{\mu}(W_{\sigma})-U_{\lambda}(W_{\sigma})\right]$

in the Rost case respectively.

Furthermore, the multi-marginal extensions now follow as an corollary as they
can be deduced inductively from the delayed optimal stopping problem
(2.3)-(2.4) (resp. (2.5)-(2.6)) in the following way.

######  Corollary 2.9.

Let $R_{1},R_{2},\dots,R_{n}$ denote a sequence of Root (resp. Rost) barriers
inducing the potentials $U_{\mu_{1}},\dots,U_{\mu_{n}}$ as well as
$U_{\mu_{1},T},\dots,U_{\mu_{n},T}$. Then the optimal stopping representations
(1.7)-(1.8) (resp. (1.9)-(1.10)) hold.

###### Proof.

For the first marginal induced by $R_{1}$ the optimal stopping representation
is simply the single marginal representation (1.2)-(1.3) (resp. (1.4)-(1.5))
already known resp. recovered above. Let now $k\in\\{2,\dots,n\\}$ and
consider $\eta=\rho_{k}$ and $R=R_{k+1}$. Then

  * $\alpha=\mathcal{L}^{\lambda}(\rho_{k},W_{\rho_{k}})$, thus $\alpha_{X}=\mu_{k}$ and $U_{\alpha_{X}}(y)=U_{\mu_{k}}(y)$,

  * $\beta^{\alpha}=\mu_{k+1}$, thus $U_{\beta^{\alpha}}(y)=U_{\mu_{k+1}}(y)$ and $U_{\beta^{\alpha}_{T}}(y)=U_{\mu_{k+1,T}}(y)$,

  * $V^{\alpha}_{T}(y)=-\mathbb{E}^{\lambda}\left[\left|W_{\rho_{k}\wedge T}-y\right|\right]=U_{\mu_{k,T}}(y)$.

Hence we recover the multi marginal Root (resp. Rost) optimal stopping
problems (1.7)-(1.8) (resp. (1.9)-(1.10)). ∎

##  3\. A Discrete (dSEP) and its Optimal Stopping Representation

We take on the idea of [1] to cast our problem in a discrete setting in order
to use arguments for SSRWs to derive a discrete version of the desired result
and then recover the continuous result through a Donsker type limiting
argument. In this section we define a discrete version of (dSEP). We
furthermore define discrete Root and Rost solutions and give an explicit
construction.

Let $X$ denote a SSRWs on some probability space $(\Omega,\mathbb{P})$,
started at some possibly random initial position. Given $x\in\mathbb{Z}$ we
write $\mathbb{P}^{x}$ for the conditional distribution when $X_{0}=x$. Hence
we can consider a probability measure $\lambda$ on $\mathbb{Z}$ a “starting”
distribution for $X$ by setting
$\mathbb{P}^{\lambda}:=\sum_{x\in\mathbb{Z}}\mathbb{P}^{x}\lambda(\\{x\\})$.

###  3.1. A Discrete (dSEP)

Consider a SSRW $(X_{t})_{t\in\mathbb{N}}$ started in $X_{0}\sim\lambda$.
Given a discrete measure $\mu$ the _discrete Skorokhod embedding problem_ is
to find a (discrete) stopping time $\rho$ such that

$X_{\rho}\sim\mu\text{ and }X_{t\wedge\rho}\text{ is uniformly integrable.}$
(3.1)

Given a delay stopping time $\eta$ the _delayed_ discrete Skorokhod embedding
problem (or _delayed_ (dSEP)) is to find a (discrete) stopping time
$\rho\geq\eta$ such that (3.1) is satisfied.

Just as in the continuous case we are interested in the existence of barrier
type solutions to the discrete (dSEP). These barriers can be defined
analogously to the continuous setting as subsets
$R\subseteq\mathbb{N}\times\mathbb{Z}$ satisfying the following respective
property.

  * $R$ will denote a (discrete) _Root_ barrier if for $(t,x)\in R$ and $s>t$ we also have $(s,x)\in R$.

  * $R$ will denote a (discrete) _Rost_ barrier if for $(t,x)\in R$ and $s<t$ we also have $(s,x)\in R$.

While in the continuous setting it is known that no external randomization is
needed in order to give a Root solution to the (SEP) and external
randomization is needed only in $t=0$ for the Rost solution (and only if the
initial measure $\lambda$ and the terminal measure $\mu$ share mass) this is
no longer the case in the discrete setting. We will see that in order to give
a discrete Root (resp. Rost) solution external randomization will be necessary
in both cases also beyond time $t=0$, however only at the boundary of the
respective barrier.

######  Example 3.1.

Consider the simple example

$\displaystyle\lambda$ $\displaystyle=\delta_{0}$ $\displaystyle\mu$
$\displaystyle=\frac{1}{3}\delta_{-2}+\frac{1}{3}\delta_{0}+\frac{1}{3}\delta_{2}.$

First note that all paths of a SSRW $X$ that reach $\pm 2$ at any point in
time will be absorbed there. As all paths originate from $(0,0)$, the
probability of being in site $x=0$ at time $t=2$ is given by
$\frac{1}{2}>\frac{1}{3}=\mu(\\{0\\})$. Consequently, we cannot stop all paths
in $(2,0)$ as this would embed too much mass in $\\{0\\}$. However, if we
allow all paths to proceed from $(2,0)$, then the probability of being in site
$x=0$ at time $t=4$ without having hit $\pm 2$ before is given by
$\frac{1}{4}<\frac{1}{3}=\mu(\\{0\\})$. In other words, this would result in
an insufficient mass being embedded in ${0}$. Hence, it becomes necessary to
stop _some_ paths in $(2,0)$, but not all of them. Precisely, we will need to
stop $\frac{1}{3}$ of paths in $(2,0)$ while allowing the remainder to reach
either of $\\{-2,0,2\\}$ at time $t=4$ in order to correctly embed the
distribution $\mu$. Refer to Figure 2 for an illustration on possible
realizations of such paths.

Figure 2. Possible realizations of paths hitting a Root barrier that solves
the discrete (SEP) given by $\lambda=\delta_{0}$ and
$\mu=\frac{1}{3}\delta_{-2}+\frac{1}{3}\delta_{0}+\frac{1}{3}\delta_{2}$.

We will formalize this concept of randomized stopping in the following way.

If $\rho$ denotes a stopping time for the process $X$ then we can for each
point $(t,x)\in\mathbb{N}\times\mathbb{Z}$ consider the probability of $\rho$
stopping in site $x$ at time $t$ after $\eta$ by

$r_{t}(x):=\mathbb{P}^{\lambda}\left[\rho=t|\left(\rho\wedge t,X_{\rho\wedge
t}\right)=(t,x),\eta\leq t\right].$ (3.2)

If now $R$ denotes a barrier and $\rho$ its hitting time then in the classic
(deterministic) case we should have $r_{t}(x)\in\\{0,1\\}$ and $r_{t}(x)=1$ if
and only if $(t,x)\in R$, i.e. we stop in the barrier immediately after
arrival. However, if we allow for $r_{t}(x)\in(0,1)$ but agree on the
convention that $(t,x)\in R$ when $r_{t}(x)>0$, then this can be understood as
stopping inside of the barrier only with probability $r_{t}(x)$. We can now
give an equivalent definition of discrete Root (resp. Rost) barriers on the
basis of these stopping probabilities. A field of stopping probabilities
denoted as $(r_{t}(x))_{(t,x)\in\mathbb{N}\times\mathbb{Z}}$ represents a

$\displaystyle\,\begin{picture}(-1.0,1.0)(-1.0,-3.0)\circle*{2.0}\end{picture}\
\,\,\text{Root barrier if for all }(t,x)\in\mathbb{N}\times\mathbb{Z}\text{
such that }r_{t}(x)>0\text{ we have }r_{t+s}(x)=1\,\forall s\geq 1,$ (3.3)
$\displaystyle\,\begin{picture}(-1.0,1.0)(-1.0,-3.0)\circle*{2.0}\end{picture}\
\,\,\text{Rost barrier if for all }(t,x)\in\mathbb{N}\times\mathbb{Z}\text{
such that }r_{t}(x)>0\text{ we have }r_{t-s}(x)=1\,\forall s=1,\dots,t.$ (3.4)

This definition guarantees the respective barrier structure and furthermore
assures that randomization only happens at the boundary points of the
respective barriers. We will also refer to
$(r_{t}(x))_{(t,x)\in\mathbb{N}\times\mathbb{Z}}$ as Root and Rost field of
stopping probabilities, respectively.

Let $u=(u_{0},u_{1},\dots)$ denote a sequence of iid uniform random variable,
i.e. $u_{i}\sim U[0,1]$. Then our Root (resp. Rost) stopping times subject to
external randomization at the endpoints can be represented as follows

$\rho=\rho_{u}=\inf\left\\{t\geq\eta:r_{t}(X_{t})>u_{t}\right\\}.$ (3.5)

We could think of at every time point $t$ flipping a coin with success
probability $r_{t}(X_{t})$. Was the coin flip successful the process stops, if
not it moves onto the next point. Note that if $r_{t}(x)\in\\{0,1\\}$ for all
$(t,x)\in\mathbb{N}\times\mathbb{Z}$, then this definition will coincide with
the usual non-randomized definition

$\rho=\inf\left\\{t\geq\eta:(t,X_{t})\in R\right\\}.$ (3.6)

Our stopping time $\rho$ is now a _randomized_ stopping time taking the two
arguments $\omega$ and $u$, thus
$\rho:\Omega\times[0,1]^{\mathbb{N}}\rightarrow\mathbb{N}$. While this is a
slightly unconventional definition of an external randomization used for its
more intuitive explanation in this context, we can also cast this randomized
stopping time into the more conventional framework of using only a single
variable of external randomization in the following way. For each
$\omega\in\Omega$ we consider the sequence
$(\zeta_{\omega}(t))_{t\in\mathbb{N}}$ of the probability of the process
$X_{\rho\wedge t}(\omega)$ being ‘alive’ at time $t$ given via

$\displaystyle\zeta_{\omega}(0)$
$\displaystyle:=(1-r_{0}(X_{0}(\omega)))\vee\text{$11$}_{\eta(\omega)=0}\quad\text{
and }$ $\displaystyle\zeta_{\omega}(t)$
$\displaystyle:=\zeta_{\omega}(t-1)\cdot(1-r_{t}(X_{t}(\omega)))\vee\text{$11$}_{t<\eta(\omega)}.$

Note that $(\zeta_{\omega}(t))_{t\in\mathbb{N}}$ is a decreasing sequence and
$\xi_{\omega}(\\{0,\dots,t\\}):=1-\zeta_{\omega}(t)$ will define a measure on
$\mathbb{N}$. Given a uniformly distributed random variable $u\sim U[0,1]$
independent of $X$ the (randomized) stopping time

$\tilde{\rho}(\omega,u):=\inf\\{t\geq 0:\xi_{\omega}(\\{0,\dots,t\\})\geq
u\\}$

now gives a more traditional representation of our randomized Root (resp.
Rost) stopping time.

In the following two subsections we will give an explicit construction of the
stopping probabilities $(r_{t}(x))_{(t,x)\in\mathbb{N}\times\mathbb{Z}}$
solving the discrete (dSEP) both in the Root and Rost case. To guarantee
uniform integrability of all solutions constructed we will henceforth always
assume $\mu$ to denote a finite sum of atoms. Let $x_{*}$ and $x^{*}$ denote
the smallest and largest site respectively at which we have an atom. Then in
both the Root and the Rost case our solution should be bounded from above by
the (delayed) hitting time

$H_{x_{*},x^{*}}:=\inf\\{t\geq\eta:X_{t}\in\\{x_{*},x^{*}\\}\\}.$

Since $\eta$ is a stopping time with finite expectation then so is
$H_{x_{*},x^{*}}$, which in turn implies uniform integrability of
$(X_{t\wedge\rho})_{t\geq 0}$.

####  3.1.1. Existence of Discrete Delayed Root Solutions

An explicit Root solution to the discrete (dSEP) can be established with the
help of expected local times. For a SSRW random walk $X$ the local time at
site $x$ up to time $t$ is defined via

$L_{t}^{x}(X)=\\#\\{s:0\leq
s<t,X_{s}=x\\}=\sum_{s=0}^{t-1}\text{$11$}_{X_{s}=x}.$

We note the following discrete version of Tanaka’s Formula for local times.

######  Theorem 3.2.

Consider a random walk $X$ defined by $X_{t}=X_{0}+\sum_{s=1}^{t}\xi_{s}$
where $\xi_{s}$ are iid Rademacher random variables. Then for $x\in\mathbb{Z}$
we can represent the local time $L_{t}^{x}(X)$ of $X$ until time $t$ as

$L_{t}^{x}(X)=|X_{t}-x|-|X_{0}-x|-\sum_{s=0}^{t-1}\operatorname{sgn}(X_{s}-x)\xi_{s+1}.$
(3.7)

We refer to [17] for a proof.

Let

$L_{s,t}^{x}(X)=\\#\\{u:s\leq u<t\text{ and
}X_{u}=x\\}=\sum_{u=s}^{t-1}\text{$11$}_{X_{u}=x}=L_{t}^{x}(X)-L_{s}^{x}(X)$

denote the local time of the process $X$ at site $x$ _between_ time $s$ and
$t$ (for $s\leq t$).

For our delay stopping time $\eta$ write
$\alpha_{X}=\mathcal{L}^{\lambda}(X_{\eta})$. Consider now $X_{0}\sim\lambda$
and let $\rho\geq\eta$ be a stopping time for the random walk $X$ such that
$X_{\rho}\sim\mu$. Then due to (3.7) we have the following representation of
the _expected_ local time between $\eta$ and $\rho$

$\mathbb{E}^{\lambda}\left[L_{\eta,\rho}^{x}(X)\right]=U_{\alpha_{X}}(x)-U_{\mu}(x)=:L(x).$
(3.8)

Conversely, for any solution $\rho\geq\eta$ to (dSEP) Equation (3.8) must be
satisfied.

Let $(r_{t}(x))_{(t,x)\in\mathbb{N}\times\mathbb{Z}}$ denote a field of
stopping probabilities and $\rho$ its corresponding stopping time delayed by
the stopping time $\eta$.

Then we define

$\tilde{\alpha}_{t}(x):=\mathbb{P}^{\lambda}\left[X_{t}=x,\eta\leq t,\rho\geq
t\right],$

the free mass available in site $x$ at time $t$.

Define $\alpha(t,x):=\mathbb{P}^{\lambda}\left[X_{\eta}=x,\eta=t\right]$, then
we can compute $\tilde{\alpha}_{t}$ inductively using only information up to
time $t-1$ in the following way

$\tilde{\alpha}_{t}(x)=\frac{1}{2}\left((1-r_{t-1}(x+1))\tilde{\alpha}_{t-1}(x+1)+(1-r_{t-1}(x-1))\tilde{\alpha}_{t-1}(x-1)\right)+\alpha(t,x).$

Precisely, paths can only end up in $(t,x)$ from the neighboring points
$(t-1,x+1)$ and $(t-1,x+1)$. They will with probability $1-r_{t-1}(x+1)$ resp.
$1-r_{t-1}(x-1)$ leave the respective site and then with probability
$\frac{1}{2}$ end up in $(t,x)$. Moreover, we only consider mass after the
stopping time $\eta$, this is represented by $\alpha(t,x)$, the probability of
particles _appearing_ in site $x$ at time $t$. Note that at time $0$ we thus
only have $\tilde{\alpha}_{0}(x)=\alpha(0,x).$

With the help of the quantities $\tilde{\alpha}_{t}(x)$ the expected number of
visits in site $x$ up until time $t$ of the process $X$ can then be written as

$l_{t}^{x}:=\sum_{s=0}^{t-1}(1-r_{s}(x))\tilde{\alpha}_{s}(x).$ (3.9)

In particular we will have $l_{0}^{x}=0$ for all $x\in\mathbb{Z}$.

We recall $L(x):=U_{\alpha_{X}}(x)-U_{\mu}(x)$ and define

$\tilde{L}_{t}(x):=L(x)-l_{t}^{x},$

the ‘missing local time’ after time $t$. Note that $\tilde{L}_{t}(x)$ (resp.
$l_{t}^{x}$) can be computed only using information up to time $t-1$.

We are now equipped to give a precise construction of a Root solution to the
discrete (dSEP).

######  Theorem 3.3.

Consider a field of stopping probabilities
$(r_{t}(x))_{(t,x)\in\mathbb{N}\times\mathbb{Z}}$ inductively defined via the
formula

$r_{t}(x):=1-\frac{L(x)-l_{t}(x)}{\tilde{\alpha}_{t}(x)}\wedge
1=1-\frac{\left(\tilde{L}_{t}\wedge\tilde{\alpha}_{t}\right)\left(x\right)}{\tilde{\alpha}_{t}(x)}\text{
when }\tilde{\alpha}_{t}(x)>0$

and chosen to comply with (3.3) otherwise.

Then this field represents a Root field of stopping probabilities and the
associated stopping time

$\rho=\inf\left\\{t\geq\eta:r_{t}(X_{t})>u_{t}\right\\}.$

will be a Root solution to the discrete (dSEP).

###### Proof.

Note the following

  * As both $\tilde{L}_{t}$ and $\tilde{\alpha}_{t}$ only use information that is either given or acquired up to time $t-1$, it is clear that $r_{t}$ can be computed inductively to give a stopping time.

  * When $\tilde{\alpha}_{t}(x)=0$ the point $(t,x)$ cannot be reached by the stopped random walk after time $\eta$. The specific value of $r_{t}(x)$ is hence irrelevant for all the respective quantities and can be chosen to comply with the definition of a Root field of stopping probabilities.

  * $r_{t}(x)=1\Leftrightarrow l_{t}^{x}=L(x)$. In other words, we must have already accrued enough local time at site $x$. Moreover we will then have $l_{t+s}^{x}=l_{t}^{x}$ and $r_{t+s}(x)=1$ for all $s\geq 0$, hence the Root structure of our barrier is guaranteed.

  * $r_{t}(x)=0\Leftrightarrow\tilde{L}_{t}(x)=L(x)-l_{t}^{x}\geq\tilde{\alpha}_{t}(x)$. So no mass will be stopped in $(t,x)$ since we still need to accrue more local time and adding all available mass to $l_{t}^{x}$ will make us remain in our local time budget, i.e. $l_{t+1}^{x}=l_{t}^{x}+\tilde{\alpha}_{t}(x)\leq L(x)$.

  * $r_{t}(x)\in(0,1)\Leftrightarrow 0<\frac{L(x)-l_{t}^{x}}{\tilde{\alpha}_{t}(x)}<1$. As letting all mass run would add too much to our expected local time only a fraction should be added and we have $l_{t+1}^{x}=l_{t}^{x}+\frac{L(x)-l_{t}^{x}}{\tilde{\alpha}_{t}(x)}\tilde{\alpha}_{t}(x)=L(x)$. This will imply $r_{t+s}=1$ for all $s\geq 1$ again showing that we will recover the desired Root barrier structure.

Thus for each time point $t$ this construction will reveal a new layer of
stopping probabilities $(r_{t}(x))_{x\in\mathbb{Z}}$ which will be of Root
structure. Let $\rho_{\infty}$ denote the stopping time corresponding to the
field of stopping probabilities
$(r_{t}(x))_{(t,x)\in\mathbb{N}\times\mathbb{Z}}$ constructed as above. It
remains to show that $\mathcal{L}^{\lambda}(X_{\rho_{\infty}})=\mu$. As
$l_{t}^{x}$ is increasing and bounded from above by $L(x)$ the limit
$l_{\infty}^{x}:=\lim_{t\rightarrow\infty}l_{t}^{x}$ exists and equals the
expected local time of $X_{\rho_{\infty}}$ after the stopping time $\eta$,
$\mathbb{E}^{\lambda}\left[L_{\eta,\rho_{\infty}}^{x}(X)\right]=l_{\infty}^{t}.$
Let $U_{\mu_{\infty}}$ denote the potential of
$\mathcal{L}^{\lambda}\left(X_{\rho_{\infty}}\right)$, then due to Tanaka’s
formula we have

$U_{\mu_{\infty}}(x)=U_{\alpha_{x}}-l_{\infty}^{t},$

hence our stopping time will embed the right measure if and only if
$l_{\infty}^{t}=L(x).$ Consider the set

$I:=\\{x\in\mathbb{Z}:l_{\infty}^{x}<L(x)\\}=\\{x\in\mathbb{Z}:U_{\mu_{\infty}}(x)>U_{\mu}(x)\\}.$

To conclude the proof of the theorem we must show that $I$ is empty. A first
step is to show that for every $x\in I$ we have

$\mathbb{P}^{\lambda}\left[X_{\rho_{\infty}}=x\right]=0.$ (3.10)

Note that this is equivalent to $\tilde{\alpha}_{t}(x)\wedge r_{t}(x)=0$ for
all $t\in\mathbb{N}$. However, we cannot have $\tilde{\alpha}(x)=0$ for all
$t\in\mathbb{N}$ as this would imply that site $x$ is never reached by the
process $X$ with positive probability after time $\eta$, furthermore implying
$L(x)=0$, which is a contradiction. Thus there must exist at least one
$T\in\mathbb{N}$ such that $\tilde{\alpha}_{T}(x)>0$. Assume now that also
$r_{T}(x)>0$. Then $l_{\infty}^{x}\geq
l_{T+1}^{x}=l_{T}^{x}+\left(\frac{L(x)-l_{T}^{x}}{\tilde{\alpha}_{T}(x)}\right)\tilde{\alpha}_{T}(x)=L(x)$
which is, again, a contradiction, allowing us to conclude (3.10).

Now we proceed to show that $I$ must be empty. Consider a maximal interval
$J\subseteq I$, i.e. either $J=\\{\dots,x_{+}-1,x_{+}\\}$ and $x_{+}+1\not\in
I$, $J=\\{x_{-},x_{-}+1,\dots\\}$ and $x_{-}-1\not\in I$ or
$J=\\{x_{-},x_{-}+1,\dots,x_{+}-1,x_{+}\\}$ and both $x_{-}-1,x_{+}+1\not\in
I$. Then we must have $U_{\mu_{\infty}}(x_{-}-1)=U_{\mu}(x_{-}-1)$ resp.
$U_{\mu_{\infty}}(x_{+}+1)=U_{\mu}(x_{+}+1)$. Note that $U_{\mu_{\infty}}$ is
bounded from above by the concave function $U_{\alpha_{X}}$ and bounded from
below by the concave function $U_{\mu}$. Hence we cannot have that
$U_{\mu_{\infty}}|_{J}$ is a linear function and there must exists $x\in J$
such that

$U_{\mu_{\infty}}(x-1)-U_{\mu_{\infty}}(x)<U_{\mu_{\infty}}(x)-U_{\mu_{\infty}}(x+1).$

However, this is equivalent to

$\mathbb{P}^{\lambda}\left[X_{\rho_{\infty}}=x\right]=-\frac{1}{2}\left(U_{\mu_{\infty}}(x-1)+U_{\mu_{\infty}}(x+1)\right)+U_{\mu_{\infty}}(x)>0$

which contradicts Equation (3.10). Hence $J=\emptyset$, thus also
$I=\emptyset$ and our claim is proven. ∎

####  3.1.2. Existence of Discrete Delayed Rost Solutions

Given a delayed stopping time $\rho$ corresponding to a field of stopping
probabilities $(r_{t}(x))_{(t,x)\in\mathbb{N}\times\mathbb{Z}}$ we consider
the quantity

$\tilde{\mu}_{t}(x):=\mathbb{P}^{\lambda}\left[X_{\rho}=x,\rho\leq t\right],$

the ‘mass embedded until time $t$’. Then

$\tilde{\mu}_{t}(x)=\sum_{s=0}^{t}\tilde{\alpha}_{s}(x)r_{s}(x)$

for $\tilde{\alpha}_{t}$ as defined in the previous section. Furthermore
consider

$\nu_{t}(x):=\mu\left(\\{x\\}\right)-\tilde{\mu}_{t-1}(x),$

the ‘mass not yet embedded’ and note that it can be computed inductively using
information only up to time $t-1$. We can then also write

$\tilde{\mu}_{t}(x)=\mu\left(\\{x\\}\right)-\nu_{t}(x)+\tilde{\alpha}_{t}(x)r_{t}(x).$

Note that if the field of stopping probabilities embeds the measure $\mu$,
then

$\lim_{t\rightarrow\infty}\tilde{\mu}_{t}(x)=\mu\left(\\{x\\}\right)\text{
resp. }\lim_{t\rightarrow\infty}\nu_{t}(x)=0.$

With the help of these quantities we can give an explicit construction of Rost
solution to the discrete (dSEP).

######  Theorem 3.4.

Consider a field of stopping probabilities
$(r_{t}(x))_{(t,x)\in\mathbb{N}\times\mathbb{Z}}$ inductively defined via the
formula

$r_{t}(x)=\frac{\nu_{t}(x)}{\tilde{\alpha}_{t}(x)}\wedge
1=\frac{\left(\tilde{\alpha}_{t}\wedge\nu_{t}\right)\left(x\right)}{\tilde{\alpha}_{t}\left(x\right)}\text{
when }\tilde{\alpha}_{t}(x)>0$

and chosen to comply with (3.3) otherwise.

Then this field represents a Rost field of stopping probabilities and the
associated stopping time

$\rho=\inf\left\\{t\geq\eta:r_{t}(X_{t})>u_{t}\right\\}.$

will be a Rost solution to the discrete (dSEP).

###### Proof.

As both $\nu_{t}$ and $\tilde{\alpha}_{t}$ only use information that is either
given or acquired up to time $t-1$, it is clear that $r_{t}$ can be computed
iteratively through time, thus in each time step $t$ we identify the $t$-layer
$r_{t}(x)_{x\in\mathbb{Z}}$ of the probability field. Let us justify that
$(r_{t}(x))_{(t,x)\in\mathbb{N}\times\mathbb{Z}}$ defined this way both embeds
the right measure $\mu$ and is of Rost structure.

Firstly, if $\mu(\\{x\\})=0$ then $r_{t}(x)=0$ for all $t\in\mathbb{N}$, thus
consider only those $x$ such that $\mu(\\{x\\})>0$. Then consider the
following cases.

  1. $t=0:$

Only consider those $x$ such that $\tilde{\alpha}_{0}(x)=\alpha(0,x)>0$ as
otherwise the point $x$ cannot be reached by the process $X$ at time $0$ after
time $\eta$.

     * If $\tilde{\alpha}_{0}(x)\leq\mu(\\{x\\})$, then all mass available in $(0,x)$ should be stopped, hence $r_{0}(x)=1$ and $\tilde{\mu}_{0}(\\{x\\})=\tilde{\alpha}_{0}(x)\leq\mu(\\{x\\})$.

     * If $\tilde{\alpha}_{0}(x)>\mu(\\{x\\})$, then some mass needs to be stopped in $(0,x)$, precisely $r_{0}(x)=\frac{\mu(\\{x\\})}{\tilde{\alpha}_{t}(x)}$ as then we have $\tilde{\mu}_{0}(\\{x\\})=\mu(\\{x\\})$.

  2. $t>0:$

Only consider those $x$ such that $\tilde{\alpha}_{t}(x)>0$ as otherwise the
point $x$ cannot be reached by the process $X$ at time $t$ after time $\eta$.

     * If $\nu_{t}(x)=0$ then all necessary mass has already been embedded before time $t$, hence $r_{t}(x)=0$.

     * If $0<\tilde{\alpha}_{t}(x)\leq\nu_{t}(x)$ then the available mass in site $x$ at time $t$ does not exceed the mass still needed at site $x$, hence $r_{t}(x)=1$ as all mass can be added.

     * If $0<\nu_{t}(x)<\tilde{\alpha}_{t}(x)$ then we have mass missing in site $x$ but the available mass at time $t$ exceeds the necessary mass, hence we should only add the fraction $r_{t}(x)=\frac{\nu_{t}(x)}{\tilde{\alpha}_{t}(x)}$ as then we have $\tilde{\mu}_{t}(\\{x\\})=\mu(\\{x\\})-\nu_{t}(x)+\tilde{\alpha}_{t}(x)\frac{\nu_{t}(x)}{\tilde{\alpha}_{t}(x)}=\mu(\\{x\\})$.

It is crucial to note that the quantity $\nu_{t}(x)$ is decreasing and remains
at 0 once it has reached there, hence clearly the field of stopping
probabilities $(r_{t}(x))_{(t,x)\in\mathbb{N}\times\mathbb{Z}}$ defined as
above is of Rost structure.

We are left to formally show that the stopping time

$\rho_{\infty}:=\inf\left\\{t\geq\eta:r_{t}(X_{t})>u_{t}\right\\}$

embeds the right measure into the SSRW, i.e.
$\mathbb{P}^{\lambda}[X_{\rho_{\infty}}=x]=\mu(\\{x\\})$ for all
$x\in\mathbb{Z}$.

We consider the measure

$\displaystyle\mu_{\infty}(\\{x\\}):=\mathbb{P}^{\lambda}[X_{\rho_{\infty}}=x]=\lim_{t\rightarrow\infty}\tilde{\mu}_{t}(x)=\sum_{s=0}^{\infty}\tilde{\alpha}_{s}(x)p_{s}(x).$

Fist assume $\mu_{\infty}(\\{x\\})>\mu(\\{x\\})$. As this would be equivalent
to $\lim_{t\rightarrow\infty}\nu_{t}(x)<0$ there would need to exist a first
$T\in\mathbb{N}$ such that $\nu_{T}(x)<0$. However this contradicts the
construction of $r_{t}(x)$ as described above.
Hence we must have $\mu_{\infty}(\\{x\\})\leq\mu(\\{x\\})$ for all
$x\in\mathbb{Z}$.

Consider the set
$I:=\left\\{x\in\mathbb{Z}:\mu_{\infty}(\\{x\\})<\mu(\\{x\\})\right\\}$. If we
assume that $I$ is not empty then

$0\leq\sum_{x\in\mathbb{Z}}\mu_{\infty}(\\{x\\})<\sum_{x\in\mathbb{Z}}\mu(\\{x\\})=1.$

Note that
$\mu_{\infty}(\\{x\\})=\lim_{t\rightarrow\infty}\tilde{\mu}_{t}(x)<\mu(\\{x\\})$
is equivalent to $\nu_{t}(x)>0$ for every $t\in\mathbb{N}$, which in turn
implies $r_{t}(x)=1$ for all $t\in\mathbb{N}$ by the construction above. In
particular, this implies $\rho_{\infty}\leq
H_{x}^{\eta}:=\inf\\{t\geq\eta:X_{t}=x\\}$ which is a finite stopping time,
hence also $\mathbb{P}^{\lambda}[\rho_{\infty}<\infty]=1$. So $X_{\rho}$ is a
well defined random variable and we must have
$\sum_{x\in\mathbb{Z}}\mu_{\infty}(\\{x\\})=1$ which is a contradiction. This
implies $I=\emptyset$ and $\mu_{\infty}(\\{x\\})=\mu(\\{x\\})$, hence our
constructed field of stopping probabilities and consequently the associated
stopping time $\rho_{\infty}$ embeds the right measure. ∎

###  3.2. A Discrete Optimal Stopping Representation

In this section we will consider a second simple symmetric second random walk
$Y$ on the probability space $(\Omega,\mathbb{P})$, mutually independent of
the SSRW $X$ introduced in previous section. For given $x,y\in\mathbb{Z}$ we
recall $\mathbb{P}^{x}$ as the conditional distribution given $X_{0}=x$ and
analogously define $\mathbb{P}_{y}$ as the conditional distribution given
$Y_{0}=y$. Similarly, conditioning on both events simultaneously is denoted by
$\mathbb{P}^{x}_{y}$. We recall the starting distribution $\lambda$ for the
process $X$ and introduce a corresponding starting distribution $\nu$ for $Y$
analogously, leading to $\mathbb{P}_{\nu}$ as well as
$\mathbb{P}^{\lambda}_{\nu}$.

From this point onward we envision the process $X$ evolving “rightwards” from
some lattice point $(0,x)$ (where possibly $x=X_{0}\sim\lambda$) and the
process $Y$ evolving “leftwards” from the lattice point $(T,y)$ at time zero.
In this context a (stopping) time $\tau$ for the “backward” process $Y$ will
be measured as $T-\tau$ for the “forward” process $X$.

Let us define the discrete time equivalents of the objects introduced in
Section 2. We consider a discrete delay stopping time
$\eta\in\mathbb{N}=\\{0,1,\dots\\}$ for the process $X$. Then analogous to the
continuous case we define the space time measure

$\alpha:=\mathcal{L}^{\lambda}((\eta,X_{\eta}))\in\mathcal{P}(\mathbb{N}\times\mathbb{Z}),$

its spatial marginal

$\alpha_{X}(A):=\alpha(\mathbb{N}\times
A)=\mathcal{L}^{\lambda}(X_{\eta})(A)\quad\text{ for
}A\subseteq\mathbb{Z}\text{ measurable}$

and the $\mathbb{P}^{\lambda}$-potential of $X_{\eta\wedge T}$ by

$V^{\alpha}_{T}(y):=-\mathbb{E}^{\lambda}\left[\left|X_{\eta\wedge
T}-y\right|\right].$

For a Root (resp. Rost) Barrier $R\subseteq\mathbb{Z}\times\mathbb{Z}$
consider the discrete, delayed Root (resp. Rost) stopping time

$\rho_{\eta}:=\inf\left\\{t\geq\eta:(t,X_{t})\in R\right\\}.$

Similarly for a Root (resp. Rost) field of stopping probabilities
$(r_{t}(x))_{(t,x)\in\mathbb{N}\times\mathbb{Z}}$ and a vector
$U=(u_{0},u_{1},\dots)$ of iid $U[0,1]$-distributed random variables we
consider the discrete, delayed Root (resp. Rost) stopping time

$\rho_{\eta}:=\inf\left\\{t\geq\eta:r_{t}(X_{t})>u_{t}\right\\}.$

We will throughout this paper assume that $\left(X_{\rho^{\eta}\wedge
t}\right)_{t\in\mathbb{N}}$ is uniformly integrable. The stopping time
$\rho_{\eta}$ induces the measures

$\beta^{\alpha}:=\mathcal{L}^{\lambda}\left(X_{\rho_{\eta}}\right)\text{ as
well as }\beta^{\alpha}_{T}:=\mathcal{L}^{\lambda}\left(X_{\rho_{\eta}\wedge
T}\right)\text{ for }T\in\mathbb{N}$

as well as the (stopped) potential

$U_{\beta^{\alpha}_{T}}(y)=-\mathbb{E}^{\lambda}\left[\left|X_{\rho_{\eta}\wedge
T}-y\right|\right].$

Moreover, given a field $(r_{t}(x))_{(t,x)\in\mathbb{N}\times\mathbb{Z}}$ of
Root (resp. Rost) stopping probabilities we denote by $\mathcal{R}_{r}$ the
set of all fields of Root (resp. Rost) stopping probabilities that agree with
$r$ everywhere except on the boundary, precisely

$\mathcal{R}_{r}:=\left\\{(s_{t}(x))_{(t,x)\in\mathbb{N}\times\mathbb{Z}}:\parbox{241.84842pt}{
$(s_{t}(x))_{(t,x)\in\mathbb{N}\times\mathbb{Z}}$ is a Root (resp. Rost) field
of stopping probabilities s.t. $s_{t}(x)=r_{t}(x)$ given
$r_{t}(x)\in\\{0,1\\}$. }\right\\}.$

We will sometimes use the shorthand notation $s\in\mathcal{R}_{r}$ for
$s=(s_{t}(x))_{(t,x)\in\mathbb{N}\times\mathbb{Z}}$ when the context makes it
obvious. Furthermore, we define the set of all associated stopping times in
the following way

$\mathcal{T}_{r}:=\left\\{\inf\left\\{t\geq
0:s_{T-t}(Y_{t})>v_{t}\right\\}:\parbox{227.62204pt}{
$(s_{t}(x))_{(t,x)\in\mathbb{N}\times\mathbb{Z}}\in\mathcal{R}_{r}$ and
$V=(v_{0},\dots,v_{T})$ denotes a vector of iid $U[0,1]$-distributed random
variables.}\right\\}.$

Then we can then give the following discrete time analogue of (2.3)-(2.4),

######  Theorem 3.5.

Let $(r_{t}(x))_{(t,x)\in\mathbb{N}\times\mathbb{Z}}$ denote a Root field of
stopping probabilities, then we have the representation

$\displaystyle U_{\beta^{\alpha}_{T}}(y)$
$\displaystyle=\mathbb{E}_{y}\left[V^{\alpha}_{T-\tau^{*}}(Y_{\tau^{*}})+(U_{\beta^{\alpha}}-U_{\alpha_{X}})(Y_{\tau^{*}})\text{$11$}_{\tau^{*}<T}\right]$
(3.11) $\displaystyle=\sup_{\tau\leq
T}\mathbb{E}_{y}\left[V^{\alpha}_{T-\tau}(Y_{\tau})+(U_{\beta^{\alpha}}-U_{\alpha_{X}})(Y_{\tau})\text{$11$}_{\tau<T}\right],$
(3.12)

where all optimizers will be of the form $\tau^{*}:=\tau\wedge T$ for
$\tau\in\mathcal{T}_{r}$.

When $\rho_{\eta}$ corresponds to a discrete delayed Rost stopping the
discrete version of (2.5)-(2.6) reads the following.

######  Theorem 3.6.

Let $(r_{t}(x))_{(t,x)\in\mathbb{N}\times\mathbb{Z}}$ denote a Rost field of
stopping probabilities, then we have the representation

$\displaystyle U_{\beta^{\alpha}}(x)-U_{\beta^{\alpha}_{T}}(x)$
$\displaystyle=\mathbb{E}^{x}\left[U_{\beta^{\alpha}}(X_{\sigma_{*}})-V^{\alpha}_{T-\sigma_{*}}(X_{\sigma_{*}})\right]$
(3.13) $\displaystyle=\sup_{\sigma\leq
T}\mathbb{E}^{x}\left[U_{\beta^{\alpha}}(X_{\sigma})-V^{\alpha}_{T-\sigma}(X_{\sigma})\right],$
(3.14)

where all optimizers will be of the form $\sigma^{*}:=\sigma\wedge T$ for
$\sigma\in\mathcal{T}_{r}$.

It will become clear in Section 3.4 why the processes $X$ and $Y$ appear
differently in the Root and Rost optimal stopping problem.

####  3.2.1. The Core Argument

We present the core argument repeatedly used in [1] and crucial for further
results, an equality in expectation for differences of independent random
walks.

$\mathbb{E}^{x}_{y}\left[\left|X_{T-s}-Y_{s}\right|\right]=\mathbb{E}^{x}_{y}\left[|X_{T-(s-1)}-Y_{s-1}|\right].$
(3.15)

The following two remarks break down the key ingredients needed for proving
the core argument.

######  Remark 3.7.

Let $Z$ be a Rademacher random variable. Then for any $a\in\mathbb{Z}$ we have

$\mathbb{E}\left[\left|a+Z\right|\right]=|a|+\text{$11$}_{a=0}.$

######  Remark 3.8.

For a sigma algebra $\mathcal{H}$ let $A$ be a $\mathcal{H}$-measurable random
variable taking values in $\mathbb{Z}$ and let $Z$ be a Rademacher random
variable independent of $\mathcal{H}$. Then by Remark 3.7 and the Independence
Lemma we can conclude

$\mathbb{E}\left[|A+Z|\big{|}\mathcal{H}\right]=|A|+\text{$11$}_{A=0}.$

We can now prove the core argument (3.15). On the one hand we have

$\displaystyle\mathbb{E}^{x}_{y}\left[|X_{T-s}-Y_{s}|\right]$
$\displaystyle=\mathbb{E}^{x}_{y}\left[\mathbb{E}^{x}_{y}\left[|X_{T-s}-Y_{s}|\big{|}X_{T-s},Y_{s-1}\right]\right]$
$\displaystyle=\mathbb{E}^{x}_{y}\left[\mathbb{E}^{x}_{y}\left[|(X_{T-s}-Y_{s-1})-(Y_{s}-Y_{s-1})|\big{|}X_{T-s},Y_{s-1}\right]\right]$
$\displaystyle=\mathbb{E}^{x}_{y}\left[|X_{T-s}-Y_{s-1}|+\mathbbm{1}_{X_{T-s}=Y_{s-1}}\right]$

where we applied Remark 3.8 for the sigma algebra
$\mathcal{H}:=\sigma(X_{T-s},Y_{s-1})$, the $\mathcal{G}$-measurable random
variables $A:=X_{T-s}-Y_{s-1}$ and the Rademacher random variable
$Z:=Y_{s}-Y_{s-1}$ which is independent of $\mathcal{H}$. Analogously, we can
show

$\displaystyle\mathbb{E}^{x}_{y}\left[|X_{T-(s-1)}-Y_{s-1}|\right]$
$\displaystyle=\mathbb{E}^{x}_{y}\left[\mathbb{E}^{x}_{y}\left[|X_{T-s+1}-Y_{s-1}|\big{|}X_{T-s},Y_{s-1}\right]\right]$
$\displaystyle=\mathbb{E}^{x}_{y}\left[\mathbb{E}^{x}_{y}\left[|(X_{T-s}-Y_{s-1})+(X_{T-s+1}-X_{T-s})|\big{|}X_{T-s},Y_{s-1}\right]\right]$
$\displaystyle=\mathbb{E}^{x}_{y}\left[|X_{T-s}-Y_{s-1}|+\mathbbm{1}_{X_{T-s}=Y_{s-1}}\right],$

so altogether we have (3.15). See also Figure 3 for an illustration of the
appearance of the indicator function.

Figure 3. Illustrating the appearance of the indicator function in the core
argument.

In particular, Equation (3.15) implies an independence of $s$, more precisely

$\mathbb{E}^{x}_{y}\left[|X_{T-s}-Y_{s}|\right]=\mathbb{E}^{x}_{y}\left[|X_{T}-Y_{0}|\right]=\mathbb{E}^{x}_{y}\left[|X_{0}-Y_{T}|\right].$

Note that we can replace $s$ by a $Y$ stopping time $\tau<T$ to receive

$\mathbb{E}^{x}_{y}\left[|X_{T-\tau}-Y_{\tau}|\right]=\mathbb{E}^{x}_{y}\left[|X_{T}-Y_{0}|\right].$

Analogously, for an $X$ stopping time $\sigma<T$ we have

$\mathbb{E}^{x}_{y}\left[|X_{\sigma}-Y_{T-\sigma}|\right]=\mathbb{E}^{x}_{y}\left[|X_{0}-Y_{T}|\right],$

collectively this leads to the identity

$\mathbb{E}^{x}_{y}\left[|X_{T-\tau}-Y_{\tau}|\right]=\mathbb{E}^{x}_{y}\left[|X_{\sigma}-Y_{T-\sigma}|\right]$
(3.16)

which will serve as a key identity for subsequent arguments.

####  3.2.2. The Interpolation Function

In [1] it was crucial to define an interpolating function $F(s)$ which
connects between the LHS of Equation (1.2) and the RHS of Equations (1.2) and
(1.3). With only slight modification of the proofs in [1] we can define a more
general interpolation function and state the following lemma.

######  Lemma 3.9.

Let $\lambda$ be a starting measure for the process $X$ and $\nu$ be a
starting measure for the process $Y$. For an $X$ stopping time $\sigma$, a $Y$
stopping time $\tau$ and any $T\geq 0$ we consider the following interpolation
function

$F^{\lambda,\nu}_{\sigma,\tau}(s):=\mathbb{E}^{\lambda}_{\nu}\left[\left|X_{\sigma\wedge(T-\tau\wedge
s)}-Y_{\tau\wedge s}\right|\right].$ (3.17)

Then we have the following:

  1. (i)

The function $F^{\lambda,\nu}_{\sigma,\tau}(s)$ is increasing in $s$, more
precisely

$\displaystyle F^{\lambda,\nu}_{\sigma,\tau}(s)$
$\displaystyle=\mathbb{E}^{\lambda}_{\nu}\left[\left|X_{\sigma\wedge(T-\tau\wedge
s)}-Y_{\tau\wedge(s-1)}\right|+\text{$11$}_{X_{\sigma\wedge(T-s)}=Y_{s-1},\tau\geq
s}\right]$ (3.18)
$\displaystyle\geq\mathbb{E}^{\lambda}_{\nu}\left[\left|X_{\sigma\wedge(T-\tau\wedge
s)}-Y_{\tau\wedge(s-1)}\right|+\text{$11$}_{X_{\sigma\wedge(T-s)}=Y_{s-1},\tau\geq
s,\sigma>T-s}\right]=F^{\lambda,\nu}_{\sigma,\tau}(s-1).$ (3.19)

  2. (ii)

If $\sigma$ is a (possibly randomized, possibly delayed) forward Root stopping
time for the process $X$ and $\tau$ is a (possibly randomized) backwards Root
stopping time for the process $Y$ then $F^{\lambda,\nu}_{\sigma,\tau}(s)$ is
constant in $s$.

###### Proof.

The essence of the proof of $(i)$ is an appropriate application of the Core
Argument presented above, and $(i)$ follows in complete analogy to the proofs
of [1, Lemma 3.3, Lemma 3.4]. For $(ii)$ we have to make some modifications.

Let $(r_{t}(x))_{(t,x)\in\mathbb{N}\times\mathbb{Z}}$ denote a Root field of
stopping probabilities, then for
$(s_{t}(x))_{(t,x)\in\mathbb{N}\times\mathbb{Z}}\in\mathcal{R}_{r}$ consider
the stopping times

$\displaystyle\rho^{\eta}$
$\displaystyle:=\inf\left\\{t\geq\eta:r_{t}(X_{t})>u_{t}\right\\},\,\,\text{
and }$ $\displaystyle\tau^{*}$ $\displaystyle:=\inf\left\\{t\geq
0:s_{T-t}(Y_{t})>v_{t}\right\\}\wedge T.$

In order to show equality in $(i)$ for these stopping times, it suffices to
show equality of the indicator functions appearing in (3.18) and (3.19),
equivalently

$\left\\{\rho^{\eta}>T-s\\}\supseteq\\{X_{\rho^{\eta}\wedge(T-s)}=Y_{s-1},\tau^{*}\geq
s\right\\}$

up to nullsets. Indeed, on $\\{\tau^{*}\geq s\\}$ we deduce $\tau^{*}>s-1$.
Hence we must have $s_{T-(s-1)}\left(Y_{s-1}\right)<1$ as otherwise
$\tau^{*}=s-1$ almost surely. By the definition of the Root stopping
probabilities we thus have
$s_{u}\left(Y_{s-1}\right)=r_{u}\left(Y_{s-1}\right)=0$ for all $u<T-(s-1)$.
Moreover, on the set $\\{X_{\rho^{\eta}\wedge(T-s)}=Y_{s-1}\\}$ we have
$r_{u}\left(X_{\rho^{\eta}\wedge(T-s)}\right)=0$ for all $u<T-(s-1)$. In
particular, since $\rho^{\eta}\wedge(T-s)<T-(s-1)$, on the set
$\\{X_{\rho^{\eta}\wedge(T-s)}=Y_{s-1}\\}$ we have
$r_{\rho^{\eta}\wedge(T-s)}\left(X_{\rho^{\eta}\wedge(T-s)}\right)=0$. Hence
$\rho^{\eta}>T-s$ needs to be satisfied as otherwise the Root properties of
the stopping probabilities would be violated. See Figure 4 for an illustration
of these arguments. ∎

(a) Here $\tau^{*}\geq s$ and $X_{\rho_{\eta}\wedge(T-s)}=Y_{s-1}$. We see
that in this case $\rho_{\eta}\wedge(T-s)=T-s$ must hold as otherwise
$Y_{\tau^{*}}$ would have stopped earlier.

(b) Here $\rho_{\eta}\wedge(T-s)=\rho_{\eta}$. We see how
$X_{\rho_{\eta}\wedge(T-s)}=Y_{s-1}$ implies that we must have $\tau^{*}\leq
s-1$ due to the Root barrier structure.

Figure 4. An illustration of some different cases that appear when
investigating equality of the interpolation function for forward and backward
Root stopping times.

###  3.3. The Root Optimal Stopping Representation

Let us introduce some frequently used notations. For the choice of
$\nu=\delta_{y}$ we simplify the notation of the interpolation function
between the forward and backward Root stopping times to

$F^{\alpha}(s):=F^{\lambda,y}_{\rho_{\eta},\tau^{*}}(s).$

Here $\alpha$ denotes the space-time law induced by the delay stopping time
$\eta$ and $\beta^{\alpha}$ is the corresponding delayed Root law as defined
in Section 3.2. For a given stopping time $\tau$ consider the function

$u^{\alpha}_{\tau}(T,y):=\mathbb{E}_{y}\left[V^{\alpha}_{T-\tau}(Y_{\tau})+(U_{\beta^{\alpha}}-U_{\alpha_{X}})(Y_{\tau})\text{$11$}_{\tau<T}\right].$
(3.20)

We also introduce

$u^{\alpha}(T,y):=u^{\alpha}_{\tau^{*}}(T,y)$

for a backward Root stopping time $\tau^{*}=\inf\left\\{t\geq
0:s_{T-t}(Y_{t})>v_{t}\right\\}\wedge T$. Considering this refined notation
Equations (3.11)-(3.12) can be written in the following way

$\displaystyle U_{\beta^{\alpha}_{T}}(y)$ $\displaystyle=u^{\alpha}(T,y)$
(3.21) $\displaystyle=\sup_{\tau\leq T}u^{\alpha}_{\tau}(T,y).$ (3.22)

Furthermore, it will be of importance that the function $u^{\alpha}_{\tau}$
has the following alternative representation

$\displaystyle u^{\alpha}_{\tau}(T,y)$
$\displaystyle=\mathbb{E}_{y}\left[V^{\alpha}_{T-\tau}(Y_{\tau})+(U_{\beta^{\alpha}}-U_{\alpha_{X}})(Y_{\tau})\text{$11$}_{\tau<T}\right]$
(3.23)
$\displaystyle=-\mathbb{E}^{\lambda}_{y}\left[\left|X_{\eta\wedge(T-\tau)}-Y_{\tau}\right|+\left(\left|X_{\rho_{\eta}}-Y_{\tau}\right|-\left|X_{\eta}-Y_{\tau}\right|\right)\text{$11$}_{\tau<T}\right].$
(3.24)

To further simplify and rewrite these expressions we observe the following
lemma.

######  Lemma 3.10.

Let $\eta$ and $\theta$ be delay stopping times for the processes $X$ and $Y$
respectively. By $(r_{t}(x))_{(t,x)\in\mathbb{N}\times\mathbb{Z}}$ we denote a
Root field of stopping probabilities. For mutually independent
$U[0,1]$-distributed random variables $u_{0},u_{1},\dots,v_{0},v_{1},\dots$ we
consider the forward Root stopping time
$\rho:=\inf\left\\{t\geq\eta:r_{t}(X_{t})>u_{t}\right\\}$ and for
$s\in\mathcal{R}_{r}$ the backward Root stopping time $\tau:=\inf\left\\{t\geq
0:s_{T-t}(Y_{t})>v_{t}\right\\}\in\mathcal{T}_{r}$.

Furthermore we introduce the filtration
$\mathcal{G}_{t}:=\sigma\left((X_{s})_{0\leq s\leq t},(Y_{s})_{0\leq s\leq
T},u_{1},\dots,u_{t},v_{1},\dots,v_{T}\right)$. Then for all
$A\in\mathcal{H}:=\mathcal{G}_{\rho\wedge\left(\eta\vee(T-\tau)\right)}$ with
$\\{\tau<T\\}\subseteq A$ we have

$\displaystyle\mathbb{E}^{\lambda}_{\nu}\left[\left|X_{\rho}-Y_{\tau}\right|\text{$11$}_{A}\right]=\mathbb{E}^{\lambda}_{\nu}\left[\left|X_{\rho\wedge\left(\eta\vee(T-\tau)\right)}-Y_{\tau}\right|\text{$11$}_{A}\right].$
(3.25)

###### Proof.

As $X$ is independent of $Y$, we have that $X$ is a $(\mathcal{G}_{t})$
martingale and furthermore $\eta$, $\rho$ as well as
$\tilde{\sigma}:=\eta\vee(T-\tau)$ are $(\mathcal{G}_{t})$ stopping times.
Hence, by the optional sampling theorem we can conclude that for every
$A\in\mathcal{H}=\mathcal{G}_{\rho\wedge\tilde{\sigma}}$ the following holds

$\mathbb{E}^{\lambda}_{\nu}\left[X_{\rho}\text{$11$}_{A}\right]=\mathbb{E}^{\lambda}_{\nu}\left[X_{\rho\wedge\tilde{\sigma}}\text{$11$}_{A}\right].$
(3.26)

By definition of the Root stopping probabilities and the definition of $\tau$,
on the set $\\{\tau<T\\}$ we have $s_{T-\tau}\left(Y_{\tau}\right)>0$.
Furthermore
$s_{T-\tau+u}\left(Y_{\tau}\right)=r_{T-\tau+u}\left(Y_{\tau}\right)=1$ for
all $u\geq 1$. Moreover, on the set
$\\{\rho>\tilde{\sigma},X_{\tilde{\sigma}}<Y_{\tau}\\}$ we must have that
$X_{\rho}\leq Y_{\tau}$ as otherwise the Root property of the stopping
probabilities would be violated. We can argue analogously that on
$\\{\rho>\tilde{\sigma},X_{\tilde{\sigma}}\geq Y_{\tau}\\}$ we must have
$X_{\rho}\geq Y_{\tau}$. Then

$\displaystyle\mathbb{E}^{\lambda}_{\nu}\left[\left|X_{\rho}-Y_{\tau}\right|\text{$11$}_{A}\right]$
$\displaystyle=\mathbb{E}^{\lambda}_{\nu}\left[\left|X_{\rho}-Y_{\tau}\right|\text{$11$}_{A,\rho\leq\tilde{\sigma}}+\left|X_{\rho}-Y_{\tau}\right|\text{$11$}_{A,\rho>\tilde{\sigma}}\right]$
$\displaystyle=\mathbb{E}^{\lambda}_{\nu}\left[\left|X_{\rho}-Y_{\tau}\right|\text{$11$}_{A,\rho\leq\tilde{\sigma}}+\left|X_{\rho}-Y_{\tau}\right|\text{$11$}_{A,\rho>\tilde{\sigma},X_{\tilde{\sigma}}<Y_{\tau}}+\left|X_{\rho}-Y_{\tau}\right|\text{$11$}_{A,\rho>\tilde{\sigma},X_{\tilde{\sigma}}\geq
Y_{\tau}}\right]$
$\displaystyle=\mathbb{E}^{\lambda}_{\nu}\left[\left|X_{\rho}-Y_{\tau}\right|\text{$11$}_{A,\rho\leq\tilde{\sigma}}-\left(X_{\rho}-Y_{\tau}\right)\text{$11$}_{A,\rho>\tilde{\sigma},X_{\tilde{\sigma}}<Y_{\tau}}+\left(X_{\rho}-Y_{\tau}\right)\text{$11$}_{A,\rho>\tilde{\sigma},X_{\tilde{\sigma}}\geq
Y_{\tau}}\right]$
$\displaystyle=\mathbb{E}^{\lambda}_{\nu}\left[\left|X_{\rho}-Y_{\tau}\right|\text{$11$}_{A,\rho\leq\tilde{\sigma}}-\left(X_{\rho\wedge\tilde{\sigma}}-Y_{\tau}\right)\text{$11$}_{A,\rho>\tilde{\sigma},X_{\tilde{\sigma}}<Y_{\tau}}+\left(X_{\rho\wedge\tilde{\sigma}}-Y_{\tau}\right)\text{$11$}_{A,\rho>\tilde{\sigma},X_{\tilde{\sigma}}\geq
Y_{\tau}}\right]$
$\displaystyle=\mathbb{E}^{\lambda}_{\nu}\left[\left|X_{\rho\wedge\tilde{\sigma}}-Y_{\tau}\right|\text{$11$}_{A}\right].$

where we use Equation (3.26) and the fact that
$\\{\rho>\tilde{\sigma},X_{\tilde{\sigma}}<Y_{\tau}\\},\\{\rho>\tilde{\sigma},X_{\tilde{\sigma}}\geq
Y_{\tau}\\}\in\mathcal{H}$. ∎

Choosing $\nu=\delta_{y}$, $\rho=\rho_{\eta}$ and $\theta=0$ in the lemma
above enables us to prove the following.

######  Lemma 3.11.

The RHS of Equation (3.11) equals the terminal value of the interpolation
function, that is

$\displaystyle-u^{\alpha}(T,y)=F^{\alpha}(T).$ (3.27)

###### Proof.

Recall the representation (3.24) and consider the following decomposition

$\displaystyle-u^{\alpha}(T,y)=$
$\displaystyle\,\mathbb{E}^{\lambda}_{y}\left[\left|X_{\eta\wedge(T-\tau^{*})}-Y_{\tau^{*}}\right|+\left(\left|X_{\rho_{\eta}}-Y_{\tau^{*}}\right|-\left|X_{\eta}-Y_{\tau^{*}}\right|\right)\text{$11$}_{\tau^{*}<T}\right]$
$\displaystyle=$
$\displaystyle\,\mathbb{E}^{\lambda}_{y}\left[\left|X_{\eta\wedge(T-\tau^{*})}-Y_{\tau^{*}}\right|\text{$11$}_{\eta>T}+\left(\left|X_{\rho_{\eta}}-Y_{\tau^{*}}\right|-\left|X_{\eta}-Y_{\tau^{*}}\right|\right)\text{$11$}_{\tau^{*}<T,\eta>T}\right]$
(3.28) $\displaystyle+$
$\displaystyle\,\mathbb{E}^{\lambda}_{y}\left[\left|X_{\eta\wedge(T-\tau^{*})}-Y_{\tau^{*}}\right|\text{$11$}_{\eta\leq
T}+\left(\left|X_{\rho_{\eta}}-Y_{\tau^{*}}\right|-\left|X_{\eta}-Y_{\tau^{*}}\right|\right)\text{$11$}_{\tau^{*}<T,\eta\leq
T}\right].$ (3.29)

We will investigate the two lines (3.28) and (3.29) separately.

Let us first consider (3.28). As $\rho_{\eta}\geq\eta$, we observe that on the
event $\\{\eta>T\\}$ we have
$\eta\wedge(T-\tau^{*})=T-\tau^{*}=\rho_{\eta}\wedge(T-\tau^{*})$, hence for
the first term of (3.28) we can conclude

$\mathbb{E}^{\lambda}_{y}\left[\left|X_{\eta\wedge(T-\tau^{*})}-Y_{\tau^{*}}\right|\text{$11$}_{\eta>T}\right]=\mathbb{E}^{\lambda}_{y}\left[\left|X_{\rho_{\eta}\wedge(T-\tau^{*})}-Y_{\tau^{*}}\right|\text{$11$}_{\eta>T}\right].$
(3.30)

Furthermore, note the following:

  * On the event $\\{\tau^{*}<T\\}$ the stopping time $\tau^{*}$ equals a backward Root stopping time.

  * On the event $\\{\eta>T\\}$ we have $\eta\vee(T-\tau^{*})=\eta=\rho_{\eta}\wedge(\eta\vee(T-\tau^{*}))$.

  * We have $\\{\tau^{*}<T,\eta>T\\}\in\mathcal{H}$ (for $\mathcal{H}$ defined in Lemma 3.10).

Therefore we can apply Lemma 3.10 to the second term of (3.28) to arrive at

$\displaystyle\,\mathbb{E}^{\lambda}_{y}\left[\left(\left|X_{\rho_{\eta}}-Y_{\tau^{*}}\right|-\left|X_{\eta}-Y_{\tau^{*}}\right|\right)\text{$11$}_{\tau^{*}<T,\eta>T}\right]$
$\displaystyle=$
$\displaystyle\,\mathbb{E}^{\lambda}_{y}\left[\left(\left|X_{\rho_{\eta}}-Y_{\tau^{*}}\right|-\left|X_{\rho_{\eta}\wedge(\eta\vee(T-\tau^{*}))}-Y_{\tau^{*}}\right|\right)\text{$11$}_{\tau^{*}<T,\eta>T}\right]=\,0.$
(3.31)

To summarize, line (3.28) reduces to

$\mathbb{E}^{\lambda}_{y}\left[\left|X_{\rho_{\eta}\wedge(T-\tau^{*})}-Y_{\tau^{*}}\right|\text{$11$}_{\eta>T}\right].$
(3.32)

Next we consider (3.29). Let us start by examining the first term of (3.29)
which can be decomposed further into

$\displaystyle\,\mathbb{E}^{\lambda}_{y}\left[\left|X_{\eta\wedge(T-\tau)}-Y_{\tau^{*}}\right|\text{$11$}_{\eta\leq
T}\right]$ $\displaystyle=$
$\displaystyle\,\mathbb{E}^{\lambda}_{y}\left[\left|X_{\eta\wedge(T-\tau)}-Y_{\tau^{*}}\right|\text{$11$}_{\eta\leq
T,T-\eta\leq\tau^{*}}\right]+\mathbb{E}^{\lambda}_{y}\left[\left|X_{\eta\wedge(T-\tau)}-Y_{\tau^{*}}\right|\text{$11$}_{\eta\leq
T,\tau^{*}<T-\eta}\right]$ $\displaystyle=$
$\displaystyle\,\mathbb{E}^{\lambda}_{y}\left[\left|X_{\rho_{\eta}\wedge(T-\tau)}-Y_{\tau^{*}}\right|\text{$11$}_{\eta\leq
T,T-\eta\leq\tau^{*}}\right]+\mathbb{E}^{\lambda}_{y}\left[\left|X_{\eta}-Y_{\tau^{*}}\right|\text{$11$}_{\eta\leq
T,\tau^{*}<T-\eta}\right].$ (3.33)

Similarly, the second term of (3.29) decomposes into

$\displaystyle\mathbb{E}^{\lambda}_{y}\left[\left(\left|X_{\rho_{\eta}}-Y_{\tau^{*}}\right|-\left|X_{\eta}-Y_{\tau^{*}}\right|\right)\text{$11$}_{\tau^{*}<T,\eta\leq
T}\right]$ $\displaystyle=$
$\displaystyle\,\mathbb{E}^{\lambda}_{y}\left[\left(\left|X_{\rho_{\eta}}-Y_{\tau^{*}}\right|-\left|X_{\eta}-Y_{\tau^{*}}\right|\right)\text{$11$}_{\tau^{*}<T,\eta\leq
T,T-\eta\leq\tau^{*}}\right]$ (3.34) $\displaystyle+$
$\displaystyle\,\mathbb{E}^{\lambda}_{y}\left[\left(\left|X_{\rho_{\eta}}-Y_{\tau^{*}}\right|-\left|X_{\eta}-Y_{\tau^{*}}\right|\right)\text{$11$}_{\eta\leq
T,\tau^{*}<T-\eta}\right].$ (3.35)

Importantly, the second term of (3.33) cancels out the second term of (3.35).

We will proceed to conclude that the terms depicted in (3.34) will equate to
0. For this purpose observe that:

  * On the event $\\{\tau^{*}<T\\}$ the stopping time $\tau^{*}$ equals a backward Root stopping time.

  * On the event $\\{T-\eta\leq\tau^{*}\\}$ we have $\eta\vee(T-\tau^{*})=\eta=\rho_{\eta}\wedge(\eta\vee(T-\tau^{*}))$.

  * We have $\\{\tau^{*}<T,\eta\leq T,T-\eta\leq\tau^{*}\\}\in\mathcal{H}$.

Hence, we can apply Lemma 3.10 to deduce

$\displaystyle\,\mathbb{E}^{\lambda}_{y}\left[\left(\left|X_{\rho_{\eta}}-Y_{\tau^{*}}\right|-\left|X_{\eta}-Y_{\tau^{*}}\right|\right)\text{$11$}_{\tau^{*}<T,\eta\leq
T,T-\eta\leq\tau^{*}}\right]$ $\displaystyle=$
$\displaystyle\,\mathbb{E}^{\lambda}_{y}\left[\left(\left|X_{\rho_{\eta}}-Y_{\tau^{*}}\right|-\left|X_{\rho_{\eta}\wedge(\eta\vee(T-\tau^{*}))}-Y_{\tau^{*}}\right|\right)\text{$11$}_{\tau^{*}<T,\eta\leq
T,T-\eta\leq\tau^{*}}\right]$ $\displaystyle=$ $\displaystyle\,0.$ (3.36)

The final term left to consideration is the first term in (3.35). For this
purpose, note that

  * on the event $\\{\tau^{*}<T-\eta\\}$ we have $\eta\vee(T-\tau^{*})=(T-\tau^{*})$, and

  * $\\{\eta\leq T,\tau^{*}<T-\eta\\}\in\mathcal{H}$.

Hence, application of Lemma 3.10 to the first term of (3.35) yields

$\displaystyle\,\mathbb{E}^{\lambda}_{y}\left[\left|X_{\rho_{\eta}}-Y_{\tau^{*}}\right|\text{$11$}_{\eta\leq
T,\tau^{*}<T-\eta}\right]=\mathbb{E}^{\lambda}_{y}\left[\left|X_{\rho_{\eta}\wedge(T-\tau^{*})}-Y_{\tau^{*}}\right|\text{$11$}_{\eta\leq
T,\tau^{*}<T-\eta}\right].$ (3.37)

To summarize, (3.29) reduces to

$\mathbb{E}^{\lambda}_{y}\left[\left|X_{\rho_{\eta}\wedge(T-\tau^{*})}-Y_{\tau^{*}}\right|\text{$11$}_{\eta\leq
T}\right].$ (3.38)

Combining the observations (3.32) and (3.38) the desired identity now becomes
easy to see:

$-u^{\alpha}(T,y)=\mathbb{E}^{\lambda}_{y}\left[\left|X_{\rho_{\eta}\wedge(T-\tau^{*})}-Y_{\tau^{*}}\right|\right]=F^{\alpha}(T).$

∎

We are ready to prove Theorem 3.5, the optimal stopping representation of Root
solutions to (dSEP).

###### Proof of Theorem 3.5.

We begin by proving (3.11) through consideration of the interpolation function

$F^{\alpha}(s)=F^{\lambda,y}_{\rho_{\eta},\tau^{*}}(s)=\mathbb{E}^{\lambda}_{y}\left[\left|X_{\rho_{\eta}\wedge(T-\tau^{*}\wedge
s)}-Y_{\tau^{*}\wedge s}\right|\right].$

Then $-F^{\alpha}(0)=\mathbb{E}^{\lambda}_{y}\left[\left|X_{\rho_{\eta}\wedge
T}-Y_{0}\right|\right]=U_{\beta^{\alpha}_{T}}(y)$ which equals the LHS of
(3.11), equivalently of (3.21). It was the purpose of Lemma 3.11 to show that
$-F^{\alpha}(T)$ equals the RHS of (3.11), equivalently of (3.21). The
equality in (3.11) now follows by Lemma 3.9 $(ii)$, which states that the
interpolation function $F^{\alpha}(T)$ is constant given our consideration of
Root stopping times.

Let us proceed to establish the optimal stopping problem (3.12). We keep the
Root stopping time $\rho_{\eta}$ but allow for an arbitrary $Y$ stopping time
$\tau\leq T$. It still remains true that
$F^{\lambda,y}_{\rho_{\eta},\tau}(0)=-U_{\beta^{\alpha}}(y)$, and due to Lemma
3.9 $(i)$ we have the inequality $-U_{\beta^{\alpha}}(y)\leq
F^{\lambda,y}_{\rho_{\eta},\tau}(T)$. Therefore, we are left to show that

$F^{\lambda,y}_{\rho_{\eta},\tau}(T)\leq
u^{\alpha}_{\tau}(T,y)=-\mathbb{E}_{y}\left[V^{\alpha}_{T-\tau}(Y_{\tau})+(U_{\beta^{\alpha}}-U_{\alpha_{X}})(Y_{\tau})\text{$11$}_{\tau<T}\right],$

or equivalently

$\mathbb{E}^{\lambda}_{y}\left[\left|X_{\rho_{\eta}\wedge(T-\tau)}-Y_{\tau}\right|\right]\leq\mathbb{E}^{\lambda}_{y}\left[\left|X_{\eta\wedge(T-\tau)}-Y_{\tau}\right|+\left(\left|X_{\rho_{\eta}}-Y_{\tau}\right|-\left|X_{\eta}-Y_{\tau}\right|\right)\text{$11$}_{\tau<T}\right].$
(3.39)

We will consider a decomposition into the events $\\{\eta>T-\tau\\}$ and
$\\{\eta\leq T-\tau\\}$.

Due to Jensen’s inequality and optional sampling we have the following

$\mathbb{E}^{\lambda}_{y}\left[\left(\left|X_{\rho_{\eta}}-Y_{\tau}\right|-\left|X_{\eta}-Y_{\tau}\right|\right)\text{$11$}_{\tau<T,\eta>T-\tau}\right]\geq
0$

and can conclude

$\displaystyle\mathbb{E}^{\lambda}_{y}\left[\left|X_{\rho_{\eta}\wedge(T-\tau)}-Y_{\tau}\right|\text{$11$}_{\eta>T-\tau}\right]$
$\displaystyle=\mathbb{E}^{\lambda}_{y}\left[\left|X_{\eta\wedge(T-\tau)}-Y_{\tau}\right|\text{$11$}_{\eta>T-\tau}\right]$
$\displaystyle\leq\mathbb{E}^{\lambda}_{y}\left[\left|X_{\eta\wedge(T-\tau)}-Y_{\tau}\right|\text{$11$}_{\eta>T-\tau}+\left(\left|X_{\rho_{\eta}}-Y_{\tau}\right|-\left|X_{\eta}-Y_{\tau}\right|\right)\text{$11$}_{\tau<T,\eta>T-\tau}\right].$

On the other hand we have

$\displaystyle\mathbb{E}^{\lambda}_{y}\left[\left|X_{\rho_{\eta}\wedge(T-\tau)}-Y_{\tau}\right|\text{$11$}_{\eta\leq
T-\tau}\right]$
$\displaystyle=\mathbb{E}^{\lambda}_{y}\left[\left|X_{\rho_{\eta}\wedge(T-\tau)}-Y_{\tau}\right|\text{$11$}_{\eta\leq
T-\tau,\tau<T}+\left|X_{0}-Y_{\tau}\right|\text{$11$}_{\eta\leq
T-\tau,\tau=T}\right]$
$\displaystyle\leq\mathbb{E}^{\lambda}_{y}\left[\left|X_{\rho_{\eta}}-Y_{\tau}\right|\text{$11$}_{\eta\leq
T-\tau,\tau<T}+\left|X_{\eta}-Y_{\tau}\right|\text{$11$}_{\eta\leq
T-\tau,\tau=T}\right]$
$\displaystyle=\mathbb{E}^{\lambda}_{y}\left[\left|X_{\eta}-Y_{\tau}\right|\text{$11$}_{\eta\leq
T-\tau}+\left(\left|X_{\rho_{\eta}}-Y_{\tau}\right|-\left|X_{\eta}-Y_{\tau}\right|\right)\text{$11$}_{\eta\leq
T-\tau,\tau<T}\right]$
$\displaystyle=\mathbb{E}^{\lambda}_{y}\left[\left|X_{\eta\wedge(T-\tau)}-Y_{\tau}\right|\text{$11$}_{\eta\leq
T-\tau}+\left(\left|X_{\rho_{\eta}}-Y_{\tau}\right|-\left|X_{\eta}-Y_{\tau}\right|\right)\text{$11$}_{\eta\leq
T-\tau,\tau<T}\right]$

where the inequality again follows by Jensen’s inequality and optional
sampling. Together this proves (3.39). Thus we have shown that

$U_{\beta^{\alpha}}(y)\geq u^{\alpha}_{\tau}(T,y)$

which concludes the proof of (3.12). ∎

###  3.4. The Root-Rost-Symmetry

To establish the optimal stopping representation of Rost solution to (dSEP) we
could simply repeat the appropriate analogues of the arguments in the section
above. Instead however we will derive the Rost representation from the Root
one by observing a symmetry between the two similar to the approach in [1].

We will first give a brief summary of the results in [1] which were stated in
non-randomized terms.

Recall the definition of a discrete Rost barrier
$\bar{R}\subseteq\mathbb{N}\times\mathbb{Z}$, that is

  * If $(t,m)\in\bar{R}$ then for all $s<t$ also $(s,m)\in\bar{R}$.

Now observe that for any $T\in\mathbb{N}$ we can transform this Rost barrier
into a Root Barrier $R_{T}$ in the following way

$R_{T}:=\left\\{(T-t,x):(t,x)\in R\right\\}.$ (3.40)

To more conveniently apply results from the sections above we will reverse the
roles of $X$ and $Y$ for Rost stopping times.

Consider a non-delayed (forward) Rost stopping time
$\bar{\rho}=\inf\left\\{t\geq 0:(t,Y_{t})\in\bar{R}\right\\}$. We can now
observe as illustrated in Figure 5 that the (forward) Rost stopping time
$\bar{\rho}$ can be represented as a backward Root stopping time
$\tau:=\inf\left\\{t\geq 0:(T-t,Y_{t})\in R_{T}\right\\}$, and that the
backwards Rost stopping time $\sigma:=\inf\left\\{t\geq
0:(T-t,X_{t})\in\bar{R}\right\\}$ can be represented as a (non-delayed,
forward) Root stopping time $\rho:=\rho_{0}=\inf\left\\{t\geq 0:(t,X_{t})\in
R_{T}\right\\}$, to summarize

$\displaystyle\begin{split}\bar{\rho}=\inf\left\\{t\geq
0:(t,Y_{t})\in\bar{R}\right\\}=\inf\left\\{t\geq 0:(T-t,Y_{t})\in
R_{T}\right\\}=\tau\\\ \sigma=\inf\left\\{t\geq
0:(T-t,X_{t})\in\bar{R}\right\\}=\inf\left\\{t\geq 0:(t,X_{t})\in
R_{T}\right\\}=\rho.\end{split}$ (3.41)

Figure 5. An illustration of the connection between $\bar{R}$ and $R_{T}$,
resp. between $\bar{\rho}$ and $\tau$ as well as $\sigma$ and $\rho$ without
delay.

Using this symmetry, in [1] the Rost optimal stopping problem was then derived
with the methods established for the Root optimal stopping problem using the
following proposition.

######  Proposition 3.12 ([1, Proposition 3.7]).

For each $x,y,T$, any $Y$-stopping time $\tau$ such that
$\mathbb{E}_{y}[|Y_{\tau}|]<\infty$, and every $\\{0,\dots,T\\}$-valued
$X$-stopping time $\sigma$, we have

$\displaystyle\mathbb{E}_{y}\left[|x-Y_{\tau}|-|x-Y_{\tau\wedge T}|\right]$
$\displaystyle\leq\mathbb{E}^{x}_{y}\left[|X_{\sigma}-Y_{\tau}|-|X_{\sigma}-y|\right].$
(3.42)

Suppose furthermore that

$\tau=\inf\\{t\in\mathbb{N}:(T-t,Y_{t})\in R\\},$ (3.43)

for a Root barrier $R$ and that $\sigma=\rho^{Root}\wedge T$. Then there is
equality in (3.42).

The proof given in [1] relied heavily on the interpolation function
$F_{\sigma,\tau}(s)=F^{x,y}_{\sigma,\tau}(s)=\mathbb{E}^{x}_{y}\left[\left|X_{\sigma\wedge(T-\tau\wedge
s)}-Y_{\tau\wedge s}\right|\right]$ in the following way. To see inequality we
observe

$\displaystyle\mathbb{E}_{y}\left[|x-Y_{\tau}|-|x-Y_{\tau\wedge T}|\right]$
$\displaystyle\leq\mathbb{E}^{x}_{y}\left[|X_{\sigma}-Y_{\tau}|\right]-F_{\sigma,\tau}(T)$
$\displaystyle\leq\mathbb{E}^{x}_{y}\left[|X_{\sigma}-Y_{\tau}|\right]-F_{\sigma,\tau}(0)$
$\displaystyle=\mathbb{E}^{x}_{y}\left[|X_{\sigma}-Y_{\tau}|-|X_{\sigma}-y|\right].$

Equality for Root forward and backward stopping times follows from Lemma 3.9
(ii). In the delayed regimes however, these arguments cannot be repeated
verbatim as Lemma 3.9 (ii) does not hold for delayed backwards Root stopping
times.

We will observe an analogous symmetry to (3.41) in the delayed regime and give
the appropriate generalization of the symmetries (3.41) as well as Proposition
3.12.

#### A delayed randomized Root-Rost-Symmetry

Let $(\bar{r}_{t}(x))_{(t,x)\in\mathbb{N}\times\mathbb{Z}}$ denote a field of
Rost stopping probabilities. Then for any $T\in\mathbb{N}$ we can transform
these Rost stopping probabilities into a field
$(r^{T}_{t}(x))_{(t,x)\in\mathbb{Z}\times\mathbb{Z}}$ of Root stopping
probabilities in the following way

$r_{t}^{T}(x):=\bar{r}_{T-t}(x).$ (3.44)

Note that the definitions of Root and Rost fields of stopping probabilities
naturally extend to $(t,x)\in\mathbb{Z}\times\mathbb{Z}$. Consider a delayed
(forward) Rost stopping time

$\bar{\rho}_{\theta}=\inf\left\\{t\geq\theta:\bar{r}_{t}(Y_{t})>v_{t}\right\\}.$

We can now observe as illustrated in Figure 5 that the (forward) Rost stopping
time $\bar{\rho}$ can be represented as a delayed backward Root stopping time

$\tau_{\theta}:=\inf\left\\{t\geq\theta:r_{T-t}^{T}(Y_{t})>v_{t}\right\\},$

and that the (undelayed) backwards Rost stopping time

$\sigma:=\inf\left\\{t\geq 0:\bar{r}_{T-t}(X_{t})>u_{t}\right\\}$

can be represented as a (undelayed, forward) Root stopping time

$\rho:=\rho_{0}=\inf\left\\{t\geq 0:r_{t}^{T}(X_{t})>u_{t}\right\\},$

in sum

$\displaystyle\bar{\rho}_{\theta}:=\inf\left\\{t\geq\theta:\bar{r}_{t}(Y_{t})>v_{t}\right\\}$
$\displaystyle=\inf\left\\{t\geq\theta:r_{T-t}^{T}(Y_{t})>v_{t}\right\\}=:\tau_{\theta}$
(3.45) $\displaystyle\sigma:=\inf\left\\{t\geq
0:\bar{r}_{T-t}(X_{t})>u_{t}\right\\}$ $\displaystyle=\inf\left\\{t\geq
0:r_{t}^{T}(X_{t})>u_{t}\right\\}=:\rho.$ (3.46)

See also Figure 6 for an illustration of these stopping times.

(a) An illustration of the connection between $\bar{R}$ and $R_{T}$ in the
delayed regime for $\theta<T$.

(b) An illustration of the connection between $\bar{R}$ and $R_{T}$ in the
delayed regime for $\theta\geq T$.

Figure 6.

We see that Proposition 3.12 is valid for _any_ stopping times $\sigma$ and
$\tau$, hence also for the choices $\sigma=\rho_{0}$ and $\tau=\tau_{\theta}$.
However, in this case is was already observed in Section 3.2.2 that the
interpolation function $F_{\rho_{0},\tau_{\theta}}(s)$ will in general no
longer be constant when $\tau$ is subject to a non-zero delay $\theta$. Thus
we will no longer recover an equality in Equation (3.42) for a _delayed_
backward Root stopping time. Moreover the RHS of Equation (3.42) will in
general also not equal the RHS of Equation (3.13), thus cannot be applied to
prove our desired generalization of the delayed Rost optimal stopping
representation.

The following generalization of Proposition 3.12 is needed.

######  Proposition 3.13.

Let $\sigma\leq T$ be a stopping time for $X$ and let $\tau$ be a stopping
time for $Y$ such that $\mathbb{E}_{\nu}\left[|Y_{\tau}|\right]$. Then

  1. (i)

$\mathbb{E}_{\nu}\left[\left|x-Y_{\tau}\right|-\left|x-Y_{\tau\wedge
T}\right|\right]\leq\mathbb{E}^{x}_{\nu}\left[\left|X_{\sigma}-Y_{\tau}\right|-\left|X_{\sigma}-Y_{\tau\wedge(T-\sigma)}\right|\right].$
(3.47)

  2. (ii)

For any $Y$-stopping time $\theta$ such that $\theta\leq\tau$ we have

$\mathbb{E}_{\nu}\left[\left|x-Y_{\tau}\right|-\left|x-Y_{\tau\wedge
T}\right|\right]\leq\mathbb{E}^{x}_{\nu}\left[\left|X_{\sigma}-Y_{\tau}\right|-\left|X_{\sigma}-Y_{\theta\wedge(T-\sigma)}\right|\right].$
(3.48)

  3. (iii)

Furthermore, let $(r_{t}(x))_{(t,x)\in\mathbb{Z}\times\mathbb{Z}}$ denotes a
field of Root stopping probabilities, consider
$(s_{t}(x))_{(t,x)\in\mathbb{Z}\times\mathbb{Z}}\in\mathcal{R}_{r}$ and let
$\theta$ denote a delay stopping time for $Y$. Then there is equality in
(3.47) and (3.48) when considering the stopping times

$\displaystyle\sigma$ $\displaystyle=\inf\left\\{t\geq
0:r_{t}(X_{t})>u_{t}\right\\}\,\,\text{ and }$ $\displaystyle\tau$
$\displaystyle=\inf\left\\{t\geq\theta:s_{T-t}(Y_{t})>v_{t}\right\\}\wedge T.$

###### Proof.

As observed in the proof of [1, Proposition 3.7] we can conclude the following
with the help of Jensen’s inequality and optional sampling

$\mathbb{E}_{\nu}\left[\left|x-Y_{\tau}\right|-\left|x-Y_{\tau\wedge
T}\right|\right]\leq\mathbb{E}^{x}_{\nu}\left[\left|X_{\sigma}-Y_{\tau}\right|-\left|X_{\sigma\wedge(T-\tau\wedge
T)}-Y_{\tau\wedge T}\right|\right].$

It is also a straightforward application of the Core Argument (3.15) together
with optional sampling to obtain

$\displaystyle\mathbb{E}^{x}_{\nu}\left[\left|X_{\sigma\wedge(T-\tau\wedge
T)}-Y_{\tau\wedge
T}\right|\right]=\mathbb{E}^{x}_{\nu}\left[\left|X_{\sigma}-Y_{\tau\wedge(T-\sigma)}\right|\right]$

which concludes the proof of $(i)$.

Note that $(ii)$ easily follows from $(i)$ via Jensen’s inequality and
optional sampling by observing that when $\theta\leq\tau$ we clearly also have
$\theta\wedge(T-\sigma)\leq\tau\wedge(T-\sigma)$.

It now remains to show $(iii)$, the equality in the Root case. We will apply
Lemma 3.10 for the choices $\lambda=\delta_{x}$, $\rho=\sigma$ and $\eta=0$.
We will consider a decomposition into the events $\\{\tau<T\\}$ and
$\\{\tau\geq T\\}$. First note that on $\\{\tau<T\\}$ we have
$\eta\vee(T-\tau)=T-\tau$, hence by Lemma 3.10 we obtain

$\mathbb{E}^{x}_{\nu}\left[\left|X_{\sigma}-Y_{\tau}\right|\text{$11$}_{\tau<T}\right]=\mathbb{E}^{x}_{\nu}\left[\left|X_{\sigma\wedge(T-\tau)}-Y_{\tau}\right|\text{$11$}_{\tau<T}\right],$

thus

$\displaystyle\mathbb{E}_{\nu}\left[\left(\left|x-Y_{\tau}\right|-\left|x-Y_{\tau\wedge
T}\right|\right)\text{$11$}_{\tau<T}\right]=0$
$\displaystyle=\mathbb{E}^{x}_{\nu}\left[\left(\left|X_{\sigma}-Y_{\tau}\right|-\left|X_{\sigma\wedge(T-\tau)}-Y_{\tau}\right|\right)\text{$11$}_{\tau<T}\right]$
$\displaystyle=\mathbb{E}^{x}_{\nu}\left[\left(\left|X_{\sigma}-Y_{\tau}\right|-\left|X_{\sigma\wedge(T-\tau\wedge
T)}-Y_{\tau\wedge T}\right|\right)\text{$11$}_{\tau<T}\right].$

On the other hand, on $\\{\tau\geq T\\}$ we have $\eta\vee(T-\tau)=0$, hence
by Lemma 3.10

$\displaystyle\mathbb{E}^{x}_{\nu}\left[\left|X_{\sigma}-Y_{\tau}\right|\text{$11$}_{\tau\geq
T}\right]=\mathbb{E}^{x}_{\nu}\left[\left|X_{\sigma\wedge
0}-Y_{\tau}\right|\text{$11$}_{\tau\geq
T}\right]=\mathbb{E}^{x}_{\nu}\left[\left|X_{0}-Y_{\tau}\right|\text{$11$}_{\tau\geq
T}\right]=\mathbb{E}_{\nu}\left[\left|x-Y_{\tau}\right|\text{$11$}_{\tau\geq
T}\right]$

which gives

$\displaystyle\mathbb{E}_{\nu}\left[\left(\left|x-Y_{\tau}\right|-\left|x-Y_{\tau\wedge
T}\right|\right)\text{$11$}_{\tau\geq T}\right]$
$\displaystyle=\mathbb{E}^{x}_{\nu}\left[\left(\left|X_{\sigma}-Y_{\tau}\right|-\left|X_{0}-Y_{\tau\wedge
T}\right|\right)\text{$11$}_{\tau\geq T}\right]$
$\displaystyle=\mathbb{E}^{x}_{\nu}\left[\left(\left|X_{\sigma}-Y_{\tau}\right|-\left|X_{\sigma\wedge(T-\tau\wedge
T)}-Y_{\tau\wedge T}\right|\right)\text{$11$}_{\tau\geq T}\right].$

Altogether equality in (3.47) follows. Note that $\eta=0$ was essential here
in order to gain this equality.

It now remains to establish equality in (3.48), that is we need to show

$\displaystyle\mathbb{E}^{x}_{\nu}\left[\left|X_{\sigma}-Y_{\tau\wedge(T-\sigma)}\right|\right]=\mathbb{E}^{x}_{\nu}\left[\left|X_{\sigma}-Y_{\theta\wedge(T-\sigma)}\right|\right].$

On the one hand we trivially have

$\displaystyle\mathbb{E}^{x}_{\nu}\left[\left|X_{\sigma}-Y_{\tau\wedge(T-\sigma)}\right|\text{$11$}_{\sigma=T}\right]=\mathbb{E}^{x}_{\nu}\left[\left|X_{\sigma}-Y_{0}\right|\text{$11$}_{\sigma=T}\right]=\mathbb{E}^{x}_{\nu}\left[\left|X_{\sigma}-Y_{\theta\wedge(T-\sigma)}\right|\text{$11$}_{\sigma=T}\right],$

whereas

$\displaystyle\mathbb{E}^{x}_{\nu}\left[\left|X_{\sigma}-Y_{\tau\wedge(T-\sigma)}\right|\text{$11$}_{\sigma<T}\right]=\mathbb{E}^{x}_{\nu}\left[\left|X_{\sigma}-Y_{\theta\wedge(T-\sigma)}\right|\text{$11$}_{\sigma<T}\right]$

can be argued verbatim as in Lemma 3.10, switching the roles of the two
stopping times therein. ∎

######  Remark 3.14.

Note that Proposition 3.12 can easily be recovered from Proposition 3.13
$(ii)$ via the choices $\nu=\delta_{y}$ and $\theta=0$.

Equipped with this proposition and the (delayed) Root-Rost symmetries (3.45)
and (3.46) we can now give a proof of Theorem 3.6, the optimal stopping
representation of Rost solutions to (dSEP)

###### Proof of Theorem 3.6.

We want to apply Proposition 3.13. Consider $\tau=\tau_{\theta}$ and note that
for the LHS of (3.47) respectively (3.48) with the help of the Root-Rost
symmetry (3.45) we have

$\displaystyle\mathbb{E}_{\nu}\left[\left|x-Y_{\tau}\right|-\left|x-Y_{\tau\wedge
T}\right|\right]=U_{\beta^{\alpha}}(x)-U_{\beta^{\alpha}_{T}}(x).$

Furthermore for any $X$-stopping time $\sigma$ we have

$\displaystyle\mathbb{E}^{x}_{\nu}\left[\left|X_{\sigma}-Y_{\tau}\right|-\left|X_{\sigma}-Y_{\theta\wedge(T-\sigma)}\right|\right]=\mathbb{E}^{x}\left[U_{\beta^{\alpha}}(X_{\sigma})-V^{\alpha}_{T-\sigma}(X_{\sigma})\right].$
(3.49)

It now becomes obvious that Equation (3.13) follows by Proposition 3.13
$(iii)$ by considering $\sigma=\sigma^{*}$ and the Root-Rost symmetry (3.46),
while Equation (3.14) follows from Proposition 3.13 $(ii)$ considering general
$X$\- stopping times $\sigma\leq T$. ∎

##  4\. Recovering the Continuous Optimal Stopping Representation as a Limit
of the Discrete Optimal Stopping Representation

The aim of this section is to recover Theorem 2.7 (resp. Theorem 2.8) from its
discrete counterpart, Theorem 3.5 (resp. Theorem 3.6) through taking limits of
appropriately scaled SSRWs.

This passage to continuous time essentially relies on the application of
Donsker-type results, similar to the limiting procedure carried out in [1,
Section 5] which in turn heavily built on arguments established in [13]. For
this purpose it is important to point out that the results and arguments
presented in Section 3 remain invariant under appropriate scaling of the
space-time grid.

In Section 4.1 we recall the appropriate space-time grid and an associated
discretization of a Brownian motion into a scaled SSRW as proposed in [13]. We
proceed to introducing a discretization of a continuous (dSEP) to a scaled
discrete delayed problem in Section 4.2 and furthermore explain how our
results of Section 3 apply in this case.

It is subject of Section 4.3 to recover continuous Root and Rost solutions to
(dSEP) as limits of solutions to a appropriately scaled and discretized
(dSEP). This will give us convergence of the LHS of 3.11 to the LHS of 2.3
(resp. convergence of the LHS of 3.13 to the LHS of 2.5).

In Section 4.4 these limiting results are furthermore applied to the recovery
of the optimal stopping problem and its value, namely establishing
convergences of the RHS of 3.11 to the LHS of 3.11 as well as 3.12 to 3.12
(analogously for Rost).

###  4.1. Discretization of a Brownian motion and its stopping times

We begin by recalling the discretization of a Brownian motion $(W_{t})_{t\geq
0}$ into a scaled SSRW as proposed in [13]. For a given $N\in\mathbb{N}$
consider a discrete set of spatial points
$\mathcal{X}^{N}:=\\{x^{N}_{1},\dots,x^{N}_{L^{N}}\\}$ such that

  * $|x^{N}_{k+1}-x^{N}_{k}|=\frac{1}{\sqrt{N}}$ for $j=1,\dots,L^{N}-1$.

  * $L^{N}\sim\sqrt{N}$.

We define a random walk $(Y^{N}_{k})_{k\in\mathbb{N}}$ in the following way.
Let $Y^{N}_{k}:=W_{\tau^{N}_{k}}$ where the $\tau^{N}_{k}$ are given as those
times when a Brownian Motion hits a new grid point in $\mathcal{X}^{N}$. More
precisely, let $(W_{t})_{t\geq 0}$ be a Brownian motion started in
$W_{0}\sim\lambda$. Then we define

  * $\tau^{N}_{0}=\inf\\{t\geq 0:W_{t}\in\mathcal{X}^{N}\\}$, and

  * given $W_{\tau^{N}_{k}}=x^{N}_{j}$ we define $\tau^{N}_{k+1}:=\inf\\{t\geq\tau^{N}_{k}:W_{t}\in\\{x^{N}_{j-1},x^{N}_{j+1}\\}\\}$.

Note, this definition implies that the random walk
$(Y^{N}_{k})_{k\in\mathbb{N}}$ is started according to a discretization
$\lambda^{N}$ of the starting law $\lambda$ given by

$\lambda^{N}:=\mathcal{L}(Y^{N}_{0})=\mathcal{L}^{\lambda}(W_{\tau^{N}_{0}}).$

Now let $\tau$ be a stopping time for the Brownian Motion $W_{t}$. Then we can
define a stopping rule $\tilde{\sigma}^{N}$ for the discretized process
$Y^{N}_{k}$ via

$\tilde{\sigma}^{N}:=\inf\\{t\in\mathbb{N}:\tau^{N}_{t-1}<\tau\leq\tau^{N}_{t}\\}.$

For such a discretized stopping time we have the following convergence
results.

######  Lemma 4.1 (Cf.[13, Lemma 5.2]).

Let $\tilde{\sigma}^{N}$ be the discretization of a stopping time $\tau$ of a
Brownian motion $W_{t}$ as defined above. Then

$\displaystyle Y^{N}_{\tilde{\sigma}^{N}}$ $\displaystyle\rightarrow
W_{\tau}\quad$ almost surely, and (4.1)
$\displaystyle\frac{\tilde{\sigma}^{N}}{N}$
$\displaystyle\rightarrow\tau\quad$ $\displaystyle\text{in probability, as
}N\rightarrow\infty.$ (4.2)

In particular, this implies that for
$\mu^{N}:=\mathcal{L}(Y^{N}_{\tilde{\sigma}^{N}})$ and for
$\mu:=\mathcal{L}^{\lambda}(W_{\tau})$ we have that $\mu^{N}\rightarrow\mu$.
Moreover, for every $T\geq 0$ we have

$\displaystyle Y^{N}_{\tilde{\sigma}^{N}\wedge NT}$ $\displaystyle\rightarrow
W_{\tau\wedge T}\quad$ almost surely, and
$\displaystyle\frac{\tilde{\sigma}^{N}\wedge NT}{N}$
$\displaystyle\rightarrow\tau\wedge T\quad$ $\displaystyle\text{in
probability, as }N\rightarrow\infty.$

Note that while in [13] this lemma was stated for stopping times $\tau$ that
are optimizers of a given (OptSEP), this characterization is not essential to
the proof given, thus we state the lemma in more generality. Given the
convergence of $\frac{\tilde{\sigma}^{N}}{N}\rightarrow\tau$ in probability,
the convergence of $\frac{\tilde{\sigma}^{N}\wedge NT}{N}\rightarrow\tau\wedge
T$ in probability is clear. Regarding the convergence of the processes, it is
important to observe that by construction of the discretization we have
$\tau^{N}_{NT}\rightarrow T$ a.s. by the strong law of large numbers. Note
furthermore that $Y^{N}_{\tilde{\sigma}^{N}\wedge
NT}=W_{\tau^{N}_{\tilde{\sigma}^{N}}\wedge\tau^{N}_{NT}}$, hence the almost
sure convergence $Y^{N}_{\tilde{\sigma}^{N}\wedge NT}\rightarrow W_{\tau\wedge
T}$ is clear.

###  4.2. A Suitable Discretization of Root and Rost solutions to (dSEP)

Consider a continuous (dSEP) given by the triple $(\lambda,\eta,\mu)$. Theorem
2.2 (resp. Theorem 2.4) gives us existence of a Root (resp. Rost) barrier $R$
in $[0,\infty)\times\mathbb{R}$ such that

$\rho=\rho_{R}:=\inf\\{t\geq\eta:(t,W_{t})\in R\\}$

is a stopping time embedding the given measure $\mu$. We propose the following
discretization $(\lambda^{N},\tilde{\eta}^{N},\mu^{N})$ of
$(\lambda,\eta,\mu)$.

$\displaystyle\lambda^{N}$ $\displaystyle:=\mathcal{L}(Y^{N}_{0}),$
$\displaystyle\tilde{\eta}^{N}$
$\displaystyle:=\inf\\{t\in\mathbb{N}:\tau_{t-1}^{N}<\eta\leq\tau_{t}^{N}\\}\,\,\text{
and }$ $\displaystyle\mu^{N}$
$\displaystyle:=\mathcal{L}^{\lambda^{N}}(Y^{N}_{\tilde{\sigma}^{N}})\,\,\text{
where }$ $\displaystyle\tilde{\sigma}^{N}$
$\displaystyle:=\inf\\{t\in\mathbb{N}:\tau_{t-1}^{N}<\rho\leq\tau_{t}^{N}\\}.$

(Note that since $\rho\geq\eta$, it is clear that we also have
$\tilde{\sigma}^{N}\geq\tilde{\eta}^{N}$.) If the measure $\mu$ is supported
also beyond the grid $\mathcal{X}^{N}$ given at the discretization step $N$ we
make the boundaries of the grid, $x^{N}_{1}$ resp. $x^{N}_{L^{N}}$ absorbing
barriers for the Brownian motion to ensure that the random walk only moves on
the given grid.

The following convergences are now clear by the definitions in Section 4.1 and
Lemma 4.1

$\displaystyle\lambda^{N}$ $\displaystyle\Rightarrow\lambda$
$\displaystyle\eta^{(N)}:=\frac{\tilde{\eta}^{N}}{N}$
$\displaystyle\xrightarrow{p}\eta$ $\displaystyle\mu^{N}$
$\displaystyle\Rightarrow\mu.$

Moreover, it is important to observe that the conditions
$\lambda^{N}\leq_{c}\mathcal{L}^{\lambda^{N}}\left(Y^{N}_{\tilde{\eta}^{N}}\right)\leq_{c}\mu^{N}$
and $\mathbb{E}\left[\tilde{\eta}^{N}\right]<\infty$ are satisfied. Therefore,
by Theorem 3.3 (resp. Theorem 3.4) and rescaling there exists a field of Root
(resp. Rost) stopping probabilities
$(r^{N}_{t}(x))_{(t,x)\in\mathbb{N}\times\mathcal{X}^{N}}$ where
$\mathcal{X}^{N}\subseteq\frac{1}{\sqrt{N}}\mathbb{Z}$ such that

$\tilde{\rho}^{N}:=\inf\left\\{t\geq\tilde{\eta}^{N}:r^{N}_{t}(Y^{N}_{t})>u_{t}\right\\}$

defines a discrete Root (resp. Rost) stopping time embedding the measure
$\mu^{N}$ into the SSRW $Y^{N}$, solving the discrete (and rescaled) (dSEP)
given by $(\lambda^{N},\tilde{\eta}^{N},\mu^{N})$.

By $\left(W_{t}^{(N)}\right)_{t\geq 0}$ we denote the rescaled continuous
version of the random walk $Y^{N}$ defined via

$W_{t}^{(N)}:=Y_{\lfloor Nt\rfloor}^{N}+\left(Nt-\lfloor
Nt\rfloor\right)\left(Y_{\lfloor Nt\rfloor+1}^{N}-Y_{\lfloor
Nt\rfloor}^{N}\right).$

Note that we have
$\left(\frac{\tilde{\eta}^{N}}{N},Y^{N}_{\tilde{\eta}^{N}}\right)=\left(\eta^{(N)},W_{\eta^{(N)}}^{(N)}\right)$
almost surely.

We now want to define Root and Rost stopping times for
$\left(W_{t}^{(N)}\right)_{t\geq 0}$. By definition of the discretization we
have $W^{(N)}_{t}\in\mathcal{X}^{N}$ if and only if $Nt\in\mathbb{N}$. Hence
we can extend a Root field of stopping probabilities
$(r^{N}_{t}(x))_{(t,x)\in\mathbb{N}\times\mathcal{X}^{N}}$ to
$[0,\infty)\times\mathbb{R}$ by setting

$r^{N}_{t}(x):=\begin{cases}r^{N}_{\lfloor t\rfloor}(x)&\text{ for
}x\in\mathcal{X}^{N},\\\ 0&\text{ for all }t\text{ when
}x\in\mathbb{R}\setminus\mathcal{X}^{N}.\end{cases}$

Then we define

$\rho^{(N)}:=\inf\left\\{t\geq\eta^{(N)}:r^{N}_{\lfloor
Nt\rfloor}\left(W^{(N)}_{t}\right)>u_{\lfloor Nt\rfloor}\right\\}$ (4.3)

in order to have

$\left(\tilde{\rho}^{N},Y^{N}_{\tilde{\rho}^{N}}\right)=\left(\rho^{(N)},W^{(N)}_{\rho^{(N)}}\right)\,\text{
almost surely}.$

Furthermore $(r^{N}_{t}(x))_{(t,x)\in\mathbb{N}\times\mathcal{X}^{N}}$ induce
a Root barrier
$\tilde{R}^{N}\subseteq\mathbb{N}\times\frac{1}{\sqrt{N}}\mathbb{Z}$ via

$\tilde{R}^{N}:=\left\\{(t,x):r^{N}_{t}(x)>0\right\\},$

and a corresponding Root barrier in $[0,\infty)\times\mathbb{R}$ can be
defined in the following way

$R^{(N)}:=\left\\{(t,x)\in[0,\infty)\times\mathbb{R}:\left(\lfloor
Nt\rfloor,x\right)\in\tilde{R}^{N}\right\\}.$ (4.4)

We will sometimes use the notation $\tilde{R}^{N}=:\tilde{R}^{N}_{+}$ (resp.
$R^{(N)}=:R^{(N)}_{+}$) and analogously define $\tilde{R}^{N}_{-}$ (resp.
$R^{(N)}_{-}$) via

$\tilde{R}^{N}_{-}:=\left\\{(t,x):r^{N}_{t}(x)=1\right\\}.$

Note that $\tilde{R}^{N}_{-}\subseteq\tilde{R}^{N}_{+}$ and
$R^{(N)}_{-}\subseteq R^{(N)}_{+}$. We make the same definitions for Rost
fields of stopping probabilities replacing the floor function by a ceiling
function.

###  4.3. Taking Limits

The main objective of this section is to show the following convergence of the
discrete time objects defined above to their continuous conterparts. This will
be carried out individually for Root and Rost respectively.

We follow [34] for the definition of a metric on the space of barriers. Let
$\mathscr{R}$ denote the space of all Root and Rost barriers in
$[0,\infty]\times[-\infty,\infty]$. Then a complete metric on this space can
be defined in the following way. Consider the map
$f:[0,\infty]\times[-\infty,\infty]\rightarrow[0,1]\times[-1,1]$,
$f(t,x):=\left(\frac{t}{1+t},\frac{x}{1+|x|}\right)$. Let $d$ denote the
ordinary Euclidean metric on $\mathbb{R}$. Then for two barriers
$R,S\subseteq[0,\infty]\times[-\infty,\infty]$ _Root’s metric_ $d_{R}$ on the
space of all barriers $\mathscr{R}$ is defined as follows

$d_{R}(R,S):=\max\left\\{\sup_{(t,x)\in
R}d\left(f(t,x),f(S)\right),\sup_{(s,y)\in
S}d\left(f(R),f(s,y)\right)\right\\}.$

####  4.3.1. A Limit of Root Stopping Times

######  Lemma 4.2.

Let $\left(\rho^{(N)}\right)_{n\in\mathbb{N}}$ be a sequence of discrete Root
stopping times as defined in (4.3). Then there exists a Root barrier
$R\subseteq[0,\infty)\times\mathbb{R}$ such that we have the following
convergence

$\left(\rho^{(N)},W^{(N)}_{\rho^{(N)}}\right)\xrightarrow{d}\left(\rho,W_{\rho}\right)$
(4.5)

where

$\rho:=\inf\left\\{t\geq\eta:(t,W_{t})\in R\right\\}.$

###### Proof.

The Root barriers $(R^{(N)})_{N\in\mathbb{N}}$ converge (possibly along a
subsequence) to a Root barrier $R$ in Root’s metric, details can be found in
[34].

We define the following auxiliary hitting time

$\displaystyle\rho^{N}$ $\displaystyle:=\inf\left\\{t\geq\eta:(t,W_{t})\in
R^{(N)}\right\\}$

and show convergence in two steps.

  1. (i)

We have $\rho^{N}\xrightarrow{p}\rho$. This is basically a consequence of a
delayed version of Root’s original convergence lemma, [34, Lemma 2.4], which
we provide in Lemma 4.3.

  2. (ii)

We furthermore have

$\left|\left(\rho^{(N)},W^{(N)}_{\rho^{(N)}}\right)-\left(\rho^{N},W_{\rho^{N}}\right)\right|\xrightarrow{p}0,$

which is a delayed version of [13, Lemma 5.6] which we give in Lemma 4.5.

∎

We formulate a delayed version of Root’s convergence lemma, [34, Lemma 2.4]

######  Lemma 4.3.

Let $\eta$ be a delay stopping time and $R$ be a Root barrier such that for
the corresponding delayed hitting time

$\tau=\inf\left\\{t\geq\eta:(t,W_{t})\in R\right\\}$

we have $\mathbb{E}[\tau]<\infty$.

Then for any $\varepsilon>0$ there exist $\delta,\tilde{\delta}>0$ such that
if for another Root barrier $\bar{R}$ we have $d_{R}(R,\bar{R})<\delta$ and
for another delay stopping time $\bar{\eta}$ we have
$\mathbb{P}[|\eta-\bar{\eta}|>\tilde{\delta}]<\tilde{\delta}$, then for the
corresponding delayed hitting time $\bar{\tau}$ defined as

$\bar{\tau}=\inf\left\\{t\geq\bar{\eta}:(t,W_{t})\in\bar{R}\right\\},$

it holds that

$\mathbb{P}[\bar{\tau}>\tau+\varepsilon]<\varepsilon.$

###### Proof.

Similar to [34] we make the following choices for $\varepsilon>0$.

  * Choose $\tilde{\varepsilon}>0$ such that $\tilde{\varepsilon}<\frac{\varepsilon}{4}$ and

$\mathbb{P}\left[\sup_{\tilde{\varepsilon}<t<\varepsilon}W_{t}>\tilde{\varepsilon}\text{
and
}\inf_{\tilde{\varepsilon}<t<\varepsilon}W_{t}<-\tilde{\varepsilon}\right]>1-\frac{\varepsilon}{4}.$

  * Choose $T>\frac{3\mathbb{E}[\tau]}{\varepsilon}$, then $\mathbb{P}[\tau\geq T]<\frac{\varepsilon}{4}$ (due to Markov’s inequality).

  * Choose $M$ and $\delta>0$ such that if $(t,x)\in R$, $t\leq T$, $|x|\leq M$ and $d_{R}(R,\bar{R})<\delta$, then $d((t,x),\bar{R})\leq\tilde{\varepsilon}$.

  * Choose $\tilde{\delta}=\tilde{\varepsilon}$, then $\mathbb{P}[|\eta-\bar{\eta}|>\tilde{\varepsilon}]<\tilde{\varepsilon}$.

Then we consider the set

$\displaystyle A:=\\{\omega\in\Omega:(i)$
$\displaystyle\sup_{\tau(\omega)+\tilde{\varepsilon}<t<\tau(\omega)+\varepsilon}(W_{t}(\omega)-W_{\tau}(\omega))>\tilde{\varepsilon}\text{
and }$
$\displaystyle\quad\inf_{\tau(\omega)+\tilde{\varepsilon}<t<\tau(\omega)+\varepsilon}(W_{t}(\omega)-W_{\tau}(\omega))<-\tilde{\varepsilon},$
$\displaystyle(ii)$ $\displaystyle\;\;\tau(\omega)<T,$ $\displaystyle(iii)$
$\displaystyle\;\;|W_{\tau}(\omega)|<M,$ $\displaystyle(vi)$
$\displaystyle\;\;\tilde{\eta}<\eta+\tilde{\varepsilon}.\\}$

We then see from the definitions made above that for $\omega\in A$ follows
$\bar{\tau}(\omega)<\tau(\omega)+\varepsilon$. Moreover, these choices and the
strong Markov property give us $\mathbb{P}[A]>1-\varepsilon$. ∎

In order to complete step (ii) in the proof of Lemma 4.2, we need to provide
the following auxiliary convergence result, which is basically a delayed
version of [13, Lemma 5.7].

######  Lemma 4.4.

Consider the stopping times

$\displaystyle\rho^{(M,N)}$
$\displaystyle:=\inf\left\\{t\geq\eta^{(N)}:\left(t,W^{(N)}_{t}\right)\in
R^{(M)}\right\\},$ $\displaystyle\rho^{M}$
$\displaystyle:=\inf\left\\{t\geq\eta:\left(t,W_{t}\right)\in
R^{(M)}\right\\},$

where $\eta^{(N)}\rightarrow\eta$ in probability. Then we have the following
convergence

$\left(W^{(N)}_{\rho^{(M,N)}},\rho^{(M,N)}\right)\xrightarrow[N\rightarrow\infty]{d}\left(W_{\rho^{M}},\rho^{M}\right).$
(4.6)

###### Proof.

We aim to apply Donsker’s theorem to the continuous scaled symmetric random
walk $\left(W_{t}^{(N)}\right)_{t\in\left[\eta^{(N)},T\right]}$. Let
$\left(B_{t}\right)_{t\in\left[\eta,T\right]}$ denote a Brownian motion, then
for each $\omega\in\Omega$ we have
$\left(W_{t}^{(N)}\right)_{t\in\left[\eta^{(N)},T\right]},\left(B_{t}\right)_{t\in\left[\eta,T\right]}\in\mathcal{D}_{T}$
where $\mathcal{D}_{T}:=\bigcup_{a\leq T}C([a,T])$.

We define an appropriate metric on $\mathcal{D}_{T}$. More generally, consider
the function space $\mathcal{D}:=\bigcup_{a\leq b}C([a,b])$. Thus for each
$f\in\mathcal{D}$ there exist $l_{f},r_{f}\in\mathbb{R}$, $l_{f}\leq r_{f}$
such that $f\in C([l_{f},r_{f}])$. For $f\in\mathcal{D}$ and $t\geq 0$ we
consider $\overline{f}(t):=f(l_{f}\vee(t\wedge r_{f}))\in C([0,\infty))$ and
define the following distance on $\mathcal{D}$.

$\displaystyle d_{\mathcal{D}}(f,g)$
$\displaystyle:=\left(\sup_{t\in[0,\infty)}|\overline{f}(t)-\overline{g}(t)|\right)\vee|l_{f}-l_{g}|\vee|r_{f}-r_{g}|.$

Considering this, metric we can apply Donsker’s theorem to get

$\left(W_{t}^{(N)}\right)_{t\in\left[\eta^{(N)},T\right]}\Rightarrow\left(B_{t}\right)_{t\in\left[\eta,T\right]}$

and we are able to use the Portmanteau Theorem in the following way

$\displaystyle\lim_{N\rightarrow\infty}\mathbb{P}\left[\left(W_{t}^{(N)}\right)_{t\in\left[\eta^{(N)},T\right]}\in\mathcal{K}\right]=\mathbb{P}\left[\left(B_{t}\right)_{t\in\left[\eta,T\right]}\in\mathcal{K}\right]$
$\displaystyle\quad\text{ for all }\mathcal{K}\subseteq\mathcal{D}\text{
Borel}\text{ with
}\mathbb{P}^{\lambda}\left[\left(B_{t}\right)_{t\in\left[\eta,T\right]}\in\partial\mathcal{K}\right]=0.$

It is now left to consider cleverly chosen sets
$\mathcal{K}\in\mathcal{B}(\mathcal{D})$ to support our convergence claim
(4.6). For $M$ fixed consider $W^{(N)}_{\rho^{(M,N)}}$ and $B_{\rho^{M}}$ as
well as the spatial grid $\mathcal{X}:=\\{x^{M}_{1},\dots,x^{M}_{L^{M}}\\}$.

Choose an arbitrary point $x_{i}^{M}\in\mathcal{X}$, $t\in(0,T]$ such that
$(t,x_{i}^{M})$ lies somewhere in the interior of $R^{(M)}$ and some
$\gamma<\left(t-\inf\left\\{s:\left(s,x_{i}^{M}\right)\in
R^{(M)}\right\\}\right)\wedge(T-t)$ to consider the set

$\bar{R}(\gamma):=[t-\gamma,t+\gamma]\times\left\\{x_{i}^{M}\right\\}\subseteq
R^{(M)}.$

Since the barrier $R^{(M)}$ will be a subset of $[0,\infty)\times\mathcal{X}$
we can identify a smallest $z\in\mathcal{X}$ such that $z>x_{i}^{M}$ and
$\left([t-\gamma,t+\gamma]\times\\{z\\}\right)\subseteq R^{(M)}$. Analogously,
we identify a largest $y\in\mathcal{X}$, $y<x_{i}^{M}$.

Moreover, let $y<w_{1}<\cdots<w_{n}<z$,
$w_{i}\in\mathcal{X}\setminus\left\\{x^{M}_{i}\right\\}$ denote all those
points at which a piece of the barrier $R^{(M)}$ sticks into our area of
interest, precisely $\left([t-\gamma,t+\gamma]\times\\{w_{i}\\}\right)\cap
R^{(M)}\neq\emptyset$. It is clear that there can only be finitely may such
points. Consider
$\bar{R}_{w_{i}}:=\left([t-\gamma,t+\gamma]\times\left\\{w_{i}\right\\}\right)\cap
R^{(M)}$ for $i=1,\dots,n$.

We proceed to define the following subsets of $\mathcal{D}_{T}$.

$\displaystyle\hat{\mathcal{K}}$
$\displaystyle:=\bigcup_{\begin{subarray}{c}\hat{\gamma}>0\\\
\hat{\gamma}\in\mathbb{Q}\end{subarray}}\left\\{f\in\mathcal{D}_{T}:\|(s,f(s))-R^{(M)}\|>\hat{\gamma}\,\,\forall\,s\in[l_{f},(t-\gamma)\vee
l_{f}]\right\\}$ $\displaystyle\hat{\mathcal{K}}^{w}$
$\displaystyle:=\bigcap_{i=1,\dots,n}\bigcup_{\begin{subarray}{c}\hat{\gamma}>0\\\
\hat{\gamma}\in\mathbb{Q}\end{subarray}}\left\\{f\in\mathcal{D}_{T}:\|(s,f(s))-\bar{R}_{w_{i}}\|>\hat{\gamma}\,\,\forall\,s\in[(t-\gamma)\vee
l_{f},t+\gamma]\right\\}$ $\displaystyle\hat{\mathcal{K}}_{z}$
$\displaystyle:=\\{f\in\hat{\mathcal{K}}\cap\hat{\mathcal{K}}^{w}:f((t-\gamma)\vee
l_{f})\in(x_{i}^{M},z)\\}$ $\displaystyle\mathcal{K}^{\varepsilon}_{q}$
$\displaystyle:=\\{f\in\mathcal{D}_{T}:f(s)<z-\varepsilon\,\,\forall\,s\in[(t-\gamma)\vee
l_{f},q]\cap\mathbb{Q}\\}$ $\displaystyle\mathcal{K}^{\varepsilon,\delta}_{q}$
$\displaystyle:=\\{f\in\mathcal{D}_{T}:f(q)<x_{i}^{M}-\delta\\}\cap\mathcal{K}^{\varepsilon}_{q}$
$\displaystyle\mathcal{K}^{\varepsilon,\delta}$
$\displaystyle:=\bigcup_{\begin{subarray}{c}q\in[t-\gamma,t+\gamma]\\\
q\in\mathbb{Q}\end{subarray}}\mathcal{K}^{\varepsilon,\delta}_{q}$
$\displaystyle\mathcal{K}^{z}$
$\displaystyle:=\bigcap_{\begin{subarray}{c}\delta>0\\\
\delta\in\mathbb{Q}\end{subarray}}\bigcup_{\begin{subarray}{c}\varepsilon>0\\\
\varepsilon\in\mathbb{Q}\end{subarray}}\mathcal{K}^{\varepsilon,\delta}\cap\hat{\mathcal{K}}_{z}$

Then

  * $\hat{\mathcal{K}}$

is the set of all paths which stay away from the barrier $R^{(M)}$ at any time
point before $(t-\gamma)\vee l_{f}$. Since $R^{(M)}$ is a finite barrier,
$\hat{\mathcal{K}}$ is a Borel set.

  * $\hat{\mathcal{K}}^{w}$

is the set of all paths which stay away from the barrier pieces
$\bar{R}_{w_{1}},\dots,\bar{R}_{w_{n}}$ before time $t+\gamma$.

  * $\hat{\mathcal{K}}_{z}$

is the set of all paths in $\hat{\mathcal{K}}\cap\hat{\mathcal{K}}^{w}$ that
are between $x_{i}^{M}$ and $z$ at time $(t-\gamma)\vee l_{f}$.

  * $\mathcal{K}^{\varepsilon}_{q}$

is the set of all paths that stay below $z-\varepsilon$ after time
$(t-\gamma)\vee l_{f}$ and before time $q$.

  * $\mathcal{K}^{\varepsilon,\delta}_{q}$

is the set of all paths that are below $x_{i}^{M}-\delta$ at time $q$ and stay
below $z-\varepsilon$ after time $(t-\gamma)\vee l_{f}$ and before time $q$.

  * $\mathcal{K}^{\varepsilon,\delta}$

is the set of all paths that such that there exist a
$q\in[t-\gamma,t+\gamma]\cap\mathbb{Q}$ fulfilling the properties of set
$\mathcal{K}^{\varepsilon,\delta}_{q}$.

  * $\mathcal{K}^{z}$

is the set of all paths such that for all $\delta>0$ there exists an
$\varepsilon>0$ such that the properties of set
$\mathcal{K}^{\varepsilon,\delta}$ are fulfilled.

Analogously, we define $\mathcal{K}^{y}$ with the opposite inequalities.

Note that $\mathcal{K}^{z}$ will be a Borel set consisting of all those paths
that start somewhere away from the barrier $R^{(M)}$ but hit the barrier for
the first time in $\bar{R}(\gamma)$ coming from above, while $\mathcal{K}^{y}$
will be a Borel set of those paths that hit the barrier $R^{(M)}$ for the
first time in $\bar{R}(\gamma)$ coming from below. Altogether,
$\mathcal{K}:=\mathcal{K}^{y}\cup\mathcal{K}^{z}$ will be a Borel set
consisting of exactly those paths that hit the barrier $R^{(M)}$ for the first
time in $\bar{R}(\gamma)$ after starting in some initial time $l_{f}$ away
from the barrier $R^{(M)}$.

We need to identify $\partial\mathcal{K}$ and to argue that
$\mathbb{P}^{\lambda}\left[\left(B_{t}\right)_{t\in\left[\eta,T\right]}\in\partial\mathcal{K}\right]=0$.
The set $\partial\mathcal{K}$ will consist of exactly those paths that start
somewhere away from the boundary and either

  * hit $\bar{R}(\gamma)$ exactly at time $t\pm\gamma$, or

  * hit $\bar{R}(\gamma)$ elsewhere, but also _touch_ the barrier $R^{(M)}$ before, without passing _through_ the barrier.

  * are born somewhere inside the barrier $R^{(M)}$ but immediately leave it without ever touching the barrier again.

  * are born somewhere inside the barrier and remain flat.

By standard properties of a Brownian motion it is clear that these events must
have zero probability.

With appropriate choices of $x_{i}^{N},t$ and $\gamma$ it now becomes clear
that we can cover the whole barrier $R^{(M)}$ with such sets
$\bar{R}(\gamma)$.

We are left to consider the possibility of _appearing_ exactly _on_ the
barrier. As a combination of the convergence of $\eta^{N}$ to $\eta$ and
Donsker’s theorem gives (should give?)

$\left(\eta^{(N)},W^{(N)}_{\eta^{(N)}}\right)\xrightarrow[N\rightarrow\infty]{d}\left(\eta,B_{\eta}\right).$

Now note that similarly to the arguments given in the proof of Lemma 4.3, a
Brownian motion that is very close to a Root barrier will proceed to hit this
barrier almost immediately. It is then a consequence of this regularity of
Root barriers which gives us

$\mathbb{P}^{\lambda^{N}}\left[\left(\eta^{(N)},W^{(N)}_{\eta^{(N)}}\right)\in
R^{(M)}\right]\xrightarrow[N\rightarrow\infty]{}\mathbb{P}^{\lambda}\left[\left(\eta,B_{\eta}\right)\in
R^{(M)}\right],$

concluding the proof of the convergence (4.6). ∎

We are now ready to finish step (ii) in the proof of Lemma 4.2.

######  Lemma 4.5 (Cf.[13, Lemma 5.6]).

We have the following convergence

$\left|\left(\rho^{(N)},W^{(N)}_{\rho^{(N)}}\right)-\left(\rho^{N},W_{\rho^{N}}\right)\right|\xrightarrow{p}0\text{
for }N\rightarrow\infty.$

###### Proof.

Define the following hitting times for the scaled continuous random walk
$W^{(N)}$

$\displaystyle\tau^{(M,N)}$
$\displaystyle:=\inf\left\\{t\geq\eta^{(N)}:\left(t,W^{(N)}_{t}\right)\in
R^{(M)}\right\\},\,\,\text{ and }$ $\displaystyle\tau^{(N)}$
$\displaystyle:=\inf\left\\{t\geq\eta^{(N)}:\left(t,W^{(N)}_{t}\right)\in
R^{(N)}\right\\}.$

Then analogous to the proof of [13, Lemma 5.6], but replacing Root’s original
convergence lemma with its delayed version Lemma 4.3, we can deduce the
convergence

$\left|\left(\tau^{(M,N)},W^{(N)}_{\tau^{(M,N)}}\right)-\left(\tau^{(N)},W^{(N)}_{\tau^{(N)}}\right)\right|\xrightarrow[M,N\rightarrow\infty]{p}0.$

It is a consequence of Lemma 4.4 that

$\left(\tau^{(M,N)},W^{(N)}_{\tau^{(M,N)}}\right)\xrightarrow[N\rightarrow\infty]{d}\left(\rho^{M},W_{\rho^{M}}\right).$

Thus it remains to show that

$\left|\left(\rho^{(N)},W^{(N)}_{\rho^{(N)}}\right)-\left(\tau^{(N)},W^{(N)}_{\tau^{(N)}}\right)\right|\xrightarrow[N\rightarrow\infty]{p}0.$
(4.7)

For this purpose recall the Root barriers $R^{(N)}_{+}$ and $R^{(N)}_{-}$
defined above and consider

$\displaystyle\tau^{(N)}_{+}$
$\displaystyle:=\inf\left\\{t\geq\eta:\left(t,W^{(N)}_{t}\right)\in
R^{(N)}_{+}\right\\}=\tau^{(N)},$ $\displaystyle\tau^{(N)}_{-}$
$\displaystyle:=\inf\left\\{t\geq\eta:\left(t,W^{(N)}_{t}\right)\in
R^{(N)}_{-}\right\\}.$

Note that by Root’s barrier structure and the definition of the discretization
we have

$d_{R}\left(R^{(N)}_{+},R^{(N)}_{-}\right)\leq\frac{1}{N}\rightarrow
0\,\,\text{ for }N\rightarrow\infty,$

hence both $R^{(N)}_{+}$ and $R^{(N)}_{-}$ converge to the same Root barrier
$R$ in Root’s metric. Moreover, it is a consequence of Lemma 4.3 together with
Donsker’s Theorem that

$\left|\tau^{(N)}_{+}-\tau^{(N)}_{-}\right|\xrightarrow[N\rightarrow\infty]{p}0.$

Now since $\tau^{(N)}_{+}\leq\rho^{(N)}\leq\tau^{(N)}_{-}$ the convergence
(4.7) follows, concluding the proof. ∎

####  4.3.2. A Limit of Rost Stopping Times

We are left to show convergence of discrete Rost solutions of (dSEP) to
continuous ones. For a measurable set $A$ and $t\geq 0$ recall the following
measures defined in Section 2

$\displaystyle\nu_{t}(A)$
$\displaystyle=\mu(A)-\mathbb{P}^{\lambda}\left[W_{\rho}\in
A,\rho<t\right]\,\,\text{ and }$ $\displaystyle\alpha_{t}(A)$
$\displaystyle=\alpha\left(\\{t\\}\times
A\right)=\mathbb{P}^{\lambda}\left[W_{t}\in A,\eta=t\right].$

######  Lemma 4.6.

Let $\left(\rho^{(N)}\right)_{n\in\mathbb{N}}$ be a sequence of discrete Rost
stopping times. Then there exists a Rost barrier
$\bar{R}\subseteq[0,\infty)\times\mathbb{R}$ such that we have the following
convergence

$\left(\rho^{(N)},W^{(N)}_{\rho^{(N)}}\right)\xrightarrow{d}\left(\rho,W_{\rho}\right)$
(4.8)

where

$\rho:=\inf\left\\{t\geq\eta:(t,W_{t})\in\bar{R}\right\\}\wedge Z$

for

$Z=\min_{k\in\mathbb{N}}Z_{k},\quad Z_{k}:=\begin{cases}t_{k}&\text{ with
probability
}\,\mathbb{P}^{\lambda}\left[Z=t_{k}\big{|}W_{\eta},\eta=t_{k}\right]=\frac{\mathrm{d}\left(\alpha_{t_{k}}\wedge\nu_{t_{k}}\right)}{\mathrm{d}\left(\alpha_{t_{k}}\right)}\left(W_{\eta}\right)\\\
\infty&\text{ else. }\end{cases}$