2. Definition of the DAG model

Let $G=(V,E)$ be a finite connected acyclic directed graph (DAG) where V is the vertex set and E is the edge set. If an edge $e \in E$ is directed from vertex x to vertex y we will write $e = \langle x, y \rangle$ and say that y is the head and x is the tail. A tangle is a DAG with two additional properties: first, there is a unique vertex which is not the tail in any edge—this is called the genesis vertex. Second, every vertex is the tail in at most two edges. The subset of vertices which are not the heads of any edges will be called the tips of the tangle.

We will define a stochastic growth model for the tangle. New transactions are created at the sequence of times $\{t_n = \lambda^{-1} n \,: \, n=1,2,\dots\}$, so the arrival rate of new transactions is $\lambda$. At time $t_n$, two tips $x_1(n)$ and $x_2(n)$ on the tangle are selected for the proof of work by the new transaction (it will be explained shortly how these tips are selected; it may happen that $x_1(n) = x_2(n)$). The proof of work lasts for a fixed length of time h. For simplicity we will assume that $\lambda$ is always chosen so that $\lambda h$ is an integer:

(2.1) \begin{eqnarray}m = \lambda h.\end{eqnarray}

At time $t_n + h = t_{n+m}$ the new transaction is added to the tangle as a tip $y_n$, and the two directed edges $\langle y_n, x_1(n) \rangle$ and $\langle y_n, x_2(n) \rangle$ are also added to the graph. This is the only mechanism by which the tangle grows (see Figure 2 for illustration).

Obviously the vertices $x_1(n)$ and $x_2(n)$ are no longer tips after time $t_n+h$; however, it may happen that these vertices had already ceased to be tips at an earlier time, owing to their being linked to some previous new transaction. We say that a tip is pending if it has been selected for proof of work by a transaction but has not yet been linked. We say that a tip is free if it is not pending. See Figure 3 for an example showing new vertices being added to the tangle.

Definition 2.1. We define the following quantities:

(2.2) \begin{align}\hspace*{-85pt}W_n = \mbox{number of pending tips at time $t_n$}, \end{align}

(2.3) \begin{align}\hspace*{-103pt}X_n = \mbox{number of free tips at time $t_n$}, \end{align}

(2.4) \begin{align}\hspace*{-73pt}L_n = W_n + X_n = \mbox{number of tips at time $t_n$}, \end{align}

(2.5) \begin{align}U_n = \mbox{number of free tips selected for proof of work at time $t_n$}.\end{align}

We have defined $U_n$ to be the number of the vertices $\{x_1(n), x_2(n)\}$ which are free at time $t_n$, so $U_n \in \{0,1,2\}$. After selection these free vertices immediately become pending vertices; hence they will never contribute to any of the subsequent values $U_{n+1}, U_{n+2}, \dots$. Furthermore at any time there are exactly m new transactions which are each in the process of carrying out their proof of work on two vertices on the graph (this holds because $m = \lambda h$ and we assume that the value of h is fixed and identical for all users). Therefore the total number of pending vertices at any time $t_n$ is the sum of $\{U_n, U_{n-1}, \dots, U_{n-m+1}\}$; that is,

(2.6) \begin{eqnarray}W_n = \sum_{j=n-m+1}^n U_j .\end{eqnarray}

We also have the evolution relations

(2.7) \begin{align}X_{n+1} &= X_n + 1 - U_{n+1}, \nonumber \\[3pt]L_{n+1} &= L_n + 1 - U_{n - m + 1},\end{align}

and the relation

(2.8) \begin{eqnarray}L_n = W_n + X_n.\end{eqnarray}

Note that the term ‘$+1$’ appears on the right sides of (2.7) because a new free tip is added to the tangle at each step. Also the term $ - U_{n+1}$ appears in $X_{n+1}$ because this is the number of free tips that are selected at the $(n+1)$th step, and the term $ - U_{n-m+1}$ appears in $L_{n+1}$ because this counts the number of vertices which cease being tips at the $(n+1)$th step. Finally, all tips which were pending at the $(n-m)$th step will no longer be tips at the nth step, and all of the m new arrivals in this interval will still be tips at the nth step; therefore, for all $n \ge m$,

(2.9) \begin{eqnarray}L_{n} = X_{n-m} + m.\end{eqnarray}

We will refer to $(W_n,X_n,L_n)$ as the tangle process. It follows from (2.9) that the process $\{L_n \}$ (for $n \ge m$) is in fact fully determined by $\{X_n \,{:}\, n \ge 0\}$.

We will discuss shortly how the processes $X_n$ and $L_n$ can be defined using appropriate initial conditions. For this purpose it will be convenient to use the evolution relations (2.7) starting at $n=0$. These relations imply that

(2.10) \begin{align}X_{n+1} &= X_0 + \sum_{i=0}^n (1 - U_{i+1}) \quad \mbox{ for all $n \ge 0$}, \nonumber \\L_{n+m+1} &= L_{m} + \sum_{i=0}^n (1 - U_{i+1}) \quad \mbox{ for all $n \ge 0$}.\end{align}

2.1. The random tip growth model

The remaining ingredient in the definition of the DAG model is the method of choosing vertices $x_1(n)$ and $x_2(n)$. We will assume in this paper that the tips $x_1(n)$ and $x_2(n)$ are chosen independently and uniformly from the set of tips, and we call this the random tip growth (RTG) model for the tangle process. Thus, the numbers $\{U_n\}$ are random variables whose distributions depend on the number of tips at time $t_n$. The RTG model is one of the tip selection algorithms discussed in [Reference Popov20], [Reference Ferraro, King and Shorten11], and it is expected that the fluid limit methods presented in this paper can be extended to those other tip selection algorithms.

We denote by $\mathcal{F}_n$ the $\sigma$-algebra generated by $\{U_1,\dots,U_n\}$:

(2.11) \begin{eqnarray}\mathcal{F}_n = \sigma \left(U_1,\dots,U_n \right).\end{eqnarray}

It follows from (2.10) that $X_n - X_0$ and $L_{n+m} - L_m$ are measurable with respect to $\mathcal{F}_n$. We also have the filtration relation

(2.12) \begin{eqnarray}\mathcal{F}_{n_1} \subset \mathcal{F}_{n_2} \quad \mbox{for all $n_1 < n_2$}.\end{eqnarray}

The conditional distribution of the random variable $U_{n+1}$ for the RTG model is

(2.13) \begin{align}\mathbb{P}(U_{n+1}=2\,|\, \mathcal{F}_n) &= \frac{X_n (X_n - 1)}{L_n^2}, \nonumber \\[2pt]\mathbb{P}(U_{n+1}=0\,|\, \mathcal{F}_n) &= \frac{W_n^2}{L_n^2}, \nonumber \\[2pt]\mathbb{P}(U_{n+1}=1\,|\, \mathcal{F}_n) &= \frac{2 W_n X_n + X_n}{L_n^2}.\end{align}

Note that

(2.14) \begin{eqnarray}\mathbb{E}[U_{n+1} \,|\, \mathcal{F}_n] = 2 \, \frac{X_n}{L_n} - \frac{X_n}{L_n^2}.\end{eqnarray}

It is clear that $(X_n,L_n)$ is not a Markov process, as the distribution of $L_{n+1}$ depends on $U_{n-m+1}$, which in turn depends on $(X_{n-m}, L_{n-m})$ through (2.13).

2.2. Generating the process from initial conditions

The stochastic process $(X_n,L_n)$ defined by (2.7) and (2.13) must be supplemented with initial conditions in order to be well-defined. This is done most easily by assigning values to the variables $(U_{-m+1},\dots,U_0)$ and $X_0$. Once these assignments have been made, the distribution of the process $(X_n, L_n)$ is determined for all $n \ge 0$, as will be explained below. In particular the variables $X_{-m},\dots,X_{-1}$ and $L_{-m},\dots,L_{-1}$ do not play any role, and we will ignore their values.

Let $(u_{-m+1},\dots,u_0)$ be a sequence with $u_i \in \{0,1,2\}$ for all $i=-m+1,\dots,0$, and let $\xi_0 \ge 1$ be an integer. Then we assign as initial conditions

(2.15) \begin{align}U_i &= u_i, \qquad i=-m+1,\dots,0, \nonumber \\[2pt] W_0 &= \sum_{i=-m+1}^0 u_i, \nonumber \\[2pt] X_0 &= \xi_0, \nonumber \\[2pt] L_0 &= X_0 + W_0 = \xi_0 + \sum_{i=-m+1}^0 u_i .\end{align}

It follows from (2.15) that $L_0 \ge \xi_0 \ge 1$, so the distribution of $U_{1}$ is well-defined. Similarly $L_n \ge X_n \ge 1$, so the distribution of $U_{n+1}$ is well-defined for all $n \ge 0$.

From (2.10) and (2.15) we also deduce that

(2.16) \begin{eqnarray}L_{1} = \xi_0 + 1 + \sum_{i=-m+2}^0 u_i ,\end{eqnarray}

and so $L_{1}$ is also fixed by the initial conditions. The same is true for $L_2,\dots,L_m$, and we have the formula

(2.17) \begin{eqnarray}L_{j} = \xi_0 + j + \sum_{i=-m+j+1}^0 u_i \qquad \mbox{for $j=0,\dots,m$}.\end{eqnarray}

3. The fluid limit

Given the process $\{X_n, L_n\}$ we rescale variables and define for all $t > 0$

(3.1) \begin{eqnarray}A^{(\lambda)}(t) = \lambda^{-1} \, X_{n(t)}, \qquad B^{(\lambda)}(t) = \lambda^{-1} \, L_{n(t)}, \qquad\mbox{where $n(t) = \lfloor \lambda \, t \rfloor$}.\end{eqnarray}

The variables $(A^{(\lambda)}(t), B^{(\lambda)}(t))$ are piecewise constant in the intervals $[t_n,t_{n+1})$, and change by at most $\pm \lambda^{-1}$ at each time $t_n$. Therefore it is reasonable that in the limit $\lambda \rightarrow \infty$ these variables will converge to continuous functions a(t) and b(t). Furthermore after rescaling (2.7) the evolution equations become

(3.2) \begin{eqnarray}\frac{A^{(\lambda)}(t_{n+1}) - A^{(\lambda)}(t_n)}{t_{n+1} - t_n} = 1 - U_{n+1} , \nonumber \\[2pt] \frac{B^{(\lambda)}(t_{n+1}) - B^{(\lambda)}(t_n)}{t_{n+1} - t_n} = 1 - U_{n -m+1}.\end{eqnarray}

The left sides of (3.2) are expected to converge to a’(t) and b’(t) as $\lambda \rightarrow \infty$, so it is reasonable to expect that the fast variations on the right side will be averaged out in the limit, leaving the expected values of the variables $U_{n+1}$ and $U_{n-m+1}$. From (2.14) we have

(3.3) \begin{eqnarray}\mathbb{E}[U_{n+1} \,|\, \mathcal{F}_n] =2 \, \frac{A^{(\lambda)}(t_n)}{B^{(\lambda)}(t_n)} - \lambda^{-1} \, \frac{A^{(\lambda)}(t_n)}{B^{(\lambda)}(t_n)} \simeq 2 \, \frac{A^{(\lambda)}(t_n)}{B^{(\lambda)}(t_n)} \simeq 2 \, \frac{a(t)}{b(t)}\end{eqnarray}

and similarly

(3.4) \begin{eqnarray}\mathbb{E}[U_{n-m+1} \,|\, \mathcal{F}_n] \simeq 2 \, \frac{A^{(\lambda)}(t_n - h )}{B^{(\lambda)}(t_n - h)} \simeq 2 \, \frac{a(t - h)}{b(t - h)}.\end{eqnarray}

Assuming that the right sides of (3.2) converge to these average values, we are led to the following pair of coupled delay differential equations for the fluid limit:

(3.5) \begin{eqnarray}\frac{d a}{d t} = 1 - 2\, \frac{a(t)}{b(t)}, \qquad \frac{d b}{d t} = 1 - 2\, \frac{a(t - h)}{b(t - h)}.\end{eqnarray}

The second equation implies that $b(t) = a(t-h) + c$ for some constant c, and the value of c will be identified in Lemma 3.1.

3.1. Delay differential equations

The equations (3.5) must be supplemented with suitable initial conditions. We will say that the combination $\alpha = (a(0), \{u(t) \,{:} -h \le t \le 0\})$ is a DDE initial condition if $a(0) > 0$, u(t) is integrable, and

(3.6) \begin{eqnarray}0 \le u(t) \le 2 \quad \mbox{for all $-h \le t \le 0$}.\end{eqnarray}

These initial conditions can be used to define a solution of the fluid equations (3.5) for $t \ge 0$ using the method of steps [Reference Driver8] in the same way as the initial conditions (2.15) were used to construct the tangle process. The idea is that the function u(t) plays the same role as the initial sequence $\{u_i\}$ for the discrete process. Therefore we first define the initial value b(0) as

(3.7) \begin{eqnarray}b(0) = a(0) + \int_{-h}^0 u(s) \, d s,\end{eqnarray}

and we then define b(t) for $0 \le t \le h$ as the solution of the delay equation

(3.8) \begin{eqnarray}\frac{d b}{d t} = 1 - u(t-h).\end{eqnarray}

This leads to the solution

(3.9) \begin{align}b(t) &= b(0) + t - \int_{-h}^{t-h} u(s) \, d s \nonumber \\[2pt] &= a(0) + t + \int_{t-h}^0 u(s) \, d s \quad \mbox{for $0 \le t \le h$}.\end{align}

We then compute a(t) for $t \in [0,h]$ as the solution of the equation

(3.10) \begin{eqnarray}\frac{d a}{d t} = 1 - 2 \frac{a(t)}{b(t)},\end{eqnarray}

which gives

(3.11) \begin{eqnarray}a(t) = Q(0,t)^{-1} a(0) + Q(0,t)^{-1} \, \int_{0}^t Q(0,s) \, d s, \quad \mbox{for $t \in [0,h]$},\end{eqnarray}

where

(3.12) \begin{eqnarray}Q(x,y) = \exp \left(2 \int_{x}^y b(s)^{-1} \, d s\right).\end{eqnarray}

Note that (3.9) implies $b(t) \ge a(0) > 0$ for all $0 \le t \le h$, so (3.12) is well-defined for $(x,y) = (0,t)$ with t in this interval, and (3.11) also implies that $a(t) > 0$ for all $0 \le t \le h$. The equation (3.9) also implies that $b(h) = a(0) + h$. Having obtained the functions (a(t), b(t)) in the interval [0, h], we then extend the solutions to the interval [h, 2h] by first defining

(3.13) \begin{eqnarray}b(t) = a(t-h) + h \quad \mbox{for all $h \le t \le 2h$},\end{eqnarray}

and then solving the differential equation for a(t) to obtain

(3.14) \begin{eqnarray}a(t) = Q(h,t)^{-1} a(h) + Q(h,t)^{-1} \, \int_{h}^t Q(h,s) \, d s \quad \mbox{for $h \le t \le 2h$}.\end{eqnarray}

From (3.13) we have $b(t) \ge h$, and thus Q(h, t) is well-defined for $h \le t \le 2h$ and again implies positivity of a(t). This construction can be continued in the same way for subsequent intervals $[2h,3h],\dots$, and produces a solution of the equations (3.5) for all $t > h$. We collect our results about this solution in the following lemma, which will be proved in Section 8.

Lemma 3.1. Let $\alpha$ be a DDE initial condition. There are unique functions (a(t), b(t)) defined for all $t > 0$ which satisfy the equations (3.9) and (3.11) in the interval [0, h], and which satisfy the differential equations (3.5) for all $t > h$. For $t \ge h$ the solutions also satisfy the following conditions:

(3.15) \begin{eqnarray}\hspace*{-75pt}(1) &&\qquad a(t) \ge 0; \end{eqnarray}

(3.16) \begin{eqnarray}\hspace*{-33pt}(2) &&\qquad b(t) = h + a(t-h); \end{eqnarray}

(3.17) \begin{eqnarray}\hspace*{-73pt}(3) &&\qquad b(t) \ge h; \end{eqnarray}

(3.18) \begin{eqnarray}(4) &&\qquad b(t) - a(t) = \int_{t-h}^t 2 \frac{a(s)}{b(s)} \, d s; \end{eqnarray}

(3.19) \begin{eqnarray}\hspace*{-27pt}(5) &&\qquad 0 \le b(t) - a(t) \le 2h.\end{eqnarray}

3.2. Fluid limit: initial conditions for the tangle from DDE initial condition

Let $\alpha$ be a DDE initial condition. As Lemma 3.1 shows, $\alpha$ provides the necessary information to generate a unique solution of the delay equations (3.5). We will now show that $\alpha$ can be used to generate the initial conditions for a tangle process. Recall that $L_0,\dots,L_{m}$ are determined by the initial conditions $\xi_0,u_{-m+1},\dots,u_0$ through the relation (2.17), and that the function $\{b(t) \,:\, 0 \le t \le h\}$ is determined by $a(0), \{u(s)\,{:}\,-h \le s \le 0\}$ through the formula (3.9). We will choose the initial values $u_{-m+1},\dots,u_0$ for the tangle process depending on the function u(s) in such a way that the difference $B^{(\lambda)}(t) - b(t)$ is small for all $t \in [0,h]$, where $B^{(\lambda)}(t)$ is the rescaled variable defined in (3.1). Define the set of all initial value sequences:

(3.20) \begin{eqnarray}\mathcal{S}(m) = \{v = (v_{-m+1},\dots,v_0) \,: \, v_i \in \{0,1,2\}, \, i={-m+1},\dots,0\}.\end{eqnarray}

Definition 3.1. Let $\alpha = (a(0), \{u(s) \,{:} -h \le s \le 0\})$ be a DDE initial condition, and let $b_{\alpha}(t)$ be defined for $0 \le t \le h$ by the formula (3.9). Let $\xi_{\alpha} = \max (\lfloor \lambda a(0) \rfloor, 1 )$. Given an initial condition $(\xi_{\alpha}, v)$ for the tangle process, where $v \in \mathcal{S}(m)$, let $\{ B_v^{(\lambda)}(t) \,:\, 0 \le t \le h \}$ be given by (3.1), where $L_0,\dots,L_{m}$ are defined by the formula (2.17) with $\xi_0 = \xi_{\alpha}$ and $u_i = v_i$. Define

(3.21) \begin{eqnarray}F(\alpha, \lambda) = \{v \in \mathcal{S}(m) \,{:}\, \sup_{0 \le n \le m} | B_v^{(\lambda)}(t_n) - b_{\alpha}(t_n) | \le 4 h^{1/2} \lambda^{-1/2} + \lambda^{-1} \}.\end{eqnarray}

Lemma 3.2. The set $F(\alpha, \lambda)$ is non-empty.

The result of Lemma 3.2, which will be proved in Section 8, implies that for each DDE initial condition it is possible to define initial conditions for the tangle process so that $B^{(\lambda)}(t) - b(t)$ is small for all $t \in [0,h]$. This will allow us to prove that the difference $B^{(\lambda)}(t) - b(t)$ is small for all t, as stated in Theorem 4.2.

4. Statement of results

The first result establishes ergodicity for the process $\{X_n\}$. We will write $\psi = (u_{-m+1},\dots,u_0;\ \xi_0)$ to denote a set of initial conditions as described in (2.15) in Section 2.2, and write $\mathbb{P}_{\psi}(\!\cdot\!)$ for the probability distribution of $\{X_n \,{:}\, n \ge 0\}$ when the process is created with initial condition $\psi$.

Theorem 4.1. There is a unique stationary distribution $\pi$ such that

(4.1) \begin{eqnarray}\mathbb{P}_{\psi}(X_n = k) \rightarrow \pi(k) \quad \text{as $n \rightarrow \infty$, for all $k = 1,2,\dots$, and for all $\psi$}.\end{eqnarray}

The next result concerns the limiting behavior of the process when the arrival rate $\lambda \rightarrow \infty$.

Theorem 4.2. Let $\alpha$ be a DDE initial condition, and let $(a_{\alpha}(t),b_{\alpha}(t))$ be the associated solutions of the fluid equations (3.5) as described in Lemma 3.1. Let $v \in F(\alpha, \lambda)$, and let $(A_v^{(\lambda)}(t), B_v^{(\lambda)}(t))$ be the rescaled tangle process with initial conditions $(\xi_{\alpha},v)$ as described in Sections 2.2 and 3.2. For all $T \ge h$, and for all $\delta > 0$, there is a constant $C < \infty$ (depending on $T,\alpha$) and $\lambda_0 < \infty$ (depending on $T, \delta,\alpha$) such that for all $\lambda \ge \lambda_0$

(4.2) \begin{eqnarray}\mathbb{P} \bigg( \sup_{h \le t \le T} | B_v^{(\lambda)}(t) - b_{\alpha}(t) | > \delta \bigg) \le\mathbb{P} \bigg( \sup_{0 \le t \le T} | A_v^{(\lambda)}(t) - a_{\alpha}(t) | > \delta \bigg) \le C \, \lambda^{-1} \, \delta^{-2}.\end{eqnarray}

Remark. Theorem 4.2 confirms that the rescaled processes $(A^{(\lambda)}(t), B^{(\lambda)}(t))$ converge in probability to the deterministic solutions of the delay equations as $\lambda \rightarrow \infty$ for all t in the interval [0, T]. This kind of behavior is familiar for Markov jump processes. One novelty of Theorem 4.2 is that although the processes are not Markov, because of the delay time h, nevertheless the same kind of limiting behavior holds, albeit with the more complicated delay differential equation.

The proof of Theorem 4.2 relies on martingale techniques. The constants C and $\lambda_0$ that appear in the theorem depend on $\alpha$, the initial conditions for the process. Simulations of the tangle process [Reference Ferraro, King and Shorten10] have shown that the delay equations (3.5) give an accurate representation of the tangle even for relatively small values of $\lambda$.

The next result shows that the solution of the delay equation (3.5) converges to a constant as $t \rightarrow \infty$.

Theorem 4.3. Let $\alpha$ be a DDE initial condition, and let $(a_{\alpha}(t),b_{\alpha}(t))$ be the associated solutions of the fluid equations (3.5) as described in Lemma 3.1. Define

(4.3) \begin{eqnarray}C_1 &=& \sup_{0 \le s \le h} |a_{\alpha}(s) - h|, \nonumber \\[3pt] \kappa(u) &=& \max \left\{\frac{3}{4}, \, \exp \left( - \frac{h}{3(u + h)}\right) \right\}, \qquad u \ge 0, \nonumber \\[3pt] \mu &=& - \frac{1}{2 h} \log (\kappa(C_1/2)).\end{eqnarray}

Then for all $t \ge 3 h$,

(4.4) \begin{eqnarray}| b(t + h) - 2 h | = | a(t) - h | \le C_1 \, \kappa(C_1/2)^{-3/2} \, e^{ - \mu t}.\end{eqnarray}

Theorem 4.3 shows that the solutions of the delay equation converge exponentially to their stationary values with rate at least $\mu$. This limiting behavior shows that the number of tips behaves as $2 \lambda h$ to leading order for large arrival rates.

5. Proof of Theorem 4.1

Theorem 4.1 will be proved by embedding the process $\{X_n\}$ in a discrete Markov chain $\{\mathcal{X}_n\}$ and using standard techniques to prove ergodicity of $\{\mathcal{X}_n\}$. We define the extended state space

(5.1) \begin{align}\Omega &= \{ v = (v_0,v_1,\dots,v_m) \in \mathbb{Z}^{m+1} \,|\, v_i \ge 1, \, (i=0,\dots,m),\nonumber\\[3pt] &\qquad |v_i - v_{i+1}| \le 1, \, (i=0,\dots,m-1) \},\end{align}

and for $n \ge m$ we define the $\Omega$-valued process

(5.2) \begin{eqnarray}\mathcal{X}_n = (X_{n-m},X_{n-m+1},\dots,X_n).\end{eqnarray}

The transition matrix for $\mathcal{X}_n$ is defined by

(5.3) \begin{eqnarray}\mathbb{P}(\mathcal{X}_{n+1}= v \,|\, \mathcal{X}_{n}= u) =\begin{cases} \mathbb{P}(X_{n+1} = v_{m} \,|\, \mathcal{X}_{n}= u) & \text{if $v_0=u_1,\dots,v_{m-1}=u_m$}, \cr0 & \text{else.}\end{cases}\end{eqnarray}

The conditional distribution of $X_{n+1}$ is determined by $X_n$ and $X_{n-m}$, as shown in (2.7), (2.8), (2.9), and (2.13), and these values are determined by $\mathcal{X}_n$. Hence $\{\mathcal{X}_n\}$ is a Markov chain on $\Omega$. Let $\omega$ denote the state

(5.4) \begin{eqnarray}\omega = (m,m,\dots,m) \in \Omega .\end{eqnarray}

Every state in $\Omega$ communicates with $\omega$ (meaning that for every $v \in \Omega$ there is a path with positive probability from v to $\omega$, and vice versa), so the chain is irreducible. Furthermore $\mathbb{P}(\mathcal{X}_{n+1}= \omega \,|\, \mathcal{X}_{n}= \omega) > 0$; hence the chain is also aperiodic. Shortly we will prove the existence of a unique stationary distribution $\sigma$ for $\{\mathcal{X}_n\}$. Assuming this for the moment, a standard coupling argument can be applied to show that for any initial condition $\psi$ and every state $v \in \Omega$,

(5.5) \begin{eqnarray}\mathbb{P}_{\psi}(\mathcal{X}_n = v) \rightarrow \sigma(v) \quad \text{as $n \rightarrow \infty$}.\end{eqnarray}

We define for each $k \ge 1$

(5.6) \begin{eqnarray}\mathcal{N}(k) = \{ v \in \Omega \,|\, v_m = k\},\end{eqnarray}

and note that

(5.7) \begin{eqnarray}\mathbb{P}_{\psi}(X_n = k) = \sum_{v \in \mathcal{N}(k)} \mathbb{P}_{\psi}(\mathcal{X}_n = v).\end{eqnarray}

We also define

(5.8) \begin{eqnarray}\pi(k) = \sum_{v \in \mathcal{N}(k)} \sigma(v),\end{eqnarray}

and hence immediately deduce the desired convergence result

(5.9) \begin{eqnarray}\mathbb{P}_{\psi}({ X}_n = k) \rightarrow \pi(k) \quad \text{as $n \rightarrow \infty$}.\end{eqnarray}

In order to prove the existence of a unique stationary distribution $\sigma$ for $\{\mathcal{X}_n\}$, we will prove that the chain is positive recurrent. We will use the following lemma.

Lemma 5.1. Recall the definition of the state $\omega$ (5.4). There are positive constants $\gamma$, c such that for all $u, v \in \Omega$ with $u_m > 4 m, \, v_m \le 4 m$, and all $n \ge m$,

(5.10) \begin{eqnarray}\mathbb{P}(\mathcal{X}_{n+4m} = \omega \,|\, \mathcal{X}_n = v) \ge \gamma\end{eqnarray}

and

(5.11) \begin{eqnarray}\mathbb{E}_{\psi}[X_{n+1} \,|\, \mathcal{X}_n = u] \le u_m - c .\end{eqnarray}

Lemma 5.1 will be proved in Section 8. We now apply the result to prove that the chain is positive recurrent. First, (5.10) implies that the subset $A = \{v \in \Omega \,|\, v_m \le 4m\}$ is a small set [Reference Baxendale3]: let $\mu_{\omega}$ be the atom at $\omega$, and let $\mathbb{P}_v$ denote the distribution of $\mathcal{X}$ with initial value $\mathcal{X}_0 = v$; then

(5.12) \begin{eqnarray}\mathbb{P}_v(\mathcal{X}_{4m} \in B) \ge \gamma \mu_{\omega}(B)\end{eqnarray}

for all $B \subset \Omega$. Second, (5.11) implies that $\mathbb{E}_{\psi}[V(\mathcal{X}_{n+1}) \,|\, \mathcal{X}_n = u] \le V(u) - c$ for $u \in A^c$ where $V(u) = u_m$ (and of course V is uniformly bounded on A). We now apply Proposition 2.3 from [Reference Baxendale3] (which is a version of Theorem 9.1 in Tweedie [Reference Tweedie23]) to deduce that the chain is positive recurrent. So in particular the chain has a unique stationary distribution $\sigma$, as required.

6. Proof of Theorem 4.2

Theorem 4.2 will be proved using standard martingale techniques, as presented, for example, in [Reference Darling and Norris7]. For convenience we will drop the subscripts v, $\alpha$ on the variables. We assume that $\lambda$ is sufficiently large so that $\xi_{\alpha} = \lambda a(0) \ge 1$. Define

(6.1) \begin{eqnarray}l = \min (h, a(0)) .\end{eqnarray}

The quantity l will appear in many of the bounds derived later in this proof, and will represent the effect of the initial conditions on the constants C and $\lambda_0$ appearing in Theorem 4.2. It follows from (2.17) and (2.9) that

(6.2) \begin{eqnarray}B^{(\lambda)}(t) \ge l \qquad \mbox{for all $t \ge 0$},\end{eqnarray}

and from (3.9) and (3.13) that

(6.3) \begin{eqnarray}b(t) \ge l \qquad \mbox{for all $t \ge 0$}.\end{eqnarray}

Define for $t \in [0,T]$

(6.4) \begin{eqnarray}g(t) = \sup_{0 \le s \le t} |A^{(\lambda)}(s) - a(s)| ,\end{eqnarray}

so that the quantity of interest in Theorem 4.2 is $\mathbb{P}(g(T) > \delta)$.

We next derive the first inequality in (4.2). Recall from (3.15) that $b(t) = a(t - h) + h$ for all $t \ge h$, and from (2.9) that $L_{n} = X_{n-m} + m$ for all $n \ge m$. Therefore if $t \ge h$ and $t \in [t_n,t_{n+1})$ we have

(6.5) \begin{align}B^{(\lambda)}(t) - b(t) &= B^{(\lambda)}(t_n) - b(t) \nonumber \\[3pt]&= A^{(\lambda)}(t_{n-m}) - a(t-h) \nonumber \\[3pt]&= A^{(\lambda)}(t - h) - a(t-h),\end{align}

and therefore (since $g(\!\cdot\!)$ is non-decreasing)

(6.6) \begin{eqnarray}\sup_{h \le s \le t} |B^{(\lambda)}(s) - b(s)| = g(t- h) \le g(t) .\end{eqnarray}

This establishes the first inequality in (4.2). The following lemma extends the bound (6.6) to the interval [0, t].

Lemma 6.1. For all $t \ge h$,

(6.7) \begin{eqnarray}\sup_{0 \le s \le t} | B^{(\lambda)}(s) - b(s) | \le g(t) + 6 h^{1/2} \lambda^{-1/2}.\end{eqnarray}

Lemma 6.1 will be proved in Section 8. Next we will derive a bound for the quantity $A^{(\lambda)}(t) - a(t)$. For all $j \ge 0$ we define

(6.8) \begin{align}\hspace*{-28pt}G_{j+1} = X_{j+1} - X_j - \mathbb{E}[1 - U_{j+1} \,|\, \mathcal{F}_j] , \end{align}

(6.9) \begin{align}H_{j+1} = \mathbb{E}[1 - U_{j+1} \,|\, \mathcal{F}_j] - \lambda \, (a(t_{j+1}) - a(t_j)) .\end{align}

Then since $X_0 = \lambda a(0) = \lambda a(t_0)$ we have

(6.10) \begin{align}A^{(\lambda)}(t_n) - a(t_n) &=\lambda^{-1} \, (X_n - X_0) - (a(t_n) - a(t_0)) \nonumber \\[3pt]&= \lambda^{-1} \, \sum_{j=0}^{n-1} \left(G_{j+1} + H_{j+1} \right).\end{align}

The sum $\sum_{j=0}^{n-1} G_{j+1}$ is a martingale, and we will use this fact to bound the probability that it grows too large. The following bounds are derived in Section 8.

Lemma 6.2. We have

(6.11) \begin{eqnarray}\mathbb{P}\bigg( \sup_{0 \le n \le \lfloor \lambda T \rfloor} \bigg|\lambda^{-1} \, \sum_{j=0}^{n-1} G_{j+1} \bigg| \ge \theta \bigg) \le4 \, \theta^{-2} \, \lambda^{-1} \, T.\end{eqnarray}

Lemma 6.3. We have

(6.12) \begin{eqnarray}\lambda^{-1} \, \left| \sum_{j=0}^{n-1} H_{j+1} \right| \le 4 \, l^{-1} \, \lambda^{-1} \, \sum_{j=0}^{n-1} g(t_{j+1}) + 13 \, l^{-1} \, h^{ 1/2} \, \lambda^{-1/2} \, t_n\nonumber \\[3pt]\le 4 \, l^{-1} \, \lambda^{-1} \, \sum_{j=0}^{n-1} g(t_{j+1}) + 13 \, l^{-1} \, h^{ 1/2} \, \lambda^{-1/2} \, T.\end{eqnarray}

We will apply the bounds in Lemmas 6.2 and 6.3 to (6.10). Define the event

(6.13) \begin{eqnarray}E = \left\{\sup_{0 \le n \le \lfloor \lambda T \rfloor} \left|\lambda^{-1} \, \sum_{j=0}^{n-1} G_{j+1} \right| < \theta \right\},\end{eqnarray}

so that we have

(6.14) \begin{eqnarray}\mathbb{P}(E) \ge 1 - 4 \, \theta^{-2} \, \lambda^{-1} \, T .\end{eqnarray}

Combining (6.10), (6.11), and (6.12), it follows on the event E that for any $0 \le n \le \lfloor \lambda T \rfloor$,

(6.15) \begin{eqnarray}| A^{(\lambda)}(t_n) - a(t_n) | \le \rho + 4 \, l^{-1} \, \lambda^{-1} \, \sum_{j=0}^{n-1} g(t_{j+1}),\end{eqnarray}

where

(6.16) \begin{eqnarray}\rho = \theta + 13 \, l^{-1} \, h^{ 1/2} \, \lambda^{-1/2} \, T .\end{eqnarray}

Since $g(t) \ge 0$, and (6.15) holds for all $0 \le n \le \lfloor \lambda T \rfloor$, this also implies that

(6.17) \begin{eqnarray}\sup_{0 \le k \le n} | A^{(\lambda)}(t_k) - a(t_k) | \le \rho + 4 \, l^{-1} \, \lambda^{-1} \, \sum_{j=0}^{n-1} g(t_{j+1}) .\end{eqnarray}

Furthermore if $t \in [h,T]$ and $t \in [t_k,t_{k+1})$ we have

\begin{align*}| A^{(\lambda)}(t) - a(t) | &= | A^{(\lambda)}(t_k) - a(t_k) + a(t_k) - a(t)| \\[3pt]& \le | A^{(\lambda)}(t_k) - a(t_k)| + |a(t_k) - a(t)| \\[3pt]& \le | A^{(\lambda)}(t_k) - a(t_k)| + (t - t_k) \\[3pt]& \le | A^{(\lambda)}(t_k) - a(t_k)| + \lambda^{-1},\end{align*}

where we used the bound $|a'(s)| \le 1$ for all $s > 0$ (which follows from (3.5)). Therefore, on the event E,

(6.18) \begin{eqnarray}g(t_n) \le\sup_{0 \le k \le n} | A^{(\lambda)}(t_k) - a(t_k) | + \lambda^{-1}\le \rho + \lambda^{-1} + 4 \, l^{-1} \, \lambda^{-1} \, \sum_{j=0}^{n-1} g(t_{j+1}).\end{eqnarray}

Now applying the discrete Gronwall inequality [Reference Agarwal1] to (6.18) we deduce that on the event E, for all $0 \le n \le \lfloor \lambda T \rfloor$,

(6.19) \begin{eqnarray}g(t_n) \le (\rho + \lambda^{-1}) \, e^{4 \, l^{-1} \, \lambda^{-1} \, n} \le ( \rho + \lambda^{-1}) \, e^{4 \, l^{-1} \, T}.\end{eqnarray}

Given $\delta > 0$ we choose

(6.20) \begin{equation}\hspace*{-90pt}\theta = \frac{\delta}{3} \, e^{ - 4 \, l^{-1} \, T}, \end{equation}

(6.21) \begin{align}\lambda_0 = \max \left\{\theta^{-1}, \left(13 \, \theta^{-1} \, l^{-1} \, h^{1/2} \,T\right)^2 \right\}.\end{align}

Then for $\lambda \ge \lambda_0$ we have $\rho + \lambda^{-1} \le 3 \, \theta$ and

(6.22) \begin{eqnarray}( \rho + \lambda^{-1}) \, e^{4 \, l^{-1} \, T} \le \delta ,\end{eqnarray}

and hence (6.19) implies that $g(T) \le \delta$ on the event E. Therefore

(6.23) \begin{eqnarray}\mathbb{P}\left(g(T) > \delta \right)\le 1 - \mathbb{P}(E) \le 4 \, \theta^{-2} \, \lambda^{-1} \, T ,\end{eqnarray}

and this completes the proof with

(6.24) \begin{eqnarray}C = 36 \, e^{ 8 \, l^{-1} \, T} \, T .\end{eqnarray}

7. Proof of Theorem 4.3

Recall the delay equation (3.5) for a(t). Applying Lemma 3.1 we get

(7.1) \begin{eqnarray}\frac{d a}{d t} = 1 - 2\, \frac{a(t)}{a(t - h) + h}.\end{eqnarray}

Given the solution a(t) for $t \le T$, (7.1) is a linear equation for a(t) in the interval $[T,T+h]$, and we can write down an explicit solution in terms of the solution in the interval $[T-h,T]$. Then by translating coordinates the equation (7.1) can be viewed as providing a map from the space of functions on [0, h] into itself. In order to prove (4.4) we will consider instead $a(t) - h$, so define for $t \in [0,h]$

(7.2) \begin{eqnarray}x(t) = \frac{a(T-h+t) - h}{2}, \qquad y(t) = \frac{a(T+t) - h}{2};\end{eqnarray}

then from (7.1) we derive

(7.3) \begin{eqnarray}\frac{d y}{d t} = \frac{x(t) - 2 y(t)}{2 (x(t) + h)}, \qquad y(0) = x(h).\end{eqnarray}

As explained above, we will view (7.3) as a map from x to y. Define the functional $\mathcal{M}$ as the map which takes x to the solution y of the equation (7.3):

(7.4) \begin{eqnarray}\mathcal{M}(x)(t) = y(t), \qquad 0 \le t \le h,\end{eqnarray}

with the norms

(7.5) \begin{eqnarray}\| x \| = \sup_{0 \le t \le h} |x(t)|, \qquad \| y \| = \sup_{0 \le t \le h} | \mathcal{M}(x)(t) | .\end{eqnarray}

We will prove the following bounds: for all differentiable x,

(7.6) \begin{align}\| \mathcal{M}(x) \| & \le \| x \| , \nonumber \\[3pt]\| \mathcal{M}(\mathcal{M}(x)) \| & \le \kappa(\| x \|) \, \| x \| ,\end{align}

where $\kappa$ was defined in (4.3). Before proving (7.6) we note that it implies the bound (4.4): indeed for $t \ge 4 h$, there is an integer $n \ge 2$ such that $(2 n - 1) h \le t < (2 n+1) h$. The first inequality in (7.6) implies that

(7.7) \begin{eqnarray}\sup_{2 n h \le s \le (2 n + 1) h} \, | a(s) - h | \le \sup_{(2 n - 1) h \le s \le 2 n h} \, | a(s) - h |.\end{eqnarray}

Define $x_0(s) = (a(s) - h)/2$ for $s \in [h,2h]$. Then for any $t \in [(2 n - 1) h, (2 n+1) h]$ the inequalities (7.6) and (7.7) imply

(7.8) \begin{align}| a(t) - h | &\le \sup_{(2 n - 1) h \le s \le 2 n h} \, | a(s) - h | \nonumber \\[3pt]&= 2 \, \| \mathcal{M}^{\, \circ (2 n-2)} (x_0) \| \nonumber \\[3pt]& \le 2 \, (\kappa(\| x_0 \|))^{n - 1} \, \| x_0 \| \nonumber \\[3pt]& \le (\kappa(\| x_0 \|))^{(t-h)/2h - 1} \, C_1 \nonumber \\[3pt]&= e^{ - \mu t} \, C_1 \, \kappa(C_1/2)^{-3/2},\end{align}

where we used $C_1 = 2 \| x_0 \|$, and also that $\kappa$ is an increasing function.

So we have reduced the proof to that of (7.6). Given x, let y be the solution of (7.3), and let $t \in [0,h]$. There are three cases.

Case 1.1: $y'(t) = 0$ In this case it follows from (7.3) that $y(t) = x(t)/2$, and hence

(7.9) \begin{eqnarray}| y(t) | \le \frac{1}{2} \, \| x \| .\end{eqnarray}

Case 1.2: $y'(t) > 0$. Define

(7.10) \begin{align}S_1 &= \{ s \in [0,t) \,{:}\, y'(s) \le 0 \}, \nonumber \\[3pt]S_2 &= \{ s \in (t,h] \, {:} \, y'(s) \le 0 \}, \nonumber \\[3pt]t_1 &= \begin{cases} \sup S_1 & \mbox{if $S_1 \neq \emptyset$}, \cr 0 & \mbox{if $S_1 = \emptyset$}, \end{cases} \nonumber \\[3pt]t_2 &= \begin{cases} \inf S_2 & \mbox{if $S_2 \neq \emptyset$}, \cr h & \mbox{if $S_2 = \emptyset$}. \end{cases}\end{align}

Then $y(t_1) < y(t) < y(t_2)$. By assumption x is differentiable, so y $^{\prime}$ is continuous, so if $t_1 > 0$ then $y'(t_1) = 0$, and so $y(t_1) = x(t_1)/2$. If $t_1=0$ then $y(t_1) = y(0) = x(h)$. Therefore in either case

(7.11) \begin{eqnarray}y(t) > y(t_1) \ge \min \{x(t_1)/2, x(h) \}.\end{eqnarray}

Similarly, if $t_2 < h$ then $y'(t_2) = 0$, and so $y(t_2) = x(t_2)/2$. If $t_2 = h$ then $y(t_2) = y(h)$ and $y'(h) > 0$, so $y(h) < x(h)/2$. Therefore in either case

(7.12) \begin{eqnarray}y(t) < y(t_2) \le \max \{x(t_2)/2, x(h)/2 \}.\end{eqnarray}

Therefore

(7.13) \begin{eqnarray}| y(t) | \le \max \{x(t_2)/2, x(h)/2, - x(t_1)/2, - x(h) \},\end{eqnarray}

and so we deduce that

(7.14) \begin{eqnarray}| y(t) | \le \max \left\{ | x(h) |, \, \frac{1}{2} \, \| x \| \right\}.\end{eqnarray}

Case 1.3: $y'(t) < 0$. Define

(7.15) \begin{align}S_3 &= \{ s \in [0,t) \,{:}\, y'(s) \ge 0 \}, \nonumber \\[3pt] S_4 &= \{ s \in (t,h] \, {:} \, y'(s) \ge 0 \}, \nonumber \\[3pt] t_3 &= \begin{cases} \sup S_3 & \mbox{if $S_3 \neq \emptyset$,} \cr 0 & \mbox{if $S_3 = \emptyset$,} \end{cases} \nonumber \\[3pt] t_4 &= \begin{cases} \inf S_4 & \mbox{if $S_4 \neq \emptyset$,} \cr h & \mbox{if $S_4 = \emptyset$.} \end{cases}\end{align}

Then $y(t_3) > y(t) > y(t_4)$. By assumption y$^{\prime}$ is continuous, so if $t_3 > 0$ then $y'(t_3) = 0$, and so $y(t_3) = x(t_3)/2$. If $t_3=0$ then $y(t_3) = y(0) = x(h)$. Therefore in either case

(7.16) \begin{eqnarray}y(t) < y(t_3) \le \max \{x(t_3)/2, x(h) \}.\end{eqnarray}

Similarly, if $t_4 < h$ then $y'(t_4) = 0$, and so $y(t_4) = x(t_4)/2$. If $t_4 = h$ then $y(t_4) = y(h) > x(h)/2$, and thus in either case

(7.17) \begin{eqnarray}y(t) > y(t_4) \ge \min \{x(t_4)/2, x(h)/2 \}.\end{eqnarray}

Therefore

(7.18) \begin{eqnarray}| y(t) | \le \max \{x(t_3)/2, x(h), - x(t_4)/2, - x(h)/2 \},\end{eqnarray}

and so we deduce again that for this case

(7.19) \begin{eqnarray}| y(t) | \le \max \left\{ | x(h) |, \, \frac{1}{2} \, \| x \| \right\}.\end{eqnarray}

Putting together these three cases we have the bound

(7.20) \begin{eqnarray}| y(t) | \le \max \left\{ | x(h) |, \, \frac{1}{2} \, \| x \| \right\}.\end{eqnarray}

This immediately implies that $\| y \| \le \| x \|$, which is the first inequality in (7.6). For the second inequality, we will provide a bound for $|y(h)|$ in terms of $\| x \|$, which will be combined with (7.20) to derive (7.6). Again we examine several cases.

Case 2.1: $y'(h) = 0$. In this case $y(h) = x(h)/2$ and so $|y(h)| \le \|x\|/2$.

Case 2.2: $y'(h) < 0$. In this case $y(h) > x(h)/2$. We assume that $y'(t) < 0$ for all $t \in [0,h]$: if this is not true, then as with Case 3 we deduce the existence of $t_3$ such that $y(h) < y(t_3) = x(t_3)/2$, and then we have $x(h)/2 < y(h) < x(t_3)/2$, which implies $|y(h)| \le \|x\|/2$. We also assume that $y(h) > 0$: if $y(h) \le 0$ then the inequality $y(h) > x(h)/2$ implies $|y(h)| \le \| x \|/2$. Since y(t) is monotone decreasing and $y(h) > 0$, this implies that $y(t) > 0$ for all $t \in [0,h]$. Also $y'(t) < 0$ implies

(7.21) \begin{eqnarray}y(t) > \frac{x(t)}{2}, \quad \mbox{and} \quad y(t) > y(h) > \frac{x(h)}{2} \quad \mbox{for all $t \in [0,h)$}.\end{eqnarray}

Suppose first that there is some $t \in [0,h)$ such that

(7.22) \begin{eqnarray}y(t) \le \frac{ 3 x(t)}{4}.\end{eqnarray}

Then

(7.23) \begin{eqnarray}\frac{ 3 x(t)}{4} \ge y(t) > y(h) > \frac{x(h)}{2},\end{eqnarray}

and therefore

(7.24) \begin{eqnarray}|y(h)| \le \frac{3}{4} \, \| x \|.\end{eqnarray}

If no such t exists then we have

(7.25) \begin{eqnarray}y(t) > \frac{ 3 x(t)}{4} \quad \mbox{for all $t \in [0,h)$},\end{eqnarray}

and hence (since by assumption $y(t) > 0$)

(7.26) \begin{eqnarray}\frac{d y}{ d t} = - \frac{y - x/2}{x + h} \le - \frac{1}{3} \, \frac{y}{x + h}\le - \frac{1}{3} \, \frac{y}{\| x \| + h}.\end{eqnarray}

We immediately deduce that

(7.27) \begin{eqnarray}y(h) \le y(0) \, \exp \left( - \frac{h}{3(\| x \| + h)} \right).\end{eqnarray}

Putting together these two possibilities we get

(7.28) \begin{eqnarray}|y(h)| \le \kappa(\| x \|) \, \| x \| \quad \mbox{where $\kappa(u) = \max \Big\{\frac{3}{4}, \, \exp \Big( - \frac{h}{3(u + h)}\Big) \Big\}$}.\end{eqnarray}

Case 2.3: $y'(h) > 0$. The analysis of this case is identical to that of Case with some signs reversed, and the same conclusion holds.

Combining Cases , , and , we conclude that the bound (7.28) holds in all cases. Using (7.20) we conclude that

(7.29) \begin{eqnarray}\| \mathcal{M}(x)(h) \| \le \kappa(\| x \|) \, \| x \| .\end{eqnarray}

Finally we return to the second inequality in (7.6), and deduce from (7.29) that

\begin{align*}\| \mathcal{M}(\mathcal{M}(x)) \| & \le \max \left\{ \| \mathcal{M}(x)(h) \|, \, \frac{1}{2} \| \mathcal{M}(x) \| \right\} \\[3pt] & \le \max \left\{ \kappa(\| x \|) \, \| x \|, \, \frac{1}{2} \| \mathcal{M}(x) \| \right\} \\[3pt] & \le \max \left\{ \kappa(\| x \|) \, \| x \|, \, \frac{1}{2} \| x \| \right\} \\[3pt] & = \kappa(\| x \|) \, \| x \| .\\\end{align*}

8. Proofs of lemmas

8.1. Proof of Lemma 3.1

The formulas (3.9) and (3.11) show that (a(t), b(t)) is uniquely defined and differentiable in the interval (0, h), and is continuous at $t=h$. The iterative construction described for the intervals $[0,h], [h,2h], \dots$ produces a unique differentiable solution in every interval $(j h, (j+1) h)$ for $j=1,2,\dots$. The solution is clearly continuous at $t= j h$ for all $j \ge 1$. It is also differentiable at $t= j h$ for all $j \ge 2$, because it satisfies the differential equations (3.5) in both intervals $((j-1) h, jh)$ and $(j h, (j+1) h)$. Properties (1), (2), (3) follow by construction. To see that Property (4) holds, let $c(t) = b(t) - a(t)$ and consider first the interval [0, h], where we have

(8.1) \begin{eqnarray}c'(t) = b'(t) - a'(t) = 2 \frac{a(t)}{b(t)} - u(t-h) .\end{eqnarray}

Therefore for some constant K we have

(8.2) \begin{eqnarray}c(t) = \int_{0}^t 2 \frac{a(s)}{b(s)} \, d s + \int_{t-h}^0 u(s) \, d s + K .\end{eqnarray}

Evaluating at $t=0$ we see from (3.7) that $K=0$, and hence we have at $t=h$ the relation

(8.3) \begin{eqnarray}c(h) = \int_{0}^{h} 2 \frac{a(s)}{b(s)} \, d s .\end{eqnarray}

Now for $t \ge h$ we have

(8.4) \begin{eqnarray}c'(t) = b'(t) - a'(t) = 2 \frac{a(t)}{b(t)} - 2 \frac{a(t-h)}{b(t-h)},\end{eqnarray}

and thus for some constant K $^{\prime}$

(8.5) \begin{eqnarray}c(t) = \int_{t-h}^t 2 \frac{a(s)}{b(s)} \, d s + K' .\end{eqnarray}

Evaluating at $t=h$ we deduce that $K'=0$, and this establishes Property (4). Property (5) follows immediately.

8.2. Proof of Lemma 3.2

From (2.17) and (3.9) we derive for $0 \le n \le m$ that

(8.6) \begin{align}B_v^{(\lambda)}(t_n) - b_{\alpha}(t_n) &= \lambda^{-1} \sum_{i=n-m+1}^0 v_i - \int_{t_{n-m}}^{0} u(s) \, d s+ \lambda^{-1} \xi_{\alpha} - a(0) \nonumber \\&= \lambda^{-1} \sum_{i=n-m+1}^0 (v_i - x_i)+ \lambda^{-1} \xi_{\alpha} - a(0),\end{align}

where

(8.7) \begin{eqnarray}x_j = \lambda \, \int_{t_{j-1}}^{t_j} u(s) \, d s, \qquad j = -m+1,\dots, 0 .\end{eqnarray}

We also have from the definition of $\xi_{\alpha}$ that

(8.8) \begin{eqnarray}| \lambda^{-1} \xi_{\alpha} - a(h) | \le \lambda^{-1} .\end{eqnarray}

We now introduce a product probability measure on $\mathcal{S}(m)$ so that the coordinates $v_{-m+1},\dots,v_0$ are independent random variables: for any sequence $(u_{-m+1},\dots,u_0)$,

(8.9) \begin{eqnarray}\mathbb{P}(v = (u_{-m+1},\dots,u_0)) = \prod_{j=-m+1}^0 \mathbb{P}_j(v_j = u_j) .\end{eqnarray}

The distribution $\mathbb{P}_j$ is chosen so that

(8.10) \begin{eqnarray}\mathbb{E}[v_j] = \sum_{k=0,1,2} k \, \mathbb{P}_j(v_j = k) = x_j\end{eqnarray}

(since $0 \le x_j \le 2$ this is always possible). Define

(8.11) \begin{eqnarray}M_n = \sum_{j=-m+1}^n (v_j - x_j), \quad -m+1 \le n \le 0 .\end{eqnarray}

Since the $\{v_j\}$ are independent with finite variances and (8.10) holds, we can apply Kolmogorov’s maximal inequality [Reference Billingsley4] and deduce that for any $\delta > 0$

(8.12) \begin{eqnarray}\mathbb{P}\bigg( \max_{-m+1 \le n \le 0} |M_n| > \delta\bigg) \le \delta^{-2} \, {\rm Var}[M_0] .\end{eqnarray}

Since $|v_j| \le 2$ for all j, we have ${\rm Var}[v_j - x_j] \le 4$, and hence by independence

(8.13) \begin{eqnarray}{\rm Var}[M_0] \le 4 m = 4 \lambda h .\end{eqnarray}

Taking $\delta = 4 h^{1/2} \, \lambda^{1/2}$ we deduce that

(8.14) \begin{eqnarray}\mathbb{P}\bigg( \max_{0 \le n \le m} \bigg| \sum_{i=n-m+1}^0 (v_i - x_i)) \bigg| > 4 h^{1/2} \, \lambda^{1/2} \bigg) \le 1/4 .\end{eqnarray}

Therefore, using (8.8) and the formula (8.6), we get

(8.15) \begin{eqnarray}\mathbb{P}(F(\alpha, \lambda)) \ge \mathbb{P}\left( \max_{0 \le n \le m} \left|\lambda^{-1} \sum_{i=n-m+1}^0 (v_i - x_i)) \right| \le 4 h^{1/2} \, \lambda^{-1/2} \right) \ge 3/4,\end{eqnarray}

and so we deduce that $F(\alpha, \lambda)$ is non-empty.

8.3. Proof of Lemma 5.1

For every $v \in A$, we have $|v_m - m| \le 3 m$. Thus, there is a sequence $\mathcal{X}_n,\mathcal{X}_{n+1},\dots,\mathcal{X}_{n+3m}$ with positive probability such that $\mathcal{X}_n=v$ and $X_{n+3m}=m$. We choose $X_{n+3m+1}=m,\dots,X_{n+4m}=m$, so that $\mathcal{X}_{n+4m}=\omega$, and thus we have constructed a path with positive probability leading from $\mathcal{X}_n=v$ to $\mathcal{X}_{n+4m}=\omega$. Let

(8.16) \begin{eqnarray}\kappa = \min_{v \in A} \min_{\epsilon=0,1,2} \mathbb{P}(U_{n+1}=\epsilon\,|\, \mathcal{X}_n = v);\end{eqnarray}

then we have

(8.17) \begin{eqnarray}\mathbb{P}(\mathcal{X}_{n+4m} = \omega \,|\, \mathcal{X}_n = v) \ge \kappa^{4m}.\end{eqnarray}

This establishes (5.10) with $\gamma = \kappa^{4m}$.

We also have for $u \in A^c$ that

(8.18) \begin{equation}\hspace*{-175pt}\mathbb{E}_{\psi}[X_{n+1} \,|\, \mathcal{X}_n = u] = X_n + 1 - 2 \frac{X_n}{L_n} + \frac{X_n}{L_n^2}\end{equation}

(8.19) \begin{equation}\hspace*{-50pt}= u_m + 1 - 2 \frac{u_m}{u_0 + m} + \frac{u_m}{(u_0 + m)^2} \end{equation}

(8.20) \begin{equation}\hspace*{-74pt} \le u_m + 1 - 2 \frac{u_m}{u_m+2 m} + \frac{1}{u_m} \end{equation}

(8.21) \begin{equation}\le u_m + 1 - 2 \frac{4 m}{4 m+2 m} + \frac{1}{4m} \le u_m - \frac{1}{3} + \frac{1}{4m},\end{equation}

and this establishes (5.11) with $c = 1/12$ (since $m \ge 1$).

8.4. Proof of Lemma 6.1

We derive a uniform bound for the difference $B^{(\lambda)}(s) - b(s)$ in terms of the function g and an error term coming from the initial conditions. Recall that by assumption $v \in F(\alpha, \lambda)$; therefore

(8.22) \begin{eqnarray}\sup_{0 \le n \le m} | B^{(\lambda)}(t_n) - b(t_n) | \le 4 h^{1/2} \lambda^{-1/2} + \lambda^{-1}.\end{eqnarray}

Furthermore, if $t \in [0,h]$ and $t \in [t_n,t_{n+1})$, then

(8.23) \begin{eqnarray}| b(t) - b(t_n) | = \left| \int_{t_n}^t (1 - u(s-h)) \, d s \right| \le t - t_n \le \lambda^{-1}.\end{eqnarray}

Therefore (8.22) and (8.23) together imply that

(8.24) \begin{eqnarray}\sup_{0 \le s \le h} |B^{(\lambda)}(s) - b(s)| \le 4 h^{1/2} \lambda^{-1/2} + 2 \, \lambda^{-1}\le 6 h^{1/2} \lambda^{-1/2},\end{eqnarray}

where we have used $ h \lambda \ge 1$. Combining (6.6) and (8.24) we get the uniform bound

(8.25) \begin{eqnarray}\sup_{0 \le s \le t} | B^{(\lambda)}(s) - b(s) | \le g(t) + 6 h^{1/2} \lambda^{-1/2} \quad \mbox{for all $t \ge 0$}.\end{eqnarray}

8.5. Proof of Lemma 6.2

We use the martingale property to bound the first sum on the left side of (6.10). Using (6.8) we have

(8.26) \begin{equation}G_{j+1} = 1 - U_{j+1} - \left(1 - \mathbb{E}[U_{j+1} \,|\, \mathcal{F}_j] \right) \end{equation}

(8.27) \begin{equation}\hspace*{-25pt}= 2 \, \frac{X_j}{L_j} - \frac{X_j}{L_j^2} - U_{j+1}.\end{equation}

It follows that $G_{j+1}$ is $\mathcal{F}_{j+1}$-measurable, and

(8.28) \begin{eqnarray}\mathbb{E}[G_{j+1} \,|\, \mathcal{F}_j] = 0 .\end{eqnarray}

Furthermore $|G_{j+1}| \le 2$, so $\{G_j\}$ is a bounded martingale difference series relative to the filtration $\mathcal{F}_n$. Therefore $\sum_{j=0}^{n-1} G_{j+1}$ is a martingale, and $\big(\!\sum_{j=0}^{n-1} G_{j+1}\big)^2$ is a submartingale, so we can apply Doob’s martingale inequality [Reference Billingsley4] to deduce that for $N = \lfloor \lambda T \rfloor$ and any $\theta > 0$,

(8.29) \begin{align}\mathbb{P}\bigg( \sup_{0 \le n \le N} \bigg|\lambda^{-1} \, \sum_{j=0}^{n-1} G_{j+1} \bigg| \ge \theta \bigg) & = \mathbb{P}\bigg( \sup_{0 \le n \le N} \bigg| \sum_{j=0}^{n-1} G_{j+1} \bigg|^2 \ge \lambda^2 \, \theta^2 \bigg) \nonumber \\[3pt]&\le \lambda^{-2} \, \theta^{-2} \, \mathbb{E}\bigg[ \bigg(\sum_{j=0}^{N-1} G_{j+1} \bigg)^2\bigg] \nonumber \\[3pt]& = \lambda^{-2} \, \theta^{-2} \, \sum_{j=0}^{N-1} \mathbb{E}[ G_{j+1}^2 ] \nonumber \\[3pt]& \le 4 \, \theta^{-2} \, \lambda^{-2} \, N \nonumber \\[3pt]& = 4 \, \theta^{-2} \, \lambda^{-1} \, T.\end{align}

8.6. Proof of Lemma 6.3

From (2.14) and (3.1) we get

(8.30) \begin{align}H_{j+1} &= \mathbb{E}[1 - U_{j+1} \,|\, \mathcal{F}_j] - \lambda \, \int_{t_{j}}^{t_{j+1}} \bigg(1 - 2 \, \frac{a(s)}{b(s)} \bigg) \, d s \nonumber \\[3pt]&= - 2 \, \frac{X_j}{L_j} + \frac{X_j}{L_j^2} + 2 \, \lambda \, \int_{t_{j}}^{t_{j+1}} \frac{a(s)}{b(s)} \, d s \nonumber \\[3pt]&= 2 \, \lambda \, \int_{t_{j}}^{t_{j+1}} \bigg( \frac{a(s)}{b(s)} - \frac{A^{(\lambda)}(t_j)}{B^{(\lambda)}(t_j)} \bigg) \, d s+ \lambda^{-1} \frac{A^{(\lambda)}(t_j)}{(B^{(\lambda)}(t_j))^2} \nonumber \\[3pt]&= 2 \, \lambda \, \int_{t_{j}}^{t_{j+1}} \bigg( \frac{a(s)}{b(s)} - \frac{A^{(\lambda)}(s)}{B^{(\lambda)}(s)} \bigg) \, d s+ \lambda^{-1} \frac{A^{(\lambda)}(t_j)}{(B^{(\lambda)}(t_j))^2}. \end{align}

We write

(8.31) \begin{eqnarray} \frac{a(s)}{b(s)} - \frac{A^{(\lambda)}(s)}{B^{(\lambda)}(s)} &=& \frac{a(s) - A^{(\lambda)}(s)}{b(s)} + \frac{A^{(\lambda)}(s)}{B^{(\lambda)}(s)} \, \frac{B^{(\lambda)}(s) - b(s)}{b(s)}. \end{eqnarray}

Using the bounds $A^{(\lambda)}(s) \le B^{(\lambda)}(s)$ and (6.2), (6.3), (6.4), and (6.7), we have from (8.31) that

(8.32) \begin{eqnarray}\left| \frac{a(s)}{b(s)} - \frac{A^{(\lambda)}(s)}{B^{(\lambda)}(s)} \right| \le 2 \, l^{-1} \, g(s) + 6 \, l^{-1} \, h^{1/2} \, \lambda^{-1/2} .\end{eqnarray}

Therefore we deduce from (8.30) that

(8.33) \begin{align}| H_{j+1} | &\le 4 \, l^{-1} \, g(t_{j+1}) + 12 \, l^{-1} \, h^{ 1/2} \, \lambda^{-1/2} + l^{-1} \, \lambda^{-1} \nonumber\\[3pt] &\le 4 \, l^{-1} \, g(t_{j+1}) + 13 \, l^{-1} \, h^{ 1/2} \, \lambda^{-1/2} ,\end{align}

which gives the bound

(8.34) \begin{align}\lambda^{-1} \, \left| \sum_{j=0}^{n-1} H_{j+1} \right| &\le 4 \, l^{-1} \, \lambda^{-1} \, \sum_{j=0}^{n-1} g(t_{j+1}) + 13 \, l^{-1} \, h^{ 1/2} \, \lambda^{-1/2} \, t_n \nonumber \\[3pt] &\le 4 \, l^{-1} \, \lambda^{-1} \, \sum_{j=0}^{n-1} g(t_{j+1}) + 13 \, l^{-1} \, h^{ 1/2} \, \lambda^{-1/2} \, T .\end{align}