2.1. Main results

For $x\in\mathbb{R}$ and A Borel (one-dimensional), we let p(x, A) be a Markov transition kernel. By this we mean that for every Borel A, $p(\cdot,A)$ is a Borel function and for each $x\in\mathbb{R}$ , $p(x,\cdot)$ is a probability measure. We will say that p is stochastically monotone if $p(x,(y,\infty))$ is nondecreasing in x for each $y\in\mathbb{R}$ , which, as was discussed earlier and will be demonstrated later, is a natural property across a broad range of frequently used stochastic models.

The following condition plays a crucial role in our results. Whenever it is satisfied, it allows us to establish highly general results. The condition is natural in the context of, e.g., queues and other storage systems, as will be pointed out in Section 3.

Now, for $n\ge 1$ , let p and $p_n$ , for $n\ge 1$ , be transition kernels. Define

(1) \begin{equation}G(x,u)=\inf\{y\,|\, p(x,({-}\infty,y])\ge u\}\end{equation}

to be the generalized inverse function associated with the CDF $F_x(y)=p(x,({-}\infty,y])$ , and similarly let $G_n(x,u)$ be the generalized inverse function associated with $p_n$ . We recall (see e.g. the paper [Reference Embrechts and Hofert9], among many others) that G(x, u) is nondecreasing and left-continuous in u (on (0, 1)), and that $G(x,u)\le y$ if and only if $u\le p(x,({-}\infty,y])$ . Thus, if $U=_{\rm d}\text{U}(0, 1)$ , where $\text{U}(0, 1)$ is the uniform distribution on (0, 1), then ${\mathbb P}(G(x,U)\le y)=p(x,({-}\infty,y])$ and thus ${\mathbb P}(G(x,U)\in A)=p(x,A)$ . Similar reasoning applies to $G_n(x,u)$ for every $n\ge 1$ .

Proof. It follows from the facts (i) that for $x_1<x_2$

(2) \begin{equation}\{y\,|\,p(x_1,({-}\infty,y])\ge u\}\supset \{y\,|\,p(x_2,({-}\infty,y])\ge u\},\end{equation}

(ii) that under Condition 1 for $x_1<x_2$

(3) \begin{equation}\{y\,|\,p(x_1,({-}\infty,x_1+y])\ge u\}\subset \{y\,|\,p(x_2,({-}\infty,x_2+y])\ge u\},\end{equation}

and (iii) that $G(x,u)-x=\inf\{y\,|\,p(x,({-}\infty,x+y]\ge u\}$ .

Now, let $g_k^{k}(x,u)=G_k(x,u)$ , and for $n\ge k+1$ let

(4) \begin{equation}g_k^n(x,u_1,\ldots,u_{n-k+1})=G_n(g_k^{n-1}(x,u_1,\ldots,u_{n-k}),u_{n-k+1}).\end{equation}

It immediately follows by induction that if $p_k,\ldots,p_n$ are stochastically monotone, then $g_k^n(x,u_1,\ldots,u_{n-k+1})$ is nondecreasing in x. Assume that $U_1,U_2,\ldots$ are independent and identically distributed (i.i.d.) with distribution $\text{U}(0, 1)$ ; then with $X^{\prime}_0=x$ and

(5) \begin{equation}X^{\prime}_n=g_1^n(x,U_1,\ldots,U_n)\end{equation}

for $n\ge 1$ , $\{X^{\prime}_n\,|\, n\ge 0\}$ is a real-valued (possibly time-inhomogeneous) Markov chain with possibly time-dependent transition kernels $p_1,p_2,\ldots$ . Let us now set $p^{k-1}_k(x,A)=1_A(x)$ and, for $n\ge k$ ,

(6) \begin{equation}p^n_k(x,A)=\int_{\mathbb{R}}p_n(y,A)p_k^{n-1}(x,\text{d}y).\end{equation}

A (possibly time-inhomogeneous) Markov chain with stochastically monotone transition kernels will be called a stochastically monotone Markov chain (see, e.g., [Reference Daley7] for the time-homogeneous case). Lemma 2 immediately implies the following.

Therefore, a subsequence of a time-homogeneous stochastically monotone Markov chain (resp., in addition satisfying Condition 1) may no longer be time-homogeneous, but is always a stochastically monotone Markov chain (resp., in addition satisfying Condition 1).

Recall that $h\,:\,\mathbb{R}^2\to\mathbb{R}$ is called supermodular if whenever $x_1\le x_2$ and $y_1\le y_2$ we have that

(7) \begin{equation}h(x_1,y_2)+h(x_2,y_1)\le h(x_1,y_1)+h(x_2,y_2).\end{equation}

If X and Y have CDFs $F_X$ and $F_Y$ , then (X, Y) will be called comonotone if $\mathbb{P}(X\le x,Y\le y)=\mathbb{P}(X\le x)\wedge \mathbb{P}(Y\le y)$ for all x, y. There are various equivalent definitions for comonotonicity. In particular it is worth mentioning that when X and Y are identically distributed, they are comonotone if and only if $\mathbb{P}(X=Y)=1$ . It is well known that if (X ^′, Y ^′) is comonotone and has the same marginals as (X, Y), then for any Borel supermodular h for which $\mathbb{E} h(X,Y)$ and $\mathbb{E} h(X^{\prime},Y^{\prime})$ exist and are finite, we have that $\mathbb{E} h(X,Y)\le \mathbb{E} h(X^{\prime},Y^{\prime})$ . In particular, if X, Y are identically distributed, then $\mathbb{E} h(X,Y)\le \mathbb{E} h(Y,Y)$ , which is a property that we will need later in this paper. For such results and much more, see e.g. [Reference Puccetti and Wang21] and references therein, where the Borel assumption is not made but is actually needed, as there are non-Borel supermodular functions for which h(X, Y) is not necessarily a random variable. We write down what we will need later as a lemma. Everything in this lemma is well known.

Lemma 3. Let (X,Y) be a random pair such that $X=_{\rm d} Y$ . Then for every Borel supermodular function $h\,:\,\mathbb{R}^2\to\mathbb{R}$ for which $\mathbb{E} h(X,Y)$ and $\mathbb{E} h(Y,Y)$ exist and are finite, we have that

(8) \begin{equation}\mathbb{E} h(X,Y)\le \mathbb{E} h(Y,Y).\end{equation}

Moreover, if h is supermodular and $f_1,f_2$ are nondecreasing, then $h(f_1(x),f_2(y))$ is supermodular, and in particular, since $h(x,y)=xy$ is supermodular, $f_1(x)f_2(y)$ is supermodular as well.

As usual, we call $\pi$ invariant for a Markov kernel p if, for every Borel A, $\int_{\mathbb{R}}p(x,A)\pi(\text{d}x)=\pi(A)$ . We proceed by stating and proving our first main result.

Theorem 1. Assume that $X_0,X_1,X_2$ is a stochastically monotone Markov chain where $p_1$ has an invariant distribution $\pi_1$ and $X_0$ is $\pi_1$ -distributed. Then for every Borel supermodular $h\,:\,\mathbb{R}^2\to\mathbb{R}$ ,

(9) \begin{equation}\mathbb{E} h(X_0,X_2)\le \mathbb{E} h(X_1,X_2)\end{equation}

whenever the means exist and are finite. In particular, for any nondecreasing $f_1,f_2$ for which the means of $f_1(X_0)$ , $f_2(X_2)$ , $f_1(X_0)f_2(X_2)$ , and $f_1(X_1)f_2(X_2)$ exist and are finite, we have that

(10) \begin{equation}0\le\text{ Cov}(f_1(X_0),f_2(X_2))\le \text{Cov}(f_1(X_1),f_2(X_2)).\end{equation}

Proof. Let $X^{\prime}_0,U_1,U_2$ be independent with $U_1,U_2=_{\rm d}\text{U}(0, 1)$ and $X^{\prime}_0= X_0$ . Then with $X^{\prime}_1=G_1(X^{\prime}_0,U_1)$ and $X^{\prime}_2=G_2(X^{\prime}_1,U_2)$ we have that $(X^{\prime}_0,X^{\prime}_1,X^{\prime}_2)=_{\rm d} (X_0,X_1,X_2)$ . Now we note that since $G_2(y,u_2)$ is nondecreasing in y, we have (by Lemma 3) that $h(x,G_2(y,u_2))$ is supermodular in x, y for every fixed $u_2$ . Since $X^{\prime}_0=_{\rm d} X^{\prime}_1$ , it follows from Lemma 3 that

(11) \begin{equation}\mathbb{E} (h(X^{\prime}_0,G_2(X^{\prime}_1,U_2))\,|\,U_2)\le \mathbb{E} (h(X^{\prime}_1,G_2(X^{\prime}_1,U_2))\,|\,U_2).\end{equation}

Taking expected values on both sides gives (9). Noting that $\mathbb{E} f_1(X_0)\mathbb{E} f_2(X_2)=\mathbb{E} f_1(X_1)\mathbb{E} f_2(X_2)$ and that $f_1(x)f_2(y)$ is supermodular gives the right inequality in (10). To show the left inequality, note that $G_2(G_1(x,u_1),u_2)$ is a nondecreasing function of x, and thus, so is $\gamma(x)=\mathbb{E} f_2(G_2(G_1(x,U_1,U_2)))$ . Now,

(12) \begin{equation}\text{Cov}(f_1(X_0),f_2(X_2))=\text{Cov}(f_1(X_0),\mathbb{E} [f_2(X_2)|X_0])=\text{Cov}(f_1(X_0),\gamma(X_0)),\end{equation}

and it is well known that the covariance of comonotone random variables (whenever well defined and finite) must be nonnegative.

A time-homogeneous continuous-time Markov process $\{X_t\,|\,t\ge 0\}$ will be called stochastically monotone whenever $p^t(x,A)=\mathbb{P}_x(X_t\in A)$ is a stochastically monotone kernel for each $t>0$ . We will say that it satisfies Condition 1 whenever $p^t$ satisfies this condition for every $t>0$ . Note that by Corollary 1 this is equivalent to the assumption that these conditions are satisfied for $0<t\le \epsilon$ for some $\epsilon>0$ .

Proof. For every $0<t_1<t_2$ we have that $X_0,X_{t_2-t_1},X_{t_2}$ satisfy the conditions and hence the conclusions of Theorem 1 (for the discrete-time case, recall Corollary 1). By stationarity we have that $(X_{t_2-t_1},X_{t_2})=_{\rm d} (X_0,X_{t_1})$ . Therefore

(13) \begin{equation}\mathbb{E} h(X_0,X_{t_2})\le \mathbb{E} h(X_{t_2-t_1},X_{t_2})=\mathbb{E} h(X_0,X_{t_1}).\end{equation}

Note that, since $X_t=_{\rm d} X_0$ , Lemma 3 implies that

(14) \begin{equation}\mathbb{E} h(X_0,X_t)\le \mathbb{E} h(X_0,X_0),\end{equation}

so that $\mathbb{E} h(X_0,X_t)$ is nonincreasing on $[0,\infty)$ and not just on $(0,\infty)$ . Since

\begin{equation*}\mathbb{E} f_1(X_0)\mathbb{E} f_2(X_t)=\mathbb{E} f_1(X_0)\mathbb{E} f_2(X_0),\end{equation*}

the result for the covariance follows by taking $h(x,y)=f_1(x)f_2(y)$ .

We continue with two theorems in which Condition 1 is imposed.

Theorem 3. Assume that $X_0,X_1,X_2,X_3$ is a stochastically monotone Markov chain satisfying Condition 1, where $p_1$ has an invariant distribution $\pi_1$ and $X_0$ is $\pi_1$ -distributed. Then for every Borel supermodular $h\,:\,\mathbb{R}^2\to\mathbb{R}$ ,

(15) \begin{equation}\mathbb{E} h(X_0,X_2-X_3)\le \mathbb{E} h(X_1, X_2-X_3)\end{equation}

whenever the expectations exist and are finite. In particular, if f is nondecreasing and the appropriate expectations exist and are finite, then

(16) \begin{equation}0\le \text{ Cov}(f(X_0),X_2)-\text{ Cov}(f(X_0),X_3)\le \text{ Cov}(f(X_1),X_2)-\text{ Cov}(f(X_1),X_3).\end{equation}

Proof. The proof is very similar to the proof of Theorem 1. That is, we let $X^{\prime}_0=X_0$ , $X^{\prime}_n=G_n(X^{\prime}_{n-1},U_n)$ for $n=1,2,3$ , where $X^{\prime}_0,U_1,U_2,U_3$ are independent and $U_1,U_2,U_3=_{\rm d} \text{U}(0, 1)$ . From the stochastic monotonicity and Condition 1 it follows that $G_2(x,u_2)-G_3(G_2(x,u_2),u_3)$ is nondecreasing in x. Therefore, by Lemma 3 we have that, since $h(x,G_2(y,u_2)-G_3(G_2(y,u_2),u_3))$ is supermodular in x, y and $X^{\prime}_1=_{\rm d} X^{\prime}_0$ ,

(17) \begin{align}\mathbb{E} [h(X^{\prime}_0,X^{\prime}_2-X^{\prime}_3)|U_2,U_3]&=\mathbb{E} [h(X^{\prime}_0,G_2(X^{\prime}_1,U_2)-G_3(G_2(X^{\prime}_1,U_2),U_3))|U_2,U_3]\nonumber\\&\le \mathbb{E} [h(X^{\prime}_1,G_2(X^{\prime}_1,U_2)-G_3(G_2(X^{\prime}_1,U_2),U_3))|U_2,U_3]\\&=\mathbb{E} [h(X^{\prime}_1,X^{\prime}_2-X^{\prime}_3)|U_2,U_3],\nonumber\end{align}

and taking expected values establishes (15). Taking $h(x,y)=f(x)y$ gives the right inequality of (16). The left inequality is obtained via comonotonicity, by observing that since $G_2(G_1(x,u_1),u_2)-G_3(G_2(G_1(x,u_1),u_2),u_3)$ is nondecreasing in x, $\mathbb{E} [X_2-X_3|X_0]$ is a nondecreasing function of $X_0$ , so that this inequality follows from the comonotonicity of $f(X_0)$ and $\mathbb{E} [X_2-X_3|X_0]$ as in the proof of the left inequality of (10).

In particular, note that when choosing $f(x)=x$ and assuming that $\mathbb{E} X_0^2<\infty$ , we see that, under the conditions of Theorem 4, the auto-covariance $R(t)=\text{Cov}(X_s,X_{s+t})$ (or auto-correlation $R(t)/R(0)$ when $X_0$ is not a.s. constant) is nonnegative, nonincreasing, and convex in t.

Proof. Let $t_1<t_2$ ; then $X_0,\, X_{t_2-t_1},\, X_{t_2-t_1+s},\, X_{t_2+s}$ satisfy the conditions and hence the conclusion of Theorem 3. Therefore,

(18) \begin{equation}\mathbb{E} h(X_0,X_{t_2}-X_{t_2+s})\le \mathbb{E} h(X_{t_2-t_1},X_{t_2}-X_{t_2+s})=\mathbb{E} h(X_0,X_{t_1}-X_{t_1+s}),\end{equation}

where the right equality follows from stationarity. If f is nondecreasing, then $h(x,y)=f(x)y$ is supermodular and thus $\mathbb{E} f(X_0)X_{t+s}-\mathbb{E} f(X_0) X_t$ is nonincreasing in t for every $s>0$ . Therefore $\mathbb{E} f(X_0)X_t$ is midpoint-convex, and since by Theorem 2 it is nonnegative and nonincreasing (hence Borel), it must be convex (see [Reference Blumberg4, Reference Sierpinski24]).

Can anything be said for the case where the initial distribution is not invariant? Here is one possible answer.

We note that it would suffice to assume that $X_0\le X_t$ for $t\in(0,\epsilon]$ for some $\epsilon>0$ , or in discrete time for $t=1$ . Also, we note that for (i) we can replace $X_0\le X_t$ by $X_0\le_{\text{st}}X_t$ .

Proof. For any $s<t$ take $\epsilon\in(0,t-s]$ and let $G_v(x,u)$ be the generalized inverse with respect to the kernel $p^v$ . Let $U_0,U_1,\ldots$ be i.i.d. with $U_i=_{\rm d}\text{U}(0, 1)$ . Since $X_0\le X_\epsilon$ we have with $X^{\prime}_0=X_0$ that $X^{\prime}_0\le G_\epsilon(X^{\prime}_0,U_0)$ , and thus

(19) \begin{equation}X^{\prime}_s\equiv G_s(X^{\prime}_0,U_1)\le G_s(G_\epsilon(X^{\prime}_0,U_0),U_1)\equiv X^{\prime\prime}_{s+\epsilon}=_{\rm d} X^{\prime}_{s+\epsilon}\equiv G_\epsilon(X^{\prime}_s,U_2),\end{equation}

implying stochastic monotonicity.

Taking $X^{\prime}_t=G_{t-s-\epsilon}(X^{\prime}_{s+\epsilon},U_3)$ , we have that $(X^{\prime}_0,X^{\prime}_s,X^{\prime}_{s+\epsilon},X^{\prime}_t)$ is distributed like $(X_0,X_s,X_{s+\epsilon},X_t)$ . Since h is nondecreasing in its first variable and $X^{\prime}_s\le X^{\prime\prime}_{s+\epsilon}$ , it follows that

(20) \begin{equation}\mathbb{E} h(X^{\prime}_s,X^{\prime}_t)\le \mathbb{E} h(X^{\prime\prime}_{s+\epsilon},X^{\prime}_t).\end{equation}

The (by now repetitive) fact that

(21) \begin{align}\mathbb{E} [h(X^{\prime\prime}_{s+\epsilon},X^{\prime}_t)|U_3]&=\mathbb{E}[h(X^{\prime\prime}_{s+\epsilon},G_{t-s-\epsilon}(X^{\prime}_{s+\epsilon},U_3)|U_3]\nonumber \\ &\le \mathbb{E}[h(X^{\prime}_{s+\epsilon},G_{t-s-\epsilon}(X^{\prime}_{s+\epsilon},U_3)|U_3]=\mathbb{E}[h(X^{\prime}_{s+\epsilon},X^{\prime}_t)|U_3]\end{align}

follows from the supermodularity of $h(x,G_{t-s-\epsilon}(y,u_3))$ in x, y. Taking expected values, together with (20), implies that $\mathbb{E} h(X_s,X_t)$ is nondecreasing in s on [0, t]. The proof of the fact that, under Condition 1, $\mathbb{E} h(X_s,X_t-X_{t+\delta})$ is nondecreasing in s on [0, t] is similar, once we define $X^{\prime}_{t+\delta}=G_\delta(X^{\prime}_t,U_4)$ and observe that $X^{\prime}_t-X^{\prime}_{t+\delta}=G_{t-s-\epsilon}(X^{\prime}_{s+\epsilon},U_3)-G_\delta(G_{t-s-\epsilon}(X^{\prime}_{s+\epsilon},U_3),U_4)$ is nondecreasing in $X^{\prime}_{s+\epsilon}$ .

When h is nondecreasing in both variables we have that

\begin{equation*}h(X_s,X_{s+t})=_{\rm d} h(X_s,G_t(X_s,U_0)),\end{equation*}

so that by stochastic monotonicity $\mathbb{E} (h(X_s,G_t(X_s,U_0))|U_0)$ is nondecreasing in s and hence also $\mathbb{E} h(X_s,X_{s+t})$ . The proof for $\mathbb{E} h(X_s,X_{s+t}-X_{s+t+\delta})$ , under Condition 1, is similar.

Finally, since $X_t$ is stochastically increasing, it clearly follows that $\mathbb{E} X_t$ is nondecreasing. When Condition 1 is met, taking $h(x,y)=y$ (nondecreasing in both variables) we have that $\mathbb{E} X_{s+t}-\mathbb{E} X_{s+t+\delta}$ is nondecreasing. This implies midpoint-concavity, so that since $\mathbb{E} X_t$ is monotone (hence Borel) it follows that it is concave (again, see [Reference Blumberg4, Reference Sierpinski24]).

We complete this section by noting that although, for the sake of convenience, all the results are written for the case where the state space is $\mathbb{R}$ , they hold whenever the state space is any Borel subset of $\mathbb{R}$ , as was assumed in [Reference Daley7]; for instance, for the examples discussed in Section 3, the state space is either $[0,\infty)$ or $\mathbb{Z}_+$ .

2.2. Role of stochastic monotone Markov processes and supermodularity

To put our work into perspective, we conclude this section by explaining the train of thought that led us to this research. One result that sparked this line of research was that for a stationary reflected (both one- and two-sided) Lévy process X with $\mathbb{E} X_0^2<\infty$ , $R(t)=\text{Cov}(X_0,X_t)$ is nonnegative, nonincreasing, and convex [Reference Berkelmans, Cichocka and Mandjes3, Reference Es-Saghouani and Mandjes10, Reference Glynn and Mandjes11]. Since in this case $\mathbb{E} X_t=\mathbb{E} X_0$ , this is equivalent to $\mathbb{E} X_0X_t$ being nonnegative, nonincreasing, and convex. Another result is that for a stationary discrete-time stochastically monotone Markov process and a nondecreasing function g with $\mathbb{E} g^2(X_0)<\infty$ , $\text{Cov}(g(X_0),g(X_n))$ is nonincreasing [Reference Daley7]. This is equivalent to $\mathbb{E} g(X_0)g(X_n)$ being nonincreasing. We observed that xy, g(x)g(y) (when g is nondecreasing) are supermodular functions of x, y. Also, we knew that the one- and two-sided Skorokhod reflection of a process of the form $x+X_t$ is monotone in x. When X is a Lévy process, the reflected process is Markovian, and from the monotonicity in x it must be stochastically monotone.

Therefore, a natural question arose: is it true that for any stationary stochastically monotone Markov process (in discrete or continuous time) and for any supermodular h we have that $\mathbb{E} h(X_0,X_t)$ is nonincreasing? If yes, then this would make the abovementioned results from [Reference Berkelmans, Cichocka and Mandjes3, Reference Daley7, Reference Es-Saghouani and Mandjes10, Reference Glynn and Mandjes11], each of which uses a totally different (often quite involved) approach, simple special cases. We were happy to see that the answer to this question was ‘yes’.

The next step was to try to identify what condition ensures convexity of the correlation or even more general function. As seen in Section 2, the condition that ensures convexity of $\mathbb{E} g(X_0)X_t$ for a nondecreasing function g (in particular $g(x)=x$ ) is Condition 1. We lack a full intuitive understanding of why it is this precise condition that makes it work. As will be seen in Section 3, various natural Markovian models satisfy stochastic monotonicity and Condition 1.

Finally, we also knew that for a (one- and two-sided) reflected Lévy process X starting from the origin (and actually also for more general processes), $\mathbb{E} X_t$ is nonincreasing and concave [Reference Andersen and Mandjes1, Reference Kella12, Reference Kella and Sverchkov14, Reference Kella and Whitt15]. We asked ourselves whether this too might be seen as a special case of the more general theory we had discovered, and, as it turned out, the answer to this question was affirmative as well.

3.1. Lévy process reflected at the origin

Consider a càdlàg Lévy process $Y=\{Y_t\,|\,t\ge 0\}$ with $\mathbb{P}(Y_0=0)=1$ (not necessarily spectrally one-sided). For every x, the one-sided (Skorokhod) reflection map, with reflection taking place at level 0, is defined through

(22) \begin{equation}X_t(x)=x+Y_t-\inf_{0\le s\le t}(x+Y_s)\wedge0=Y_t+L_t\wedge x,\end{equation}

where $L_t=-\inf_{0\le s\le t}Y_s\wedge 0$ with $L_t(x)=(L_t-x)^+$ (so, in particular, $L_t=L_t(0)$ ). The pair $(L_t(x),X_t(x))$ is known to be the unique process satisfying the following conditions:

1. (i) $L_t(x)$ is right-continuous and nondecreasing in t, with $L_0=0$ .

2. (ii) $X_t(x)$ is nonnegative for every $t\ge 0$ .

3. (iii) For every $t>0$ such that $L_s(x)<L_t(x)$ for every $s<t$ , we have that $X_t(x)=0$ .

It is known [Reference Kella13] that (iii) is equivalent to the condition that

(23) \begin{equation}\int_{[0,\infty)}X_s(x)L_{\text{d}s}(x)=0,\end{equation}

or alternatively to the condition that $L_t(x)$ is the minimal process satisfying (i) and (ii). Special cases of such processes are the workload process in an M/G/1 queue and the (one-dimensional) reflected Brownian motion (where the reflection takes place at 0).

It turns out that when $x=0$ , $\mathbb{E} X_t$ is nondecreasing and concave in t [Reference Kella12, Reference Kella and Sverchkov14]. When $\mathbb{E} Y_1<0$ , this process, which is well known to be Markovian, has a stationary distribution. If W has this stationary distribution and is independent of the process Y, then $X^*_t=X_t(W)$ is a stationary process, and it has been established [Reference Es-Saghouani and Mandjes10, Reference Glynn and Mandjes11, Reference Ott19] that when $\mathbb{E} W^2<\infty$ , the autocovariance $R(t)=\text{Cov}(X_s^*,X_{s+t}^*)$ (or autocorrelation $R(t)/R(0)$ ) is nonnegative, nonincreasing, and convex in t. Where earlier proofs tended to be ad hoc (e.g. dealing only with spectrally one-sided processes, i.e., assuming that the Lévy process has jumps in one direction) and involved (e.g. requiring delicate manipulations with completely monotone functions), with the techniques developed in the present paper this property now follows virtually immediately. The remainder of this subsection illustrates this.

Let us define $p^t(x,A)=\mathbb{P}(X_t(x)\in A)$ , so that $p^t(\cdot,\cdot)$ is the transition kernel of the associated Markov process. Since $X_t(x)=Y_t+L_t\wedge x$ is nondecreasing in x and $X_t(x)-x=Y_t-(x-L_t)^+$ is nonincreasing in x (for each $t>0$ ), we clearly have that

(24) \begin{equation}p^t(x,(y,\infty))=\mathbb{P}(X_t(x)>y)\end{equation}

is nondecreasing in x and

(25) \begin{equation}p^t(x,(x+y,\infty))=\mathbb{P}(X_t(x)>x+y)=\mathbb{P}(Y_t-(x-L_t)^+>y)\end{equation}

is nonincreasing in x. Therefore stochastic monotonicity and Condition 1 are satisfied.

3.2. Lévy process with a two-sided reflection

In this subsection we argue that the structural properties discussed in the previous subsection carry over to the case of a two-sided reflection. With Y as defined in Section 3.1, a two-sided (Skorokhod) reflection in [0, b] for $b>0$ (and similarly in [a, b] for any $a<b$ ) is defined as the unique process $(X_t(x),L_t(x),U_t(x))$ , with $X_t(x)=x+Y_t+L_t(x)-U_t(x)$ , satisfying the following:

1. (i) $L_t(x),\,U_t(x)$ are right-continuous and nondecreasing with $L_0(x)=U_0(x)=0$ .

2. (ii) $X_t(x)\in [0,b]$ for all $t\ge 0$ .

3. (iii) For every $t>0$ such that $L_s(x)<L_t(x)$ (resp., $U_s(x)<U_t(x)$ ) for every $s<t$ , $X_t(x)=0$ (resp., $X_t(x)=b$ ).

Also here, (iii) is equivalent to

(26) \begin{equation}\int_{[0,\infty)}X_t(x)L_{\text{d}t}(x)=\int_{[0,\infty)}(b-X_t(x))U_{\text{d}t}(x)=0.\end{equation}

For this case it is also known that $\mathbb{E} X_t(0)$ is nondecreasing and concave [Reference Andersen and Mandjes1] as well as that for the stationary version the autocovariance R(t) is nonnegative, nondecreasing, and convex [Reference Berkelmans, Cichocka and Mandjes3]. As in the one-sided case, we can apply our newly developed results to establish these facts in a very compact manner provided we verify that the process under consideration is a stochastically monotone Markov process that fulfills Condition 1.

Since Y is a Lévy process, we have that $X_t(x)$ is a time-homogeneous Markov process starting at x. The driving process Y being the same for both $X_t(x)$ and $X_t(y)$ , we find that choosing $x<y$ means that $X_t(x)$ can never overtake $X_t(y)$ . Consequently, $X_t(x)$ is nondecreasing in x and thus the Markov chain is stochastically monotone (with some effort, this can also be shown directly from representation (27) to follow).

In order to verify that it satisfies Condition 1, we recall from [Reference Kruk, Lehoczky, Ramanan and Shreve17], upon re-denoting by $X^0_t(x)$ the one-sided reflected process described in Section 3.1, that

(27) \begin{equation}X_t(x)=X^0_t(x)-\sup_{0\le s\le t}\left[\left(X_s^0(x)-b\right)^+\wedge\inf_{s\le u\le t}X_t^0(x)\right].\end{equation}

Since $X_t^0(x)$ is nondecreasing and $X_t^0(x)-x$ is nonincreasing in x (as explained in Section 3.1), it immediately follows that $X_t(x)-x$ is nonincreasing in x, which implies Condition 1.

Regarding the results for R(t) that hold under stationarity, observe that in this two-sided reflected case a stationary distribution always exists and has a bounded support. Therefore, we do not need to impose any additional requirements on Y. This is in contrast to the one-sided case, where it was necessary to assume that $\mathbb{E} Y_1<0$ and that the stationary distribution has a finite second moment. As in the case with one-sided reflection, the findings carry over to the discrete-time counterpart: the two-sided reflected random walk.

3.3. Lévy dams with a nondecreasing release rule

In the previous two subsections, dealing with the one- and two-sided reflected Lévy process, we mentioned that existing (and also some previously nonexistent) results may be instantly concluded from the theory that we develop in this paper. The present subsection gives an illustration of our theory’s potential to produce similar results for dam processes which, to the best of our knowledge, are completely new for these kinds of processes and were not known earlier. More concretely, it shows that, with the general theory that we developed, the structural results discussed above carry over to more than just reflected Lévy processes.

Let the process $J=\{J_t\,|\,t\ge 0\}$ be a right-continuous subordinator (nondecreasing Lévy process) with $\mathbb{P}(J_0=0)=1$ , and let $r\,:\,[0,\infty)\to [0,\infty)$ be nondecreasing and left-continuous on $(0,\infty)$ , with $r(0)=0$ . Consider the following dam process:

(28) \begin{equation}X_t(x)=x+J_t-\int_0^tr(X_s(x))\text{d}s.\end{equation}

It is well known [Reference Çinlar and Pinsky6] that, under the stated assumptions, the solution to (28) is unique (pathwise) and belongs to the class of time-homogeneous Markov processes.

As before, we need to check that the process under consideration is stochastically monotone and fulfills Condition 1. For $x<y$ we have that

(29) \begin{equation}X_t(y)-X_t(x)=y-x-\int_0^t(r(X_s(y)-r(X_s(x))\text{d}s.\end{equation}

Denote by $\tau$ the first time (if it exists) for which the right side is zero. Because $x<y$ , for every $t<\tau$ we have that $X_t(x)<X_t(y)$ . On $\tau<\infty$ we clearly have that $X_\tau(x)=X_\tau(y)$ , and therefore we also have that for any $h\ge 0$ ,

(30) \begin{align}X_{\tau+h}(x)&=X_\tau(x)+J_{\tau+h}-J_\tau+\int_0^h r(X_{\tau+s}(x))\text{d}s\nonumber\\&=X_\tau(y)+J_{\tau+h}-J_\tau+\int_0^h r(X_{\tau+s}(x))\text{d}s=X_{\tau+h}(y),\end{align}

where the right equality follows from the uniqueness of the solution Z to the equation

(31) \begin{equation}Z_h=z+J_{\tau+h}-J_\tau-\int_0^hr(Z_s)\text{d}s.\end{equation}

Therefore, we have that $X_t(x)\le X_t(y)$ for every $t\ge 0$ . Moreover, note that

(32) \begin{equation}(X_t(x)-x)-(Y_t(y)-y)=\int_0^t(r(X_s(y))-r(X_s(x))\text{d}s,\end{equation}

and thus, since r is assumed to be nondecreasing, we also have that $X_t(x)-x\ge X_t(y)-y$ . The conclusion is that $X_t(x)$ is nondecreasing in x and $X_t(x)-x$ is nonincreasing in x. In other words, the process considered is a stochastically monotone Markov process satisfying Condition 1. As a consequence, the structural properties on $\mathbb{E} X_t$ and R(t), as we discussed above, apply to this process as well. Regarding R(t), we note that here a stationary distribution exists whenever $\mathbb{E} J_1<r(x)$ for some $x>0$ (recalling that $r({\cdot})$ is nondecreasing).

To perform a sanity check, we note that if we choose $r(x)=rx$ , then the resulting process is a (generalized) shot-noise process. In this case it is well known that we can explicitly write

(33) \begin{equation}X_t(x)=xe^{-rt}+\int_{(0,t]}e^{-r(t-s)}J_{\text{d}s}.\end{equation}

In this setting it is immediately clear that $X_t(x)$ is nondecreasing and $X_t(x)-x$ is nonincreasing in x. We observe that here, if $\mathbb{E} X_0^2<\infty$ , then $R(t)=\text{Cov}(X_0,X_t)=\text{Var}(X_0)e^{-rt}$ , so that $R(t)/R(0)=e^{-rt}$ , which is, as expected, nonnegative, nonincreasing, and convex in t (for any distribution of $X_0$ having a finite second moment), and which converges to zero as $t\to\infty$ . It is well known that in this particular case, the stationary distribution has a finite second moment if and only if $J_1$ has a finite second moment. This is equivalent to requiring that $\int_{(1,\infty)}x^2\nu(\text{d}x)<\infty$ , where $\nu$ is the associated Lévy measure.

3.4. Discrete-time (state-dependent) random walks

Consider a discrete-time random walk on $\mathbb{Z}_+$ with the following transition probabilities:

(34) \begin{equation}p_{ij}=\begin{cases}q_i, &i\ge 1,\ j=i-1,\\r_i,&i\ge 0,\ j=i,\\p_i,&i\ge 0,\ j=i+1,\\0&\text{otherwise,}\end{cases}\end{equation}

where $q_i+r_i+p_i=1$ for $i\ge 1$ and $r_0+p_0=1$ . It is a trivial exercise to check that $p(i,A)=\sum_{j\in A}p_{ij}$ is stochastically monotone if and only if $p_{i-1}\le 1-q_i$ for $i\ge 1$ , and that it satisfies Condition 1 if and only if $q_i$ is nondecreasing in i and $p_i$ is nonincreasing in i. From Lemma 2 it may be concluded that these are also the respective conditions for this Markov chain to be stochastically monotone and to satisfy Condition 1. Therefore, the condition that both are satisfied is that for each $i\ge 1$

(35) \begin{equation}p_i\le p_{i-1}\le 1-q_i\le 1-q_{i-1},\end{equation}

where $q_0\equiv 0$ .

From this it immediately follows that if $r_i=0$ for all $i\ge 1$ , then the stochastic monotonicity together with Condition 1 is equivalent to the assumption that $p_i=p$ for $i\ge 0$ and $r_0=q_i=1-p$ for $i\ge 1$ . This is precisely the reflected process associated with $\sum_{k=1}^n Y_k$ (zero for $n=0$ ) where the $Y_k$ are i.i.d. with ${\mathbb P}(Y=1)=1-{\mathbb P}(Y=-1)=p$ , which is a simple special case of Remark 2.

3.5. Birth-and-death processes

Consider a right-continuous birth-and-death process on $\mathbb{Z}_+$ with birth rates $\lambda_i$ , $i\ge 0$ , and death rates $\mu_i\ge 1$ . If the process is explosive we assume that the ‘cemetery’ state is $+\infty$ and that from a possible time of explosion the process remains there forever (a minimal construction, that is).

As observed in [Reference Keilson and Kester16], this Markov process is stochastically monotone. To see this (for the sake of ease of reference), simply start two such independent processes from different initial states. By independence they do not jump at the same time (a.s.), and thus as long as they do not meet in a given state one remains strictly above the other. If and when they do meet (stopping time + strong Markov property) we let them continue together. If the higher process explodes then it remains at infinity forever and thus the bottom process never overtakes the top one. This coupling immediately implies stochastic monotonicity.

Therefore it remains to identify when Condition 1 holds. For the random walk of Subsection 3.4 the condition was that $p_i$ is nonincreasing and $q_i$ is nondecreasing in i. Therefore it is conceivable that the condition here should be that $\lambda_i$ is nonincreasing and $\mu_i$ is nondecreasing in i. This indeed turns out to be correct. In order to see this we will first need the following lemma.

Proof. We use the standard notation ${\mathbb P}_i$ to indicate the probability measure when the initial state is i. Also recall that a right-continuous birth-and-death process is orderly, in the sense that the probability that there are two or more jumps in the interval [0, t] starting from any initial state is o(t). This implies that $\lim_{t\downarrow 0}t^{-1}{\mathbb P}_i(|X^k_t-i|\ge 2)=0$ and thus

(36) \begin{equation}\lim_{t\downarrow0}\frac{1}{t}{\mathbb P}_i(X^k_t\ge i+1)=\lim_{t\downarrow0}\frac{1}{t}{\mathbb P}_i(X_t^k=i+1)=\lambda_i\end{equation}

for $i\ge 0$ . Similarly, $\lim_{t\downarrow0}t^{-1}{\mathbb P}_i(X^k_t\le i-1)=\mu_i$ for $i\ge 1$ .

To show (i) $\Rightarrow$ (ii), suppose that $X_0^1=X_0^2=i$ a.s. (clearly $X^1_0\le_{\text{st}} X^2_0$ ). From $X^1_t\le_{\text{st}}X^2_t$ we have that ${\mathbb P}_i(X_t^1\ge i+1)\le {\mathbb P}_i(X_t^2\ge i+1)$ for $i\ge 0$ and $t>0$ . Dividing by t and letting $t\downarrow 0$ gives $\lambda^1_i\le \lambda^2_i$ . Similarly, since ${\mathbb P}_i(X_t^1\ge i)\le {\mathbb P}_i(X_t^2\ge i)$ we have that ${\mathbb P}_i(X_t^1\le i-1)\le {\mathbb P}_i(X_t^2\ge i-1)$ for $i\ge 1$ and $t>0$ . Dividing by t and letting $t\downarrow 0$ gives $\mu_i^1\ge \mu_i^2$ .

It remains to show (ii) $\Rightarrow$ (i). If we can find a coupling such that $X^1_t\le X^2_t$ a.s. for each $t\ge 0$ , then the lemma instantly follows. It is well known that if $X_0^1\le_{\text{st}}X_0^2$ , then there are $(\tilde X^1_0,\tilde X^2_0)$ such that $\tilde X^k_0=_{\rm d} X^k_0$ and $\tilde X^1_0\le \tilde X^2_0$ a.s. Now assume that $(X^1,X^2)$ is a right-continuous Markov process on $\{(i,j)|\,0\le i\le j\}$ with the following transition rates (with $\mu^1_0=\mu^2_0=0$ ): for $i<j$ we have

(37) \begin{equation}\begin{array}{c@{\quad}c@{\quad}c@{\quad}c@{\quad}c}&&(i,j+1)\\ \\&&{\scriptstyle\lambda^2_j}\Big\uparrow\\ \\(i-1,j)&\stackrel{\mu^1_i}{\longleftarrow}&(i,j)&\stackrel{\lambda^1_i}{\longrightarrow}&(i+1,j)\\ \\&&{\scriptstyle\mu^2_j}\Big\downarrow\\ \\&&(i,j-1)\end{array}\end{equation}

whereas for $i=j$

(38) \begin{equation}\begin{array}{c@{\quad}c@{\quad}c@{\quad}c@{\quad}c}&&(i,i+1)&&(i+1,i+1)\\ \\&&{\scriptstyle\lambda^2_i-\lambda^1_i}\Big\uparrow&{\scriptstyle\lambda^1_i}\nearrow\\ \\(i-1,i)&\stackrel{\mu^1_i-\mu^2_i}{\longleftarrow}&(i,i)\\ \\&{\scriptstyle\mu^2_i}\swarrow\\ \\(i-1,i-1)\end{array}\end{equation}

All other transition rates are zero. Since the process lives on $\{(i,j)|\,0\le i\le j\}$ , it is clear that $X^1_t\le X^2_t$ a.s. for each t. It is easy to check that for each $k=1,2$ , $X^k$ is a birth-and-death process with birth rates $\lambda^k_i$ and death rates $\mu^k_i$ .

Note that the processes suggested in the proof run independently as long as they do not meet, and only if and when they meet does something else happen that ensures that the bottom process does not overtake the top one.