Stefan Ankirchner
email: s.ankirchner@uni-jena.de

Thomas Kruse
email: thomas.kruse@uni-due.de

Mikhail Urusov
email: mikhail.urusov@uni-due.de

A functional limit theorem for continuous Markov processes

Keywords: Markov process, Markov chain approximation, functional limit theorem, rate of convergence, sticky Brownian motion, slow reflection. 2010 MSC: 60F17, 60J60, 60H35, 60J22

We present an algorithm for approximating one-dimensional regular continuous strong Markov processes, including, e.g., processes with sticky points. The algorithm is based on the construction of Markov chains whose laws can be embedded into the process with a sequence of stopping times. We show a functional limit theorem stating that the Markov chains converge in distribution to the continuous Markov process. Under a mild condition on the process' speed measure we prove that the approximating Markov chains converge at fixed times at the rate of 1/4 with respect to every L p -norm and in the p-th Wasserstein distance, while, for the convergence of paths, we prove any rate strictly smaller than 1/4. Finally, we illustrate the algorithm's performance for sticky Brownian motion, with and without reflection.

Introduction

In this paper we propose an algorithm for a Markov chain approximation of onedimensional regular continuous strong Markov processes. In what follows we use the term general diffusions for the latter class of processes. While (weak) solutions of stochastic differential equations are regular continuous strong Markov processes, there are many interesting general diffusions that cannot be characterized as solutions of SDEs.

One such example is Brownian motion on R sticky at zero. This is a continuous process that behaves like a Brownian motion outside zero but spends a positive amount of time at zero having no intervals of zeros. More precisely, almost surely it holds that the zeros of the paths of a sticky Brownian motion constitute a nowhere dense set with a positive Lebesgue measure, i.e., a set that looks like a "fat" Cantor set. This phenomenon is due to the fact that the speed measure of the Brownian motion on R sticky at zero has an atom at zero, which shows that such a process cannot be realized as a solution of an SDE even with very irregular coefficients because the speed measures of solutions of SDEs are absolutely continuous with respect to the Lebesgue measure in the interior of the state space. A related interesting phenomenon is slow reflection. In this case the sticky point is located at the boundary of the state space.

Recent years have witnessed a renewed interest in the sticky Brownian motion and related processes, see [START_REF] Karatzas | On the one-sided Tanaka equation with drift[END_REF], [START_REF] Bass | A stochastic differential equation with a sticky point[END_REF], [START_REF] Engelbert | Stochastic differential equations for sticky Brownian motion[END_REF], [START_REF] Hajri | Application of stochastic flows to the sticky Brownian motion equation[END_REF] and references therein. Lately, diffusions with slow reflection were applied in [START_REF] Eberle | Sticky couplings of multidimensional diffusions with different drifts[END_REF] to provide bounds (via sticky couplings) for the distance between two multidimensional diffusions with different drifts. Diffusions with slow reflection also attracted interest in economic theory, where such processes characterize optimal continuation values in dynamic principal-agent problems (see, e.g., [START_REF] Zhu | Optimal contracts with shirking[END_REF] and [START_REF] Piskorski | Optimal dynamic contracts with moral hazard and costly monitoring[END_REF]).

For approximating general diffusions with atoms in the speed measure we are only aware of algorithms that are tailor-made for specific examples. [START_REF] Amir | Sticky Brownian motion as the strong limit of a sequence of random walks[END_REF] provides a sequence of random walks that converges in distribution to the Brownian motion on R sticky at zero. The random walks considered there are forced to stay in zero for some time whenever they visit zero. In contrast to our approach, the approximating processes are not Markov chains. [START_REF] Fushiya | Weak convergence theorem of a nonnegative random walk to sticky reflected brownian motion[END_REF] constructs Markov chains that converge in distribution to the Brownian motion on [0, ∞) with sticky reflection at 0. The approximating Markov chains considered there exhibit sticky behavior in zero in the sense that once the Markov chains reach zero they stay there with positive probability also in the next time period.

We suggest here an approximation algorithm that applies to all general diffusions and uses Markov chains as approximating processes. Our first main result is a functional limit theorem (Theorem 1.1), which establishes convergence of our algorithm. Moreover, we derive convergence rates under the additional assumption that the diffusion is not faster, up to a constant, than a Brownion motion (see Condition (C) in Section 4) and show by means of an example that, in general, such an additional assumption cannot be omitted. We show that at any fixed time the Markov chain approximations converge at rate of at least 1/4 with respect to every L p -norm (Theorem 4.1) and therefore also for every p-th Wasserstein distance (Corollary 4.3). We also prove that the paths converge uniformly in time at a rate that is infinitesimally smaller than 1/4 again with respect to L p -norms (Theorem 4.4) and p-th Wasserstein distances (Corollary 4.5). We stress that the convergence rates hold true regardless of how "irregular" the behavior of Y is. 1The idea of our algorithm is to construct the approximating Markov chains together with certain sequences of stopping times 2 (τ N k ) k∈N 0 , N ∈ N, such that the scheme is "exact along these sequences": namely, if Y = (Y t ) t≥0 is a general diffusion to be approximated via a sequence of Markov chains X N = (X N k ) k∈N 0 we must have (Y τ N k ) k∈N 0 d = (X N k ) k∈N 0 for all N ∈ N. Moreover, we require that the expected time lag between two consecutive stopping times is 1/N . First we prove that it is, indeed, always possible to find such sequences (τ N k ) of stopping times and construct the corresponding sequence X N of Markov chains. Then, in order to establish weak convergence of X N to Y , the crucial step is to show that the family τ N k , k ∈ N 0 , N ∈ N, satisfies a certain law of large numbers for arrays. This is a delicate point because the random variables in the arrays are only uncorrelated but not necessarily independent (see the discussion after Theorem 3.2 in [START_REF] Ankirchner | A functional limit theorem for irregular SDEs[END_REF] as well as [START_REF] Ankirchner | WLLN for arrays of nonnegative random variables[END_REF] for more details on the literature on related laws of large numbers). We overcome this problem via a technical result, Theorem 3.3, which is also of interest in itself, and which can be viewed as a uniform in k ∈ {1, . . . , N } rate with respect to every L α -norm in the law of large numbers for (τ N k ) (as N → ∞). It is worth noting that Theorem 3.3 does not force us to introduce any extra assumption, and we obtain an algorithm that, indeed, applies to all general diffusions. Moreover, Theorem 3.3 is also useful for establishing the convergence rates.

An algorithm with a similar idea (i.e., "exact along a sequence of stopping times") for the SDE

dY t = η(Y t ) dW t (1)
was suggested in [START_REF] Ankirchner | Numerical approximation of irregular SDEs via Skorokhod embeddings[END_REF] and [START_REF] Ankirchner | A functional limit theorem for irregular SDEs[END_REF]. Notice that SDE (1) is a special case of the setting in the present paper: (1) is known to have a unique in law weak solution under the Engelbert-Schmidt condition that η is a non-vanishing Borel function (possibly, very irregular) such that 1/η 2 is locally integrable (see [START_REF] Engelbert | On solutions of one-dimensional stochastic differential equations without drift[END_REF] or Theorem 5.5.7 in [START_REF] Karatzas | Brownian Motion and Stochastic Calculus[END_REF]), and, in this case, Y is a regular continuous strong Markov process in natural scale with speed measure given by the formula m(dx) = 2 η 2 (x) dx. In [START_REF] Ankirchner | A functional limit theorem for irregular SDEs[END_REF] the convergence of the scheme for (1) is proved, however, under the assumption that |η| and 1/|η| are locally bounded, which is significantly stronger than the mentioned Engelbert-Schmidt condition, but is essential for the method of the proof in [START_REF] Ankirchner | A functional limit theorem for irregular SDEs[END_REF]. Moreover, there is a certain weak law of large numbers for uncorrelated arrays in [START_REF] Ankirchner | A functional limit theorem for irregular SDEs[END_REF], which provides convergence in probability only (no L αrates -cf. with the discussion above), but requires even global boundedness of |η| and 1/|η| (cf. with the previous discussion of Theorem 3.3). In [START_REF] Ankirchner | Numerical approximation of irregular SDEs via Skorokhod embeddings[END_REF] it is proved that the scheme of [START_REF] Ankirchner | A functional limit theorem for irregular SDEs[END_REF] has rate 1/4, but again under the strong assumption of global boundedness of |η| and 1/|η|, and this is again essential for the argumentation in [START_REF] Ankirchner | Numerical approximation of irregular SDEs via Skorokhod embeddings[END_REF]. Also, the method in [START_REF] Ankirchner | Numerical approximation of irregular SDEs via Skorokhod embeddings[END_REF] to establish the rate is based on bounding Var[τ N N ], which in the end gives the rate with respect to L 2 -norm only.

The following list summarizes the contributions of our present paper.

• Compared to [START_REF] Ankirchner | Numerical approximation of irregular SDEs via Skorokhod embeddings[END_REF] and [START_REF] Ankirchner | A functional limit theorem for irregular SDEs[END_REF], we extend the scope of our algorithm, i.e., we extend the our numerical results in Section 6 for the sticky Brownian motion suggest that the actual rate is better. 2 Throughout, N denotes the set of positive integers, while N 0 = N ∪ {0} is the set of nonnegative ones. construction of approximating Markov chains X N with scaled Bernoulli increments to the case where Y is a general diffusion. In particular, it applies to diffusions that cannot be described as solutions of SDEs, e.g., the sticky Brownian motion.

• We weaken the assumptions under which the algorithm is proved to converge.

Even in the special case of (1), we now have the convergence under the Engelbert-Schmidt condition only (cf. with the discussion in the previous paragraph).

• We prove the convergence rate 1/4 at terminal time with respect to every L pnorm and in the p-th Wasserstein distance under a weaker condition than the one required in [START_REF] Ankirchner | Numerical approximation of irregular SDEs via Skorokhod embeddings[END_REF] (and, in [START_REF] Ankirchner | Numerical approximation of irregular SDEs via Skorokhod embeddings[END_REF], rate 1/4 is proved with respect to L 2 -norm only, while the convergence in the Wasserstein distance is not discussed). Namely, the assumption in the present paper is that the speed measure m(dx) of Y satisfies m(dx) ≥ c λ(dx) with some constant c > 0, where λ(dx) denotes the Lebesgue measure. In the particular case of (1), this means that |η| is bounded (in [START_REF] Ankirchner | Numerical approximation of irregular SDEs via Skorokhod embeddings[END_REF], both |η| and 1/|η| are required to be bounded to obtain the rate).

• For convergence of the whole path, we prove the rate 1 4 -ε, where ε is arbitrarily small (see Theorem 4.4 for the precise formulation). We then deduce the rate 1 4 -ε for convergence in every p-th Wasserstein distance on the path space. Results of the latter type are not provided in [START_REF] Ankirchner | Numerical approximation of irregular SDEs via Skorokhod embeddings[END_REF] and [START_REF] Ankirchner | A functional limit theorem for irregular SDEs[END_REF].

As noted in [START_REF] Alfonsi | Pathwise optimal transport bounds between a one-dimensional diffusion and its Euler scheme[END_REF], the Wasserstein distance is an appropriate measure for the distance between the path distribution of a diffusion and its Markov chain approximation. In [START_REF] Alfonsi | Pathwise optimal transport bounds between a one-dimensional diffusion and its Euler scheme[END_REF] every p-th Wasserstein distance between the path distribution of a Lipschitz continuous and uniformly elliptic SDE and its Euler approximation is shown to converge to zero with rate 2 3 -ε for every positive real ε. As discussed above, the approximations of our algorithm also converge with respect to every p-th Wasserstein distance; we prove convergence of our algorithm in Wasserstein distances for a larger class of diffusions but at a slower rate.

There are a few related schemes in the literature that employ random time grids to approximate solutions of one-dimensional SDEs. In [START_REF] Etoré | A Donsker theorem to simulate one-dimensional processes with measurable coefficients[END_REF] the authors first fix a finite grid in the state space of the diffusion. Then they construct a Bernoulli random walk on this grid that can be embedded into the diffusion. The authors determine the expected time for attaining one of the neighboring points by solving a PDE.

A similar scheme is set-up in [START_REF] Milstein | Uniform approximation of the Cox-Ingersoll-Ross process via exact simulation at random times[END_REF] to approximate the Cox-Ingersoll-Ross (CIR) process. Also here the authors first fix a grid on [0, ∞) and then construct a random walk on the grid that can be embedded into the CIR process. In contrast to [START_REF] Etoré | A Donsker theorem to simulate one-dimensional processes with measurable coefficients[END_REF], the authors in [START_REF] Milstein | Uniform approximation of the Cox-Ingersoll-Ross process via exact simulation at random times[END_REF] compute the distributions of the embedding stopping times (and not only their expected value) by solving a parabolic PDE. In the numerical implementation of the scheme the authors then draw the random time increments from these distributions and thereby obtain a scheme that is exact along a sequence of stopping times.

Note that in contrast to [START_REF] Etoré | A Donsker theorem to simulate one-dimensional processes with measurable coefficients[END_REF] and [START_REF] Milstein | Uniform approximation of the Cox-Ingersoll-Ross process via exact simulation at random times[END_REF], in our approach the space grid is not fixed a priori. Instead, we fix the expected time lag between the consecutive embedding stopping times. The state distribution of the approximating Markov chain is then determined endogenously through a state-dependent scale factor (see a N defined in (7) below).

Yet a further scheme that uses a random time partition to approximate a diffusion Y with discontinuous coefficients is suggested in [START_REF] Lejay | An exponential timestepping algorithm for diffusion with discontinuous coefficients[END_REF]. In contrast to our approach the distribution of the time increments is fixed there. More precisely, the authors of [START_REF] Lejay | An exponential timestepping algorithm for diffusion with discontinuous coefficients[END_REF] use the fact that the distribution of Y sampled at an independent exponential random time is given by the resolvent of the process. Consequently, if it is possible to generate random variables distributed according to the resolvent kernel, one obtains an exact simulation of Y at an exponentially distributed stopping time. Iterating this procedure and letting the parameter of the exponential distribution go to infinity provides an approximation of Y .

Our algorithm seems to be mainly useful for irregular diffusions for which standard approximation schemes, e.g., the Euler one, are not applicable. We remark that there exist several approaches for approximating specific irregular SDEs with the Euler scheme (see, e.g., [START_REF] Kohatsu-Higa | Weak rate of convergence of the Euler-Maruyama scheme for stochastic differential equations with non-regular drift[END_REF] for SDEs with irregular drift coefficients).

The paper is structured as follows. In Section 1 we rigorously define, for a given general diffusion, a sequence of approximating Markov chains and formulate a functional limit theorem. In Section 2 we show that the Markov chains can be embedded into the diffusion with sequences of stopping times. Section 3 provides the proof of the functional limit theorem. In Section 4 we prove convergence rates for the Markov chain approximation, discuss convergence in Wasserstein distances as well as the condition under which we obtain the rates and the convergence in Wasserstein distances. Throughout the first four sections we assume that any accessible boundary point of the state space is absorbing. In Section 5 we explain how the approximation scheme can be extended to diffusions with reflecting boundary points. The extension works for both instantaneous and slow reflection. Finally, in Section 6, we illustrate our algorithm in the cases of sticky Brownian motions on R and on [0, ∞), where the sticky point is zero.

Approximating general diffusions with Markov chains

Let (Ω, F, (F t ) t≥0 , (P y ) y∈I , (Y t ) t≥0 ) be a one-dimensional continuous strong Markov process in the sense of Section VII.3 in [START_REF] Revuz | of Grundlehren der Mathematischen Wissenschaften[END_REF]. We assume that the state space is an open, half-open or closed interval I ⊆ R. We denote by I • = (l, r) the interior of I, where -∞ ≤ l < r ≤ ∞, and we set Ī = [l, r]. Recall that by the definition we have P y [Y 0 = y] = 1 for all y ∈ I. We further assume that Y is regular. This means that for every y ∈ I • and x ∈ I we have that [START_REF] Revuz | of Grundlehren der Mathematischen Wissenschaften[END_REF]). Recall that for all a < b in I • we have

P y [H x (Y ) < ∞] > 0, where H x (Y ) = inf{t ≥ 0 : Y t = x}. If
0 < m([a, b]) < ∞. (2)
Finally, in Sections 1-4 we also assume that if a boundary point is accessible, then it is absorbing. We drop this assumption in Section 5, where we extend our approximation method to Markov processes with reflecting boundaries. The extension works for both instantaneous and slow reflection.

We next construct a sequence of Markov chains that converges in distribution to the Markov process Y . For the construction we introduce the function q :

I • × Ī → [0, ∞] defined by q(y, x) = 1 2 m({y})|x -y| + x y m((y, u))du, (3)
where for u < y we set m((y, u)) := -m((u, y)). Notice that, for y ∈ I • , the function q(y, •) is decreasing on [l, y] and increasing on [y, r]. Recall the Feller test for explosions: for any

y ∈ I • , l is accessible (i.e., l ∈ I) ⇐⇒ q(y, l) < ∞, (4)
r is accessible (i.e., r ∈ I) ⇐⇒ q(y, r) < ∞

(see, e.g., Lemma 1.1 in [START_REF] Ankirchner | Stopping with expectation constraints: 3 points suffice[END_REF]). Consequently, q is finite on I • × I. Notice that for all y, z ∈ I • and x ∈ I we have q(z, x) = q(y, x) -q(y, z) -

∂ 0 q ∂x (y, z)(x -z), (6)
where ∂ 0 q ∂x (y, x) = 1 2 ( ∂ + q ∂x + ∂ -q ∂x )(y, x). For all y ∈ I • and N ∈ N we define a N (y) = sup a ≥ 0 : y + a ∈ I, y -a ∈ I and q(y, y

+ a) + q(y, y -a) ≤ 2 N . (7)
Moreover, we set a N (l) = a N (r) = 0. Notice that the sup in ( 7) is attained, because q(y, •) is continuous and satisfies (4) and [START_REF] Ankirchner | A functional limit theorem for irregular SDEs[END_REF].

For the rest of this section we fix a starting point y ∈ I • of Y . Let (ξ k ) k∈N 0 be an iid sequence of random variables, on a probability space with a measure P , satisfying

P (ξ k = ±1) = 1 2 .
For every N ∈ N we denote by (X N k ) k∈N 0 the Markov chain defined by

X N 0 = y and X N k+1 = X N k + a N (X N k )ξ k+1 , for k ∈ N 0 . (8)
We extend (X N k ) k∈N 0 to a continuous-time process by linear interpolation, i.e., for all t ∈ [0, ∞), we set

X N t = X N t + (t -t )(X N t +1 -X N t ). (9)
Then we have the following functional limit theorem.

Theorem 1.1. The distributions of the processes (X N N t ) t∈[0,1] under P converge weakly to the distribution of (Y t ) t∈[0,1] under P y , as N → ∞, i.e., for every functional F : C([0, 1], I) → R that is bounded and continuous with respect to the sup norm it holds that

E[F (X N N • )] → E y [F (Y )], N → ∞. (10)
In order to prove Theorem 1.1 we first show that for every N ∈ N the Markov chain (X N k ) k∈N 0 can be embedded in law into Y with a sequence of increasing stopping times with an expected time lag of 1/N . To be more precise, we construct in the next section for every N ∈ N a sequence of stopping times

(τ N k ) k∈N 0 such that (Y τ N k ) k∈N 0 d = (X N k ) k∈N 0 and E y (τ N k+1 -τ N k |F τ N k ) = 1 N for all k ∈ N 0 .
2 Embedding the chains into the Markov process

Before we construct the embedding stopping times we prove some auxiliary results.

Lemma 2.1. Let a < b in I and y ∈ (a, b). Then E y H a,b = E y q(y, Y H a,b ). (11)
Proof. Recall that the speed measure m satisfies

E y H a,b = (a,b) (b -x ∨ y)(x ∧ y -a) b -a m(dx),
(see e.g. Section VII.3 in [START_REF] Revuz | of Grundlehren der Mathematischen Wissenschaften[END_REF]). This implies

E y H a,b = 1 b -a (a,y) (b -y)(x -a)m(dx) + (y,b) (b -x)(y -a)m(dx) + (b -y)(y -a)m({y}) = b -y b -a (a,y) (x -a)m(dx) + (y -a) m({y}) 2 + y -a b -a (y,b) (b -x)m(dx) + (b -y) m({y}) 2 = b -y b -a q(y, a) + y -a b -a q(y, b) = E y q(y, Y H a,b ). Lemma 2.2. Let y ∈ I • . Then the process q(y, Y t ) -(t ∧ H l,r ), t ∈ [0, ∞), is a P y -local martingale. Proof. Let a, b ∈ I with a < y < b. We first show that q(y, Y t∧H a,b ) -t ∧ H a,b , t ∈ [0, ∞),
is a P y -martingale. For this purpose observe that for all t ∈ [0, ∞) it holds

E y q(y, Y H a,b ) -H a,b |F t = (q(y, Y H a,b ) -H a,b )1 {H a,b ≤t} + E y q(y, Y H a,b ) -H a,b |F t 1 {H a,b >t} . ( 12
)
On the event {H a,b > t} we have

q(y, Y H a,b ) -H a,b = q(y, Y H a,b ) • θ t -H a,b • θ t -t
, where θ t denotes the shift operator for Y (see Chapter III in [START_REF] Revuz | of Grundlehren der Mathematischen Wissenschaften[END_REF]). The Markov property and [START_REF] Etoré | A Donsker theorem to simulate one-dimensional processes with measurable coefficients[END_REF] imply that on the event {H a,b > t} we have P y -a.s.

E y q(y, Y H a,b ) -H a,b |F t =E z [q(y, Y H a,b ) -H a,b ] z=Yt -t =E z [q(y, Y H a,b ) -q(z, Y H a,b )] z=Yt -t. (13)
Formula ( 6) yields for all 13) implies that on the event {H a,b > t} we have P y -a.s.

z ∈ I • q(y, Y H a,b ) -q(z, Y H a,b ) = q(y, z) + ∂ 0 q ∂x (y, z)(Y H a,b -z). Since E z [Y H a,b -z] = 0 for all z ∈ I • , equation (
E y q(y, Y H a,b ) -H a,b |F t = q(y, Y t ) -t.
Together with [START_REF] Fushiya | Weak convergence theorem of a nonnegative random walk to sticky reflected brownian motion[END_REF] this yields for all t ∈ [0, ∞)

E y q(y, Y H a,b ) -H a,b |F t = q(y, Y t∧H a,b ) -t ∧ H a,b , which shows that q(y, Y t∧H a,b ) -t ∧ H a,b , t ∈ [0, ∞), is a P y -martingale.
The statement of the lemma follows via a localization argument. If l / ∈ I, then choose a decreasing sequence (l n ) n∈N ⊆ I with l 1 < y and lim n→∞ l n = l. If l ∈ I, set l n = l for all n ∈ N. Similarly, if r / ∈ I, then choose an increasing sequence (r n ) n∈N ⊆ I with r 1 > y and lim n→∞ r n = r, and if r ∈ I, then set r n = r for all n ∈ N. The sequence of stopping times inf{t ≥ 0 : X t / ∈ [l n , r n ]}, n ∈ N, is then a localizing sequence for the process q(y, Y t ) -(t ∧ H l,r ), t ∈ [0, ∞). Now we have everything at hand to start constructing a sequence of embedding stopping times. Suppose Y starts at a point y ∈ I • and fix

N ∈ N. Set τ N 0 = 0. Let σ N 1 = inf{t ≥ 0 : |Y t -y| = a N (y)}.
Note that by Lemma 2.1 we have

E y (σ N 1 ) = 1 2 (q(y, y + a N (y)) + q(y, y -a N (y))) ≤ 1 N .
We now define τ N 1 by distinguishing two cases:

If E y (σ N 1 ) = 1 N , then we set τ N 1 = σ N 1 . If c := E y (σ N 1 ) < 1
N , then we deterministically extend σ N 1 so as to make it have expectation

1 N . Notice that in this case it must hold that P y (Y σ N 1 = l or r) = 1 2 (only in the case max{|l|, |r|} < ∞, y = l+r
2 and a N (y) = r-l 2 that probability is 1, but we exclude this case by considering a sufficiently large N ∈ N, so that a N ( l+r 2 ) < r-l 2 ). Then set

τ N 1 = σ N 1 + 2 1 N -c 1 {Y σ N 1 =l or r} .
Observe that E y (τ N 1 ) = 1 N and that the three random variables Y τ N 1 , Y σ N 1 and X N 1 have all the same law.

We can proceed in a similar way to define the subsequent stopping times. Let k ∈ N. Suppose that we have already constructed τ N k . On the set

{Y τ N k = l or r} we set τ N k+1 = τ N k + 1 N . On {Y τ N k ∈ I • } we first define σ N k+1 = inf{t ≥ τ N k : |Y t -Y τ N k | = a N (Y τ N k )}. Note that Y τ N
k takes only finitely many values. Let a be a possible value and consider the event

A = {Y τ N k = a}. If c := E y [σ N k+1 -τ N k |A] < 1 N , then extend σ N k+1 on the event A by setting τ N k+1 = σ N k+1 + 2 1 N -c 1 {Y σ N k+1 =l or r} (14)
(notice that P y (Y σ N k+1 = l or r|A) = 1 2 ); else set τ N k+1 = σ N k+1 . Since Y has the strong Markov property, we have E y (τ N k+1 -τ N k |F τ N k ) = 1 N . Moreover, (Y τ N j ) j∈{0,...,k+1} d = (X N j ) j∈{0,.
..,k+1} . To sum up, we have the following. Proposition 2.3. For all N ∈ N the sequence of stopping times

(τ N k ) k∈N 0 satisfies 1. (Y τ N k ) k∈N 0 d = (X N k ) k∈N 0 , 2. E y (τ N k+1 -τ N k |F τ N k ) = 1 N for all k ∈ N 0 .
3 Proof of Theorem 1.1

In this section we prove Theorem 1.1. We start by estimating moments of first exit times.

E y [τ α ] ≤ α α 2 (q α (y, y -a) + q α (y, y + a)) . (15)
Proof. According to Lemma 2.2 the process N t := q(y, Y t ) -(t ∧ H l,r (Y )), t ≥ 0, is a P y -local martingale. The product formula yields for all t ∈ [0, H l,r (Y )]

t α-1 q(y, Y t ) = t α-1 N t + t α = (α -1) t 0 s α-2 N s ds + t 0 s α-1 dN s + t α = (α -1) t 0 s α-2 q(y, Y s )ds + t 0 s α-1 dN s + 1 α t α ≥ t 0 s α-1 dN s + 1 α t α . ( 16
)
Note that ( t 0 s α-1 dN s ) t≥0 is a local martingale and let (τ n ) n∈N be a localizing sequence for it. Set τ n := n ∧ τ n for all n ∈ N. In particular, it holds E y [τ α n ] < ∞ for all n ∈ N. With inequality ( 16) and Hölder's inequality we obtain for all n ∈ N that

E y [(τ n ∧ τ ) α ] ≤ αE y [(τ n ∧ τ ) α-1 q(y, Y τn∧τ )] ≤ α(E y [(τ n ∧ τ ) α ]) α-1 α (E y [q α (y, Y τn∧τ )]) 1 α . This implies for all n ∈ N E y [(τ n ∧ τ ) α ] ≤ α α E y [q α (y, Y τn∧τ )]. (17)
By monotone convergence the left-hand side converges to

E y [τ α ] as n → ∞. Since q(y, •) is bounded on [y-a, y+a] it follows from dominated convergence that E y [q α (y, Y τn∧τ )] → E y [q α (y, Y τ )] as n → ∞. Therefore we obtain E y [τ α ] ≤ α α E y [q α (y, Y τ )]
which is precisely [START_REF] Ikeda | Stochastic Differential Equations and Diffusion Processes[END_REF].

For all N ∈ N let (τ N k ) k∈N 0 be the sequence of embedding stopping times defined in Section 2. Then we have the following result about the time lags

τ N k -τ N k-1 , N ∈ N, k ∈ {1, . . . , N }, between consecutive stopping times. Lemma 3.2. For all α ∈ [1, ∞), y ∈ I • , N ∈ N and k ∈ {1, . . . , N } it holds that E y [(N (τ N k -τ N k-1 )) α ] ≤ 2 α (2 -1/α α + 1) α . In particular, for all y ∈ I • the family (N (τ N k - τ N k-1 )) N ∈N,k∈{1,...,N } is uniformly integrable under P y .
Proof. Note that by construction (cf. ( 14)) for all y ∈ I, z

∈ I • , N ∈ N, k ∈ {1, . . . , N } the conditional distribution under P z of the random variable τ N k -τ N k-1 on {Y τ N k-1 = y} is dominated by the distribution under P y of τ := H y-a N (y),y+a N (y) (Y ) + 2 N . (18)
It suffices therefore to prove for all α ∈ [1, ∞),

y ∈ I • and N ∈ N that E y [(N τ ) α ] ≤ 2 α (2 -1/α α + 1) α . Notice that for all α ∈ [1, ∞) a α + b α ≤ (a + b) α for a, b ∈ [0, ∞), (19)
because the function x → x α , x ∈ [0, ∞), is convex and increasing. It follows from the triangle inequality, Lemma 3.1, ( 19) and ( 7) that for all α ∈ [1, ∞), N ∈ N and y ∈ I • it holds

(E y [τ α ]) 1 α ≤ E y [H y-a N (y),y+a N (y) (Y ) α ] 1 α + 2 N ≤ 2 -1/α α (q α (y, y -a N (y)) + q α (y, y + a N (y))) 1 α + 2 N ≤ 2 -1/α α (q(y, y -a N (y)) + q(y, y + a N (y))) + 2 N ≤ 2(2 -1/α α + 1) N .
This completes the proof.

The following result can be viewed as a uniform in k Law of Large Numbers in spaces L α for (τ N k ) as N → ∞. It is useful not only for proving Theorem 1.1 but also for establishing the rates of convergence in Section 4.

Below, for a random variable ξ, it is convenient to use the notation

ξ L α (Py) = (E y |ξ| α ) 1/α
for all α ∈ (0, ∞), even though it is not a norm for α ∈ (0, 1). Notice that ξ L α (Py) ≤ ξ L β (Py) for 0 < α < β by the Jensen inequality.

Theorem 3.3. Let α ∈ (0, ∞). There exists a constant C(α) ∈ (0, ∞) (only depending on α) such that for all N ∈ N and y ∈ I • it holds that

sup k∈{1,...,N } τ N k - k N L α (Py) ≤ C(α)N -1/2 .
Proof. Without loss of generality we consider α ∈ [2, ∞). Throughout the proof we fix N ∈ N and y ∈ I • . For all k ∈ {0, . . . , N } we define

G k = F τ N k and M k = τ N k -k N . Notice that (M k ) k∈{0,...,N } is a (G k ) k∈{0,.
..,N } -martingale. The Burkholder-Davis-Gundy inequality ensures that there exists a constant C(α) ∈ (0, ∞) (only depending on α) such that

E y sup k∈{1,...,N } τ N k - k N α ≤ C(α)E y   N k=1 (M k -M k-1 ) 2 α 2   = C(α)E y   N k=1 τ N k -τ N k-1 - 1 N 2 α 2   .
This, together with Jensen's inequality, proves that

E y sup k∈{1,...,N } τ N k - k N α ≤ C(α)N α 2 -1 N k=1 E y τ N k -τ N k-1 - 1 N α . (20)
It follows from Lemma 3.2 that for all k ∈ {1, . . . , N } it holds

E y τ N k -τ N k-1 - 1 N α = E y N (τ N k -τ N k-1 ) -1 α N α ≤ 2 α (2 -1/α α + 1) α + 1 N α . (21)
Combining ( 20) and ( 21) completes the proof.

Proof of Theorem 1.1. The proof now goes along the lines of the proof of Theorem 3.1 in [START_REF] Ankirchner | A functional limit theorem for irregular SDEs[END_REF]. Technically, the present proof is even easier because we get from Theorem 3.

3 that τ N N s Py ---→ N →∞ s for all s ∈ [0, 1], (22)
and this allows to pursue the argumentation in the proof of Theorem 3.1 in [START_REF] Ankirchner | A functional limit theorem for irregular SDEs[END_REF] without the technical truncation argument; cf. [START_REF] Milstein | Uniform approximation of the Cox-Ingersoll-Ross process via exact simulation at random times[END_REF] with Lemma 3.5 in [START_REF] Ankirchner | A functional limit theorem for irregular SDEs[END_REF].

Remark 3.4. Notice that Theorem 1.1 generalizes Theorem 3.1 in [START_REF] Ankirchner | A functional limit theorem for irregular SDEs[END_REF] in two directions. While Theorem 3.1 in [START_REF] Ankirchner | A functional limit theorem for irregular SDEs[END_REF] deals only with approximation of diffusions driven by the SDE

dY t = η(Y t ) dW t , (23)
which are diffusions with the speed measure m(dx) = 2 η 2 (x) dx being absolutely continuous with respect to the Lebesgue measure, we manage here to approximate strong Markov processes with general speed measures, e.g., with ones that have atoms. Furthermore, even though in [START_REF] Ankirchner | A functional limit theorem for irregular SDEs[END_REF] we exhausted the method of the proof of Theorem 3.1 of that paper, we still did not get rid of the assumption that |η| and 1/|η| are locally bounded (in [START_REF] Ankirchner | A functional limit theorem for irregular SDEs[END_REF]). On the contrary, the argumentation above built on Lemmas 3.1 and 3.2 and on Theorem 3.3 does not need those restrictions, and thus Theorem 1.1 is more general than Theorem 3.1 of [START_REF] Ankirchner | A functional limit theorem for irregular SDEs[END_REF] even when we restrict ourselves to [START_REF] Piskorski | Optimal dynamic contracts with moral hazard and costly monitoring[END_REF]. The only assumption on η that we need in case of ( 23) is the Engelbert-Schmidt condition: η does not vanish in I • and 1/η 2 is locally integrable in I • (see [START_REF] Engelbert | On solutions of one-dimensional stochastic differential equations without drift[END_REF] or Theorem 5.5.7 in [START_REF] Karatzas | Brownian Motion and Stochastic Calculus[END_REF]). The role of the Engelbert-Schmidt condition is to guarantee that (23) has a unique in law weak solution (up to the exit time H l,r (Y )) that is a regular strong Markov process with I • being the interior of its state space.

Rate of convergence

In this section, we establish rates of convergence of our scheme for single points in time, for multiple points in time, in the Wasserstein distance for marginal distributions and on the path space. We make the additional assumption that the Lebesgue measure has a bounded density with respect to the speed measure. More precisely, we suppose that the following condition is satisfied.

Condition (C) There exists a constant c > 0 such that on I • we have m(dx) ≥ c λ(dx), i.e., for all A ∈ B(I • ) we have m(A) ≥ c λ(A), where λ(dx) denotes the Lebesgue measure.

In the end of this section, we explain why we cannot omit Condition (C) in general.

Throughout this section let (τ N k ) k∈N 0 , N ∈ N, be the embedding stopping times defined in Section 2.

Rate of convergence for single points in time

Y τ N N -Y 1 L p (Py) ≡ E y |Y τ N N -Y 1 | p 1/p ≤ C(p)N -1/4 .
We recall that the notation • L p (Py) is introduced for all p ∈ (0, ∞) for the sake of convenience (even though it is not a norm for p ∈ (0, 1)).

Proof. Throughout the proof we fix N ∈ N and y ∈ I • . It is known that Y can be written as a time-changed Brownian motion. To be more precise, by extending the probability space (if necessary), we can find a process W which is a Brownian motion starting in y under P y such that

Y t = W γ(t) , for all t ∈ [0, ∞),
with the random time change γ : [0, ∞) → [0, ∞) being the right inverse of A, i.e.

γ(t) = inf{s ∈ [0, ∞) : A(s) > t}, t ∈ [0, ∞),
where the increasing process A : [0, ∞) → [0, ∞] is given by the formula

A(t) = 1 2 I L x t m(dx), t ∈ [0, ∞),
and (L x t ), t ∈ [0, ∞), x ∈ R, denotes the the local time of W (see Theorem V.47.1 in [START_REF] Rogers | Diffusions, Markov processes, and martingales[END_REF] and notice that our speed measure is twice as large as the speed measure in [START_REF] Rogers | Diffusions, Markov processes, and martingales[END_REF]). For all 0 ≤ s < t ≤ H l,r (W ) we have

A(t) -A(s) = 1 2 I (L x t -L x s )m(dx) ≥ c 2 R 1 I (x)(L x t -L x s )dx = c 2 t s 1 I (W u )du = c 2 (t -s),
where the second last equality follows from the occupation time formula. Note that this implies for all 0 ≤ s < t ≤ A(H l,r (W )) (= H l,r (Y ))

γ(t) -γ(s) ≤ 2 c (t -s). (24)
Recall that accessible boundaries are assumed to be absorbing. Therefore, the time change γ is stopped at H l,r (Y ) and hence [START_REF] Revuz | of Grundlehren der Mathematischen Wissenschaften[END_REF] holds, in fact, for all 0 ≤ s < t. The formulas

Y τ N N = W γ(τ N N ) and Y 1 = W γ(1)
, the Burkholder-Davis-Gundy inequality for W , formula [START_REF] Revuz | of Grundlehren der Mathematischen Wissenschaften[END_REF] and Theorem 3.3 imply that there exist constants C(p), C(p) ∈ (0, ∞) (not depending on N or y) such that

E y |Y τ N N -Y 1 | p = E y |W γ(τ N N ) -W γ(1) | p ≤ C(p)E y |γ(τ N N ) -γ(1)| p 2 ≤ 2 c p 2 C(p)E y |τ N N -1| p 2 ≤ C(p) p N -p 4 .
This completes the proof.

It is worth noting that, under Condition (C), all random variables Y t , t ∈ [0, ∞), have finite absolute moments of any order. While this can be inferred directly from Theorem 4.1, we prefer to state a slightly more general result of such kind and to prove it along the lines of the proof of Theorem 4.1. Proposition 4.2. Suppose that Condition (C) is satisfied and let p ∈ (0, ∞). Then, for all T ∈ [0, ∞) and y ∈ I • , it holds

E y sup t∈[0,T ] |Y t | p < ∞.
Proof. The result follows from the representation Y t = W γ(t) of the proof of Theorem 4.1 together with the bound γ(t) ≤ (2/c)t, t ∈ [0, ∞), which, in turn, follows from [START_REF] Revuz | of Grundlehren der Mathematischen Wissenschaften[END_REF] and the discussion immediately after it.

For p ∈ [1, ∞) let M p (R) denote the set of all probability measures on (R, B(R)) with finite p-th moment, i.e., probability measures µ satisfying |x| p µ(dx) < ∞. The p-th Wasserstein distance between two probability measures µ, ν ∈ M p (R) is defined by

W p (µ, ν) = inf ξ -ζ L p ,
where the infimum is taken over all couplings between µ and ν, that is, over all random vectors (ξ, ζ) with marginals µ and ν (i.e., ξ ∼ µ and ζ ∼ ν). Observe that by construction (Y τ N N , Y 1 ) is a coupling between the laws of X N N and Y 1 . Therefore, we immediately arrive at the following corollary of Theorem 4.1.

Corollary 4.3. Suppose that Condition (C) is satisfied and let p ∈ [1, ∞). Then there exists a constant C(p) ∈ (0, ∞) such that for all N ∈ N and y ∈ I • it holds that

W p (P • (X N N ) -1 , P y • (Y 1 ) -1 ) ≤ C(p)N -1/4 .

Rate of convergence for multiple points in time

Theorem 4.4. Suppose that Condition (C) is satisfied and let p ∈ (0, ∞) and ε ∈ (0, 1 4 ). Then there exists a constant C(p, ε) ∈ (0, ∞) such that for all N ∈ N and y ∈ I • it holds that

sup k∈{0,...,N } |Y τ N k -Y k N | L p (Py) ≤ C(p, ε)N -( 1 4 -ε) .
Proof. Without loss of generality we assume that p ≥ 1 and ε ∈ (0, 1 p ∧ 1 4 ). The general case follows directly by the Jensen inequality. Throughout the proof we fix N ∈ N and y ∈ I • . We use the notation C i (p, ε) ∈ (0, ∞), i ∈ N, for constants independent of N and y. As in the proof of Theorem 4.1 we use the fact that Y can be written as a timechanged Brownian motion W , i.e., Y t = W γ(t) for all t ∈ [0, ∞). First, observe that the Markov inequality and Theorem 3.3 imply that there exists a constant

C 1 (p) ∈ (0, ∞) such that P y [τ N N ≥ 2] ≤ E y |τ N N -1| 3p ≤ C 1 (p)N -3 2 p . (25)
Moreover, [START_REF] Revuz | of Grundlehren der Mathematischen Wissenschaften[END_REF] ensures that

sup k∈{0,...,N } |Y k N -y| = sup k∈{0,...,N } |W γ( k N ) -y| ≤ sup s∈[0, 2 c ]
|W s -y| and consequently there exists a constant

C 2 (p) ∈ (0, ∞) such that sup k∈{0,...,N } |Y k N -y| L 2p (Py) ≤ C 2 (p). (26)
Condition (C) ensures that for all z ∈ I • and x ∈ I it holds that

q(z, x) ≥ 1 2 m({z})|x -z| + c x z (u -z) du ≥ c 2 (x -z) 2 .
This implies for all z ∈ I that a N (z) ≤ 2 cN . It follows from the construction of the stopping times

(τ N k ) k∈{0,...,N } that |Y τ N k -y| ≤ k 2 cN ≤ 2N
c , P y -a.s., for all k ∈ {0, . . . , N }. This, the Cauchy-Schwarz inequality, ( 25) and [START_REF] Villani | of Grundlehren der Mathematischen Wissenschaften[END_REF] prove that there exists a constant C 3 (p) ∈ (0, ∞) such that

1 {τ N N ≥2} sup k∈{0,...,N } |Y τ N k -Y k N | L p (Py) ≤ (P y [τ N N ≥ 2]) 1 2p sup k∈{0,...,N } |Y τ N k -Y k N | L 2p (Py) ≤ C 1 (p) 1 2p N -3 4 2N c + C 2 (p) ≤ C 3 (p)N -1 4 . (27)
Next, due to the scaling property of normal distribution, for all s, t ∈ [0, ∞), we have

E y [|W s -W t | 1 ε ] = C 4 (ε)|s -t| 1 2ε with C 4 (ε) = E|N (0, 1)| 1 ε < ∞.
Together with the fact that 0 ≤ 1 2 -2ε < ε( 1 2ε -1), this allows to apply the Kolmogorov-Chentsov theorem (see, e.g., Theorem I.2.1 in [START_REF] Revuz | of Grundlehren der Mathematischen Wissenschaften[END_REF]) to obtain that there exists a constant

C 5 (ε) ∈ (0, ∞) such that sup s,t∈[0, 4 c ] s =t |W s -W t | |s -t| 1 2 -2ε L 1 ε (Py) ≤ C 5 (ε). ( 28
)
Theorem 3.3 implies that, for any α ∈ (0, ∞), there exists a constant

C 6 (α, ε) ∈ (0, ∞) such that sup k∈{0,...,N } τ N k - k N 1 2 -2ε L α (Py) ≤ C 6 (α, ε)N -( 1 4 -ε) . (29)
By ( 24) it holds on the set {τ

N N < 2} that sup k∈{0,...,N } |Y τ N k -Y k N | = sup k∈{0,...,N } |W γ(τ N k ) -W γ( k N ) | ≤    sup s,t∈[0, 4 c ] s =t |W s -W t | |s -t| 1 2 -2ε    sup k∈{0,...,N } γ(τ N k ) -γ k N 1 2 -2ε ≤ 2 c 1 2 -2ε      sup s,t∈[0, 4 c ] s =t |W s -W t | |s -t| 1 2 -2ε      sup k∈{0,...,N } τ N k - k N 1 2 -2ε
.

This, the Hölder inequality (applied with the conjugates 1 pε and 1 1-pε ), ( 28) and (29) ensure that there exists a constant C 7 (p, ε) ∈ (0, ∞) such that

1 {τ N N <2} sup k∈{0,...,N } |Y τ N k -Y k N | L p (Py) ≤ 2 c 1 2 -2ε sup s,t∈[0, 4 c ] s =t |W s -W t | |s -t| 1 2 -2ε L 1 ε (Py) sup k∈{0,...,N } τ N k - k N 1 2 -2ε L p 1-pε (Py) ≤ C 7 (p, ε)N -( 1 4 -ε) . (30)
The triangle inequality, ( 27) and (30) imply the claim.

With a little more effort, but proceeding in the same way as in the proof of Theorem 4.4, one obtains the following continuous-time generalization. Let ( Y N t ) t∈[0,∞) be the continuous-time process obtained from the discrete-time process (Y τ N k ) k∈N 0 via linear interpolation:

Y N t = Y τ N t + (t -t )(Y τ N t +1 -Y τ N t ), t ∈ [0, ∞). (31)
Then, under Condition (C), for all p ∈ (0, ∞) and ε ∈ (0, 1 4 ) there exists a constant C(p, ε) ∈ (0, ∞) such that for all N ∈ N and y ∈ I • it holds that

sup t∈[0,1] | Y N t -Y t | L p (Py) ≤ C(p, ε)N -( 1 4 -ε) . ( 32
)

Convergence in the Wasserstein distance on the path space

We now discuss some consequences of (32) for Markov chain approximation of path functionals of Y . We use the notation ( Y N t ) of (31) and, for large N ∈ N, we define (simulate) on a suitable probability space with measure P the continuous-time process X y,N via ( 8)-( 9) (in contrast to ( 8)-( 9) we now additionally stress the starting point y in the notation) and recall that (X y,N t

) t∈[0,∞) d = ( Y N t ) t∈[0,∞) . Let p ∈ [1, ∞).
From (32) we deduce the rate at which the law of X y,N converges to the one of Y with respect to the p-th Wasserstein distance on the path space C([0, 1], I) (with sup norm x C = sup t∈[0,1] |x(t)|). Let M p (C([0, 1], I)) denote the set of all probability measures µ on C([0, 1], I) (equipped with the Borel σ-field) with finite p-th moment, that is,

x p C µ(dx) < ∞. The p-th Wasserstein distance between µ, ν ∈ M p (C([0, 1], I)) is defined by W p (µ, ν) = inf sup t∈[0,1] |ξ t -ζ t | L p
, where the infimum is taken over all couplings between µ and ν, i.e., over all random elements (ξ, ζ) taking values in C([0, 1], I 2 ) with marginals µ and ν (that is, ξ ∼ µ and ζ ∼ ν). Note that:

• The random element ( Y N • , Y ) constitutes a coupling between the laws of X y,N N • and Y on the path space C([0, 1], I).

• Both the law of X y,N N • and that of Y on the path space C([0, 1], I) are elements of M p (C([0, 1], I)) (for every p ∈ [1, ∞)). For the latter, this follows from Proposition 4.2. For the former, this follows from the fact that, for any N ∈ N, each of the random variables X y,N k , k = 0, . . . , N , takes only finitely many values, which implies that the process (X y,N N t ) t∈[0,1] is, in fact, bounded (the bound depends on N ). After these preparations we obtain from (32) the following result.

Corollary 4.5. Suppose that Condition (C) is satisfied and let p ∈ [1, ∞) and ε ∈ (0, 1 4 ). Then there exists a constant C(p, ε) ∈ (0, ∞) such that for all N ∈ N and y ∈ I

• it holds that W p (P • (X y,N N • ) -1 , P y • (Y ) -1 ) ≤ C(p, ε)N -( 1 4 -ε) .
Discussion It is instructive to compare Theorem 1.1 and Corollary 4.5. The former works for any general diffusion, the latter assumes Condition (C). On the other hand, while the former provides weak convergence of our algorithm only, the latter gives us the rate, and even in every p-th Wasserstein distance. It is worth noting that convergence in the p-th Wasserstein distance is stronger than weak convergence and has several attractive properties not shared by the latter (see the discussion after Corollary 6.13, especially, points 1-5 preceding Lemma 6.14 in [START_REF] Villani | of Grundlehren der Mathematischen Wissenschaften[END_REF]). In particular, we conclude with the following result.

Corollary 4.6. Assume Condition (C). Let F : C([0, 1], I) → R be a continuous path functional of polynomial growth, i.e., there

exist p ∈ [1, ∞), K ∈ [0, ∞) such that for all x ∈ C([0, 1], I) it holds |F (x)| ≤ K(1 + x p C ). Then, for all y ∈ I • , it holds E F (X y,N N t ; t ∈ [0, 1]) → E y [F (Y t ; t ∈ [0, 1])] as N → ∞.
Proof. Corollary 4.5 implies the convergence in the p-th Wasserstein distance

W p (P • (X y,N N • ) -1 , P y • (Y ) -1 ) → 0 as N → ∞.
It remains to apply Theorem 6.9 in [START_REF] Villani | of Grundlehren der Mathematischen Wissenschaften[END_REF] (also consult Definition 6.8 there).

Rates for approximating expectations

In practice one is often interested in approximating E y [f (Y 1 )] or E y [F (Y . )] for suitable functions f : I → R and path functionals F : C([0, 1], I) → R. We now discuss these questions using the notation introduced in Subsection 4.3.

Corollary 4.7. Suppose that Condition (C) is satisfied.

(i) For any Lipschitz function f :

I → R, there is a constant C(f ) ∈ (0, ∞) such that for all N ∈ N and y ∈ I • it holds E[f (X y,N N )] -E y [f (Y 1 )] ≤ C(f )N -1 4 .
(ii) For any path functional F : C([0, 1], I) → R that is Lipschitz with respect to the sup norm and for any ε ∈ (0, 1 4 ), there is a constant

C(f, ε) ∈ (0, ∞) such that for all N ∈ N and y ∈ I • it holds E F (X y,N N t ; t ∈ [0, 1]) -E y [F (Y t ; t ∈ [0, 1])] ≤ C(f, ε)N -( 1 4 -ε) .
This result immediately follows from Theorem 4.1 and Theorem 4.4 (also see (32)) applied with p = 1.

We finally discuss what can be said for non-Lipschitz functions f or path functionals F . We do not have rates in this case, but we do at least have convergence [START_REF] Engelbert | On solutions of one-dimensional stochastic differential equations without drift[END_REF] for bounded continuous path functionals F due to Theorem 1.1. We now show how to allow unbounded functionals here. Notice that Condition (C) is no longer assumed. Proposition 4.8. Let y ∈ I • and f : I → R be a continuous function satisfying (A) if r is inaccessible, then

lim x r |f (x)| q(y, x) = 0; (33) (B) if l is inaccessible, then lim x l |f (x)| q(y, x) = 0. ( 34
) Then Ef (X y,N N ) → E y f (Y 1 ) as N → ∞. (35)
This is a generalization of Proposition 2.11 of [START_REF] Ankirchner | Numerical approximation of irregular SDEs via Skorokhod embeddings[END_REF] to our present setting. We sketch the proof to make the paper self-contained.

Proof. By Lemma 2.2, the process q(y, Y t ) -(t ∧ H l,r (Y )), t ∈ [0, ∞), is a P y -local martingale. In particular, it holds

E y [q(y, Y σ n ∧τ N N )] = E y [σ n ∧ τ N N ∧ H l,r (Y )], n ∈ N,
for a localizing sequence of stopping times σ n ∞ and σ n = σ n ∧ n. Since q(•, •) is nonnegative, the Fatou lemma for the left-hand side and the monotone convergence theorem for the right-hand side yield

E y [q(y, Y τ N N )] ≤ E y [τ N N ] = 1.
A simple argument employing conditions (A) and (B) now shows that the family of random variables {f (Y τ N N ) : N ∈ N} is uniformly integrable under P y . Theorem 3.3 and the continuity of

f imply the convergence of f (Y τ N N ) to f (Y 1 ) in probability P y . It follows that Ef (X y,N N ) ≡ E y f (Y τ N N ) → E y f (Y 1 ) as N → ∞.
In a similar way one can generalize Proposition 2.16 of [START_REF] Ankirchner | Numerical approximation of irregular SDEs via Skorokhod embeddings[END_REF] to our present setting and obtain a convergence result for certain unbounded path functionals, but we omit further details.

Remark 4.9. (i) For any y ∈ I • , the function q(y, •) is convex and decreasing on [l, y] and convex and increasing on [y, r] (with q(y, y) = 0). Therefore, (33) is satisfied whenever

r = ∞ and |f (x)| x → 0 as x → ∞. Similarly, (34) is satisfied whenever l = -∞ and |f (x)| |x| → 0 as x → -∞.
(ii) The previous remark together with [START_REF] Ankirchner | WLLN for arrays of nonnegative random variables[END_REF] implies that (33) and (34) are equivalent to the same statements with y being replaced by any other z ∈ I • .

(iii) It is instructive to compare Proposition 4.8 and Corollary 4.6 in the situation when both are applicable, that is, under Condition (C). First, we note that under Condition (C) it holds q(y, x) ≥ c 2 (x -y) 2

i.e., q(y, x) has quadratic growth as x → ±∞. Moreover, the example of a Brownian motion shows that we cannot, in general, expect more than quadratic growth. Thus, if say r = ∞, Proposition 4.8 requires f to grow subquadratically at ∞ to get (35), while Corollary 4.6 allows for arbitrary polynomial growth at ∞. On the other hand, if say r < ∞ is inaccessible, then Proposition 4.8 allows for certain functions f that are unbounded in any neighborhood of r, while Corollary 4.6 requires f to be bounded in a neighborhood of r. Thus, neither of these two results is stronger than the other one.

On Condition (C)

All results in this section (except Proposition 4.8) require Condition (C). While it might be possible to relax Condition (C) to some extent, we cannot drop it completely, as shown by the next example. (37) [START_REF] Kotani | On a condition that one-dimensional diffusion processes are martingales[END_REF] establishes that Y is a strict P y -local martingale4 if and only if at least one of (36)-( 37) is satisfied. [START_REF] Gushchin | On the submartingale/supermartingale property of diffusions in natural scale[END_REF] On the other hand, the approximating Markov chain (X y,N k ) k∈N 0 is always a discretetime martingale (see [START_REF] Eberle | Sticky couplings of multidimensional diffusions with different drifts[END_REF] and also notice that each random variable X y,N k takes finitely many values, hence belongs to L 1 ). In particular, we always have E[X y,N N ] = y. Thus, under Condition (D),

E[X y,N N ] → E y [Y 1 ]
as N → ∞, hence, the claim of Corollary 4.7 (even with Lipschitz function f (x) = x) does not hold true. Therefore, the claims of Theorem 4.1, Theorem 4.4 and their corollaries (even for p = 1) are violated as well whenever Condition (D) is satisfied.

Reflecting boundaries

Throughout the preceding sections we assume that if a boundary point is accessible, then it is absorbing. In this section we explain how one can drop this assumption, i.e. how one can extend our functional limit theorem, Theorem 1.1, to Markov processes with reflecting boundaries.

The idea is to reduce the reflecting case to the inaccessible or absorbing case. Indeed, for every Markov process Z with reflecting boundaries one can find a Markov process Y on an extended state space and a Lipschitz function f such that Y has inaccessible or absorbing boundaries and Z d = f (Y ). We illustrate the reduction for a Markov process Z in natural scale with state space I Z = [l, ∞), where l > -∞ is a reflecting boundary. We denote by m Z the speed measure of Z. Since l is non-absorbing, it must hold that m Z ({l}) < ∞. Notice that m Z ({l}) = 0 corresponds to instantaneous reflection, while m Z ({l}) ∈ (0, ∞) to slow reflection.

To proceed with the construction, we first remark that it holds

m Z ((l, l + 1)) < ∞. (38)
Indeed, in terms of the Feller boundary classification (see

m Y (A) = m Z (A), for all A ∈ B(R), A ⊆ (l, ∞), m Y (A) = m Z (2l -A), for all A ∈ B(R), A ⊆ (-∞, l), m Y ({l}) = 2m Z ({l}),
which is a valid speed measure on I Y = R (i.e., (2) holds) due to (38). Then |Y -l| has the same distribution as Z (see Proposition VII.3.10 in [START_REF] Revuz | of Grundlehren der Mathematischen Wissenschaften[END_REF]).

Let X N be the Markov chain constructed in Section 1 such that (X N tN ) converges in distribution to (Y t ). Then, (|X N tN -l|) converges in distribution to Z.

In a similar way, a Markov process Z on a bounded interval I Z with endpoints l and r (l < r), where l ∈ I Z is reflecting and r is inaccessible (resp., absorbing), can be reduced to a Markov process Y with state space I Y , which is the interval with endpoints 2l -r and r, where both these endpoints are inaccessible (resp., absorbing).

A Markov process Z with two reflecting boundaries can be reduced to a Markov process with state space R. To explain this, suppose for simplicity that the state space of Z is [0, 1]. Define Y as the Markov process on R with speed measure m Y satisfying

m Y (A) = m Y (-A) = m Z (A), for all A ∈ B (0, 1) , m Y (A + 2k) = m Z (A), for all A ∈ B (-1, 0) ∪ (0, 1) and k ∈ Z, m Y ({2k}) = 2m Z ({0}), for all k ∈ Z, m Y ({2k + 1}) = 2m Z ({1}), for all k ∈ Z. Let f : R → [0, 1] be the periodic function with period 2 satisfying f (x) = |x|, x ∈ [-1, 1].
Then the process f (Y ) has the same distribution as Z (cf. Proposition VII.3.10 in [START_REF] Revuz | of Grundlehren der Mathematischen Wissenschaften[END_REF]). if y < 0 (x + = max{x, 0}, x -= -min{x, 0}) and to observe that, for any y ∈ R, the function q(y, •) has a kink at zero. We now determine the functions a N (y), N ∈ N, y ∈ R, of (7): Lemma 6.1. For all N ∈ N and y ∈ R it holds that

a N (y) =      σ √ N if |y| ≥ σ √ N , σ 1 N + |y| θ + σ 2θ 2 -σ 2θ if |y| < σ √ N .
Proof. It follows from the definition (3) of q that for all y ∈ R and a ∈ [0, ∞) it holds q(y, y + a) + q(y, y -a) =

Notice that for all y ∈ R the function a → q(y, y + a) + q(y, y -a), a ∈ [0, ∞), is strictly increasing. Hence, we only need to verify that q(y, y + a N (y)) + q(y, y -a

N (y)) = 2 N (41) for all y ∈ R. Assume first that |y| ≥ σ √ N . Then (41) is satisfied. Next assume that |y| < σ √ N . In this case it holds that a N (y) ≥ |y|. Moreover it holds that 1 σ 2 a N (y) 2 + 1 θ (a N (y) -|y|) = 1 N . (42)
This proves (41) in the case |y| < σ √ N . The proof is thus completed.

Theorem 1.1 implies that the Markov chains X N , N ∈ N, defined in [START_REF] Eberle | Sticky couplings of multidimensional diffusions with different drifts[END_REF] converge in distribution to Y as N → ∞.

[0, 1], F (x) = 1 M M i=1 1 (-∞,x] (X N,i N )
, where (X N,i N ) i∈{1,...,M } are M = 10 6 independent realizations of X N N with N = 1000, σ = 1 and θ = 1. Observe that a jump at 0 becomes apparent. This reflects the fact that the (weak) limit Y 1 of X N N is with positive probability equal to 0.

Brownian motion on [0, ∞) with slow reflection at 0

In this section we consider a Brownian motion on [0, ∞) with slow reflection at 0. Let σ, θ ∈ (0, ∞). According to Theorem IV.7.2 in [START_REF] Ikeda | Stochastic Differential Equations and Diffusion Processes[END_REF] the stochastic differential equation

dZ t = θ1 {Zt=0} dt + σ1 {Zt>0} dW t , Z 0 = 0, (43)
possesses a weak solution that is unique in law. However, it is worth noting that neither existence of a strong solution nor pathwise uniqueness hold for (43) (see [START_REF] Engelbert | Stochastic differential equations for sticky Brownian motion[END_REF] and references therein). The next result shows that Z is a regular diffusion on [0, ∞) and identifies the associated speed measure.

Lemma 6.2. The solution Z of (43) is a regular continuous strong Markov process in natural scale with state space I Z = [0, ∞) and with speed measure

m Z (dz) = 2 σ 2 λ(dz) + 1 θ δ 0 (dz). (44)
Proof. Strong Markov property of Z is implied by the uniqueness in law for (43). Clearly, Z is regular with state space I Z = [0, ∞) and in natural scale. By Itô's formula, we have

f (Z t ) = f (Z 0 ) + t 0 θf (0)1 {Zs=0} + σ 2 2 f (Z s )1 {Zs>0} ds + t 0 σf (Z s )1 {Zs>0} dW s for C 2 functions f : [0, ∞) → R.
Therefore, the generator A of Z takes the form

Af (z) = θf (0) if z = 0, σ 2 2 f (z) if z > 0 (45)
for f ∈ C 2 0 ([0, ∞)) (this means that the function itself and its first and second derivative vanish at infinity) satisfying the boundary condition

θf (0) = σ 2 2 f (0).
By Theorem VII.3.12 in [START_REF] Revuz | of Grundlehren der Mathematischen Wissenschaften[END_REF], we have Af (z) = d dm Z f (z) in the interior of the state space, i.e., for z > 0, while, by Proposition VII.3.13 in [START_REF] Revuz | of Grundlehren der Mathematischen Wissenschaften[END_REF], it holds f (0) = m({0})Af (0) on the boundary. Together with (45), this implies (44) and concludes the proof. σ 2 λ(dz) + 2 θ δ 0 (dz), i.e., Y is the process studied in Section 6.1 (cf. (39)). In particular, Z can be approximated by |X N |, N ∈ N, where X N are the Markov chains constructed in Section 6.1.

Warren [START_REF] Warren | Branching processes, the Ray-Knight theorem, and sticky Brownian motion[END_REF] determines for all t ∈ (0, ∞) the conditional law of Z t given the driving Brownian motion W . As a consequence, we obtain for all t ∈ (0, ∞) closed form representations of the cumulative distribution function and the expected value of Z t . The precise formulas are provided in Lemma 6.3 below, where we, without loss of generality, consider σ = 1. The notations P 0 for the probability measure and E 0 for the corresponding expectation operator emphasize that the formulas are given for the case Z 0 = 0. We use these formulas to analyze the empirical rate of convergence of our scheme. The results are presented in Figure 2. Lemma 6.3. Let Z be a solution of (43) with σ = 1. For every t ∈ (0, ∞) the cumulative distribution function F (•; t) : [0, ∞) → [0, 1] of Z t satisfies Proof. Fix t ∈ (0, ∞) throughout the proof. Lévy's distributional theorem implies W t + sup s∈[0,t] (-W s ) d = |W t | (see Theorem VI.2.3 in [START_REF] Revuz | of Grundlehren der Mathematischen Wissenschaften[END_REF]). Then it follows from Theorem 1 in [START_REF] Warren | Branching processes, the Ray-Knight theorem, and sticky Brownian motion[END_REF] that for all z ∈ [0, ∞) it holds P 0 [Z t ≤ z] = E 0 e -2θ(Wt+sup s∈[0,t] (-Ws)-z) + = E 0 1 [0,z) (|W t |) + e -2θ(|Wt|-z)

F Z (z; t) := P 0 [Z t ≤ z] = 2Φ z √ t -1 + 2e 2θ(z+θt) Φ -2θ √ t - z √ t , z ∈ [0, ∞), (
This completes the proof.

Lemma 3 . 1 .

 31 Let α ∈ [1, ∞), let y ∈ I • and let a ∈ (0, ∞) be such that [y -a, y + a] ⊆ I. Let τ = H y-a,y+a (Y ) be the first exit time of Y from (y -a, y + a). Then it holds that

Theorem 4 . 1 .

 41 Suppose that Condition (C) is satisfied and let p ∈ (0, ∞). Then there exists a constant C(p) ∈ (0, ∞) such that for all N ∈ N and y ∈ I • it holds that

Example 4 . 10 .

 410 Fix any starting point y ∈ I • . Notice that Y is a P y -local martingale due to our assumption that the boudaries are inaccessible or absorbing. Let us consider the conditions 3 r = ∞ and ∞ x m(dx) < ∞ (36) and l = -∞ and -∞ |x| m(dx) < ∞.

  ∨ |y|) -|y|).

Figure 1 Figure 1 :

 11 Figure 1: Left: Two trajectories of the approximation of the sticky Brownian motion. The black line depicts one realization of (X N n ) {n∈0,...,N } with N = 1000, σ = 1 and θ = 0.5. The gray line shows one realization of (X N n ) n∈{0,...,N } with N = 1000, σ = 1 and θ = 1. Both trajectories are generated by the same sample of random increments (ξ n ) n∈{1,...,N } . Observe that the smaller the value of θ is, the more the process sticks to 0. Right: Empirical distribution function of the approximation of the sticky Brownian motion. The figure depicts the function F : R → [0, 1], F (x) = 1

  It follows from Section 5 that Z d = |Y |, where Y is a diffusion in natural scale with state space I Y = R and speed measure m Y (dz) = 2

Figure 2 : 2 ( 1

 221 Figure 2: The parameter values are σ = 1 and θ = 1/2 for both plots. Left: Empirical rate of convergence of the distribution function.The circles depict the five data pointslog 2 (N ), log 2 1 M M i=1 1 [0,0.1] (|X N,i N |) -F Z (0.1; 1) , N = 2 6 , . . . , 2 10 , where F Z (0.1; 1) = P 0 [Z 1 ≤ 0.1] ≈ 0.5741 (see Lemma 6.3) and (X N,i N ) i∈{1,...,M } are M = 10 8 independent realizations of X N N .The straight line is the linear best fit. Its slope is approximately -0.62. Right: Empirical rate of convergence of the expected value. The circles depict the five data pointslog 2 (N ), log 2 1 M M i=1 |X N,i N | -E 0 [Z 1 ] , N = 2 6 , . . . , 2 10, where E 0 [Z 1 ] ≈ 0.3210 (see Lemma 6.3) and (X N,i N ) i∈{1,...,M } are M = 10 8 independent realizations of X N N . The straight line is the linear best fit. Its slope is approximately -0.59.

  complements this result by showing that (a) Y is not a P y -supermartingale if and only if (37) holds; (b) Y is not a P y -submartingale if and only if (36) holds. Now consider Condition (D) One of conditions (36)-(37) is satisfied, while the other one is violated. Notice that Conditions (C) and (D) exclude each other. The above statements (a)-(b) imply that Condition (D) is equivalent to the condition that Y is either a strict P y -supermartingale or a strict P y -submartingale. 5 If Y is a strict P y -supermartingale (resp., a strict P y -submartingale), then E y [Y 1 ] < y (resp., E y [Y 1 ] > y). In any case, E y [Y 1 ] = y under Condition (D).

  Table 15.6.2 in [18]), as the accessible boundary point l is reflecting, it can only be regular, which implies (38). Now let Y be a Markov process in natural scale with state space I Y = R and speed measure m Y satisfying

  -y 2 /2 dy is the cumulative distribution function of the standard normal distribution. Moreover, it holds that

											46)
	where Φ(x) = 2π e E 0 [Z t ] = x -∞ 1 √ 2t π -1 2θ	+	e 2θ 2 t θ	Φ(-2θ	√ t) = E 0 [|W t |] -	1 2θ	+	e 2θ 2 t θ	Φ(-2θ	√ t).	(47)

  1 [z,∞) (|W t |)This proves (46). Moreover, this implies that the density function of Z t starting in 0 satisfies ∈ (0, ∞). Observe that for all z ∈ (0, ∞) it holds

	This implies for all z ∈ (0, ∞) that
							F Z (z; t) = 4θe 2θ(z+θt) Φ -2θ	√ t -	z √ t	.	(50)
	This and Fubini's theorem prove that
	E 0 [Z t ] = = = =	∞ 4θe 2θ 2 t 0 zF Z (z; t) dz = √ -2θ √ t e -y 2 2 2π -∞ e 2θ 2 t θ √ -2θ √ t e -y 2 2 2π -∞ e 2θ 2 t θ Φ(-2θ √ t) -θ	4θe 2θ 2 t √ 2π -y √ 0 1 -e -2θ(y ∞ 0 t-2θt √ ze 2θz ze 2θz dz dy -2θ -∞ t+2θt) (2θ(y √ √ t-z √ t t + 2θt) + 1) dy e -y 2 2 dy dz 1 √ -∞ 2π -2θ √ t e -(y+2θ √ t) 2 2 (2θ √ t(y + 2θ √ t) + 1) dy
	= =	e 2θ 2 t θ e 2θ 2 t θ	Φ(-2θ Φ(-2θ	√ t) -√ t) -	1 √ 2π 1 θ 2θ -	0 -∞ √ 2 t √ 2π	e -y 2 2 (2θ 0 -∞ ye -y 2 √ ty + 1) dy 2 dy = e 2θ 2 t θ	Φ(-2θ	√	t) -	1 2θ	+	2t π	.
		= 2Φ	z √ t	-1 +	2 √ 2π	∞ z/ √	t	e -2θ( √	ty-z) e -y 2 2 dy
		= 2Φ	z √ t	-1 +	2 √ 2π	e 2θ(z+θt)	∞ z/ √	t	e -(y+2θ √ 2	t) 2	dy
		= 2Φ	z √ t	-1 + 2e 2θ(z+θt) Φ -2θ	√	t -	z √	t	.
	F Z (z; t) =	2 √ t	Φ		z √	t	+ 4θe 2θ(z+θt) Φ -2θ	√	t -	z √	t	-	2 √ t	e 2θ(z+θt) Φ -2θ	√ t -	z √ t
																(48)
	for all z e 2θ(z+θt) Φ -2θ	√ t -	z √ t	=	1 √ 2π	e 2θ(z+θt) e -	2θ	√ t+ z √ t 2	2	=	1 √ 2π	e -z 2 2t = Φ	z √	t	. (49)

Condition (C) supposed in Section 4 is not a regularity assumption. For instance, it is satisfied for the aforementioned sticky Brownian motion, hence, we obtain the rate of at least 1/4 for it. However,

The notation ∞ x m(dx) < ∞ is understood as ∞ z x m(dx) < ∞ for some (equivalently, for any) z ∈ I • . The notation -∞ |x| m(dx) < ∞ is understood in a similar way.

A strict local martingale is a local martingale that fails to be a martingale.

A strict supermartingale is a supermartingale that is not a martingale. A strict submartingale is understood in a similar way.