# Recurrence of 2-dimensional queueing processes,
and random walk exit times from the quadrant

Marc PEIGNÉ and Wolfgang WOESS Laboratoire de Mathématiques et Physique
Théorique Université Francois-Rabelais Tours Fédération Denis Poisson – CNRS
Parc de Grandmont, 37200 Tours, France<EMAIL_ADDRESS>Institut für
Diskrete Mathematik, Technische Universität Graz, Steyrergasse 30, A-8010
Graz, Austria<EMAIL_ADDRESS>
(Date: June 15, 2020)

###### Abstract.

Let $X=(X_{1},X_{2})$ be a 2-dimensional random variable and
$X(n),n\in\mathbb{N}$, a sequence of i.i.d. copies of $X$. The associated
random walk is $S(n)=X(1)+\cdots+X(n)$. The corresponding absorbed-reflected
walk $W(n),n\in\mathbb{N}$, in the first quadrant is given by
$W(0)=x\in\mathbb{R}_{+}^{2}$ and $W(n)=\max\\{0,W(n-1)-X(n)\\}$, where the
maximum is taken coordinate-wise. This is often called the Lindley process and
models the waiting times in a two-server queue. We characterize recurrence of
this process, assuming suitable, rather mild moment conditions on $X$. It
turns out that this is directly related with the tail asymptotics of the exit
time of the random walk $x+S(n)$ from the quadrant, so that the main part of
this paper is devoted to an analysis of that exit time in relation with the
drift vector, i.e., the expectation of $X$.

###### Key words and phrases:

Queueing theory, Lindley process, recurrence, random walk in the quadrant,
exit times

###### 2010 Mathematics Subject Classification:

60G50; 60K25; 37Hxx

The first author acknowledges support by a visiting professorship at TU Graz.
The second author was supported by Austrian Science Fund projects FWF P31889
and W1230 as well as from the European Research Council (ERC) under Kilian
Raschel’s Starting Grant Agreement No759702

##  1\. Introduction

The waiting times in a single server queue are modeled as a Markov chain
$W(n)=W^{x}(n)$, $n\geq 0$, on the non-negative half-axis $\mathbb{R}_{+}\,$.
Here, $x\geq 0$ is the initial value, $W(0)=x$, and
$W(n)=\max\\{0,W(n-1)-X(n)\\}$, where the $X(n)$, $n\geq 1$, are i.i.d. real
random variables. We think of this process as an absorbing-reflecting random
walk on $\mathbb{R}_{+}$. Namely, setting $S(n)=X(1)+\dots+X(n)$, the process
evolves as the random walk $x-S(n)$ as long as it stays non-negative. Only
when it attempts to cross $0$ and become negative, the new value is reset to
$0$ before continuing. This is often called the _Lindley process,_ see Lindley
[24]. There is an extensive literature on this Markov chain, such as the
seminal paper by Kendall [19] plus the references therein, and the monographs
by Feller [12], Borovkov [6] and Asmussen [1].

In the present work, we are interested in the multi-dimensional case, and more
precisely, the 2-dimensional one, where the
$X(n)=\bigl{(}X_{1}(n),X_{2}(n)\bigr{)}$ are i.i.d. copies of a 2-dimensional
random variable $X=(X_{1}\,,X_{2})$, the starting point $x$ lies in the non-
negative quadrant of $\mathbb{R}^{2}$, and the maximum in
$W(n)=W^{x}(n)=\max\\{0,W(n-1)-X(n)\\}$ is taken coordinate-wise. There are
various types of multi-dimensional queueing processes. A first rigorous study
is due to Kiefer and Wolfowitz [20]. In that reference, there are several
servers and only one queue, while our process corresponds to having as many
queues as there are servers. Kingman [21], Flatto and McKean [13] and others
studied the model with two servers and two queues, were arriving customers
choose the shorter queue. Greenwood and Shaked [15] touch the model where the
process restarts from the origin whenever just one of the coordinates becomes
negative. Again, this is different from our situation, for which there are not
many references. Regarding recurrence of the 2-dimensional Lindley process,
see e.g. the recent note of Cygan and Kloas [8].

Another viewpoint is to consider the 2-dimensional absorbing-reflecting random
walk $W^{x}(n)$ as a stochastic dynamical system (SDS) evolving in
$\mathbb{R}_{+}^{2}\,$, as in the work of Leguesdron [23], Peigné [25], Benda
[3], [4], [5]. The viewpoint of the last references – inspired by important
work of Babillot, Bougerol and Elie [2] – has been to exploit the fact that
this SDS is obtained by iterating a sequence of i.i.d. random contractions of
$\mathbb{R}_{+}^{2}$, and that it is _locally contractive._ See Peigné and
Woess [26], [27] for the precise definition, an outline of relevant parts of
Benda’s (not easily accessible) work, and further results concerning
conservativity, ergodicity, and invariant measures.

Indeed, when the one-dimensional marginal processes are recurrent – a well-
understood situation, and the one we are interested in here – then our SDS is
_strongly contractive,_ that is

$|W_{n}^{x}-W_{n}^{y}|\to 0\quad\text{almost surely, for all
}\;x,y\in(0\,,\,\infty)^{2}\,.$

This implies that the process is either _transient,_ that is,
$W^{x}(n)\to\infty$ almost surely, or else it is recurrent in the following
sense: there is a closed, non-empty _limit set_
$\mathsf{L}\subset\mathbb{R}_{+}^{2}$ such that for any open set $U$ which
intersects $\mathsf{L}$ and any starting point $x$, we have

(1.1) $\mathbb{P}[W^{x}(n)\in U\;\text{for infinitely many}\;n]=1.$

A main goal of this paper is to understand when the 2-dimensional Lindley
process is recurrent.

###### (1.2) Basic Assumption.

Throughout this paper, we assume that

  * (i)

$\;X$ is not constrained to a hyperplane, and that

  * (ii)

$\;\mathbb{P}[X\in(0\,,\,\infty)^{2}]>0\,.$

This is a quite natural assumption on the support of the distribution of
$X=(X_{1}\,,X_{2})$; see the discussion in §4. Based on this assumption and
the preceding observations, the following is our main result concerning the
two-dimensional Lindley process, with quite general moment assumptions for the
random variable $X$ which models the increments, and its positive and negative
parts $X_{i}^{+}=\max\\{X_{i}\,,0\\}$ and $X_{i}^{-}=\max\\{-X_{i}\,,0\\}$,
$i=1,2$.

###### (1.3) Theorem.

_(a)_ If for at least one $i\in\\{1,2\\}$,

$\mathsf{E}(X_{i}^{+})<\mathsf{E}(X_{i}^{-})\leq\infty\,,$

then $W(n)$ is transient.
_(b)_ If for both $i\in\\{1,2\\}$,

$\mathsf{E}(X_{i}^{-})<\mathsf{E}(X_{i}^{+})<\infty\,,$

then $W(n)$ is positive recurrent.
_(c)_ If for both $i\in\\{1,2\\}$,

$\mathsf{E}(X_{i})=0\quad\text{and}\quad\mathsf{E}\bigl{(}|X_{i}|^{\max\\{2+\delta\,,\,\pi/\arccos(-\rho)\\}}\bigr{)}<\infty\,,$

where $\delta>0$ (arbitrary) and $\rho=\rho(X_{1}\,,X_{2})$ is the correlation
coefficient of $X_{1}$ and $X_{2}\,$, then $W(n)$ is null recurrent if
$\rho\geq 0$, and transient, otherwise.
_(d)_ If for some $\delta>0$, up to a possible exchange of the two
coordinates,

$\mathsf{E}(|X_{i}|^{2+\delta})<\infty\quad\text{for
}\;i=1,2,\quad\mathsf{E}(X_{1})=0,\quad\mathsf{E}(X_{2})>0,\quad\text{and}\quad\mathsf{E}((X_{2}^{-})^{3+\delta})<\infty\,,$

then $W(n)$ is null recurrent.

The two interesting cases are (c) and (d). In order to prove the theorem, we
use the following.

###### (1.4) Definition.

For $x\in(0\,,\,\infty)^{2}\,$, the exit time of the random walk from the
positive quadrant is

$\tau_{x}=\inf\\{n\geq 1:x+S(n)\notin(0\,,\,\infty)^{2}\\}\,.$

In cases (c) and (d), $\tau_{x}$ is almost surely finite. We have the
following relation of the Lindley process with these exit times.

###### (1.5) Lemma.

For $x=(x_{1}\,,x_{2})\in(0\,,\,\infty)^{2}\,$,

$\mathbb{P}\bigl{[}W^{0}(n)\in[0,x_{1})\times[0,x_{2})\bigr{]}=\mathbb{P}[\tau_{x}>n].$

Thus, we are led to another topic of its own big interest, currently the
object of very active work: the tail asymptotics of exit times of random walks
from cones, in our case, the positive quadrant. Our main source is the
profound paper of Denisov and Wachtel [9] on exit times from cones for
centered random walks. As we shall see, this leads to statement (c) of Theorem
1.3. Our main focus is on the case when one coordinate is centered and the
second one has positive drift. Exit times from cones for random walks with
drift were considered by Duraj [11] and Garbit and Raschel [14], who however
do not provide the tail asymptotics which we need. The central body of the
present paper concerns that case. We summarize.

###### (1.6) Theorem.

Under the same moment conditions as in Theorem 1.3, we have the following for
any $x\in(0\,,\,\infty)^{2}\,$, as $n\to\infty$.
In case _(a)_ , if $\;\mathsf{E}(X_{i})<0\;$ and $r\geq 1$ then
$\;\mathsf{E}\bigl{(}(X_{i}^{+})^{r}\bigr{)}<\infty\;$ implies
$\;\mathsf{E}(\tau_{x}^{r})<\infty\,$, whence
$\mathbb{P}[\tau_{x}>n]=\mathfrak{o}(n^{-r})$.
In case _(b)_ ,
$\quad\lim\limits_{n\to\infty}\mathbb{P}[\tau_{x}>n]=\mathbb{P}[\tau_{x}=\infty]>0$
In case _(c)_ , $\quad\mathbb{P}[\tau_{x}>n]\sim
v(x)\,n^{-1/p}\,,\quad\text{where}\quad p=2\arccos(-\rho)/\pi\,.$
In case _(d)_ , $\quad\mathbb{P}[\tau_{x}>n]\sim\kappa\,h(x)\,n^{-1/2}\,.$
In (c) and (d), $v$ and $h$ are positive harmonic functions for the respective
random walk $x+S(n)$ killed when exiting $(0\,,\,\infty)^{2}\,$, and
$\kappa>0$.

(The reader will see below why we prefer not to incorporate the constant
$\kappa$ into $h(x)$.)

These are the main results of the present paper. The main body of the work
consists in the proof of Theorem 1.6(d), preceded by (a)–(c).

In §2, we collect some preliminary facts concerning the one-dimensional
centered case. Furthermore, the asymptotic behaviour of the corresponding
harmonic function on $\mathbb{R}^{+}$ is crucial for us. V. Wachtel has
comunicated to us an improved version, due to himself and D. Denisov, of the
outline in [9, 2.4]. With their kind permission , this is explained in the
Appendix of this paper.

In §3, we provide the proofs of Theorem 1.3. Only in §4, we come back to the
queueing process, i.e., the proofs of Lemma 1.5 and Theorem 1.3 plus
additional observations and a discussion.

##  2\. Dimension one: exit times from the half-line

In this section only, $X$ is a one-dimensional random variable, $X(n)$,
$n\in\mathbb{N}$, are i.i.d. copies of $X$, and $S(n)=X(1)+\dots+X(n)$ (with
$S(0)=0$). For $x\in(0\,,\,\infty)$,

(2.1) $\tau_{x}=\inf\\{n\in\mathbb{N}:x+S(n)\leq 0\\}.$

We collect several facts concerning $\tau_{x}$ and related random variables,
such as

(2.2) $\underline{M\\!}\,(n)=\min\\{S(k):0\leq k\leq
n\\}\quad\text{and}\quad\overline{\\!M}(n)=\max\\{S(k):0\leq k\leq n\\}.$

For the following, see the monograph by Gut [16, Thm. 3.1].

###### (2.3) Lemma.

If $X$ is integrable and $\mathsf{E}(X)<0$ then
$\mathsf{E}(\tau_{x})<\infty\,$. In addition, for any $r\geq 1$,

$\mathsf{E}\bigl{(}(X^{+})^{r}\bigr{)}<\infty\iff\mathsf{E}(\tau_{x}^{r})<\infty\,.$

For the following, [16] is again a good source, as well as the very nice
exposition by Janson [18].

###### (2.4) Lemma.

If $X$ is integrable and $\mathsf{E}(X)>0$ then

$\mathbb{P}[\tau_{x}=\infty]>0\quad\text{and}\quad\underline{M\\!}\,=\inf\\{S(n):n\geq
0\\}>-\infty\quad\text{almost surely,}$

so that $\;T_{\min}=\inf\\{n\geq 0:S(n)=\underline{M\\!}\,\\}<\infty\;$ almost
surely. Furthermore, for any $r>0$,

$\mathsf{E}\bigl{(}(X^{-})^{r+1}\bigr{)}<\infty\iff\mathsf{E}\bigl{(}|\underline{M\\!}\,|^{r}\bigr{)}<\infty\iff\mathsf{E}(\tau_{x}^{r}\,;\,\tau_{x}<\infty)<\infty\iff\mathsf{E}\bigl{(}T_{\min}^{r}\bigr{)}<\infty\,.$

For the remainder of this section, we assume that $X$ is centered.

###### (2.5) Proposition.

Suppose that $\mathsf{E}(X^{2})<\infty$ and $\mathsf{E}(X)=0$. Then the
function

$h_{1}(x)=x-g_{1}(x)\,,\quad\text{where}\quad
g_{1}(x)=\mathsf{E}\bigl{(}x+S(\tau_{x})\,;\,\tau_{x}<\infty\bigr{)}\,,\quad
x>0,$

is finite and harmonic for the random walk killed when exiting
$(0\,,\,\infty)$, that is,

$h_{1}(x)=\mathsf{E}\Bigl{(}h_{1}\bigl{(}x+S(1)\bigr{)}\,;\,\tau_{x}>1\Bigr{)}.$

There is $d>0$ such that

(2.6)
$h_{1}(x)\geq\max\\{x,d\\}\quad\text{and}\quad\lim_{x\to\infty}\frac{h_{1}(x)}{x}=1.$

###### Proof.

As $\mathsf{E}(X^{2})<\infty\,$, finiteness of $g_{1}(x)$ follows from
classical results, see e.g. [12]. Note that $g_{1}(x)\leq 0$, whence
$h_{1}(x_{1})\geq x_{1}\,$. Since $X$ is non-degenerate and centered, there is
$c>0$ such that $\mathbb{P}[X\leq-2c]\geq 1/3$. Thus, if $0<x\leq c$ then
$\mathbb{P}[x+S(1)\leq c]\geq 1/3$, whence $-g_{1}(x)\geq 1/3$. This proves
the first part of (2.6).

Harmonicity is easily proved: Since $\mathsf{E}(X)=0$,

$\displaystyle x$
$\displaystyle=\int_{y>-x}(x+y)\,\mathbb{P}[X=dy]+\int_{y\leq-x}(x+y)\,\mathbb{P}[X=dy]$
$\displaystyle=\mathsf{E}\bigl{(}x+S(1)\,;\,\tau_{x}>1\bigr{)}+\int_{y\leq-x}(x+y)\,\mathbb{P}[X=dy].$

On the other hand, decomposing with respect to the first step of the walk,

$\displaystyle g_{1}(x)$
$\displaystyle=\int_{y>-x}\mathsf{E}\bigl{(}x+y+S(\tau_{x+y})\,;\,\tau_{x+y}<\infty\bigr{)}\,\mathbb{P}[X=dy]+\int_{y\leq-x}(x+y)\,\mathbb{P}[X=dy]$
$\displaystyle=\mathsf{E}\bigl{(}g_{1}\bigl{(}x+S(1)\bigr{)}\,;\,\tau_{x}>1\bigr{)}+\int_{y\leq-x}(x+y)\,\mathbb{P}[X=dy]\,.$

Taking the difference, we get harmonicity of $h_{1}$ as required.

Finally, a proof by D. Denisov and V. Wachtel that $h_{1}(x)/x\to 1$ as
$x\to\infty$ was comunicated to us by V. Wachtel. It is provided in the
Appendix. ∎

In the next section, we shall need an additional estimate related to the
function $g_{1}(x)$. Let $(\ell_{k})_{k\geq 0}$ be the strictly decreasing
ladder indices of $\bigl{(}S(n)\bigr{)}_{n\geq 0}\,$. That is, $\ell_{0}=0$,
and $\ell_{k}=\min\\{n:S(n)<S(\ell_{k-1})\\}$. Then the increments
$S(\ell_{n})-S(\ell_{n-1})$ are i.i.d. and integrable, because
$\mathsf{E}(X^{2})<\infty$. Also, $\tau_{x}=S(\ell_{k})$ for some random $k$
depending on $x>0$.

###### (2.7) Lemma.

For each $m>0$ there is a constant $U(m)>0$ such that

$\mathbb{P}[x+S_{1}(\tau_{x})<-t]\leq
U(m)\,\mathbb{P}[S({\ell_{1}})<-t]\quad\text{for all }\;t>0\,,\;x\in(0,m]\,.$

###### Proof.

For $x>0$, let

$U(x)=\sum_{k=0}^{\infty}\mathbb{P}\bigl{[}S(\ell_{k})\in(-x\,,\,0]\,\bigr{]}\,.$

This is the potential kernel of $\bigl{(}S(\ell_{k})\bigr{)}_{k\geq 0}\,$. It
is finite, since $S(\ell_{k})$ is a sum of i.i.d. random variables tending
almost surely to $-\infty\,$. Then

$\displaystyle\mathbb{P}[x+S_{1}(\tau_{x})<-t]$
$\displaystyle=\sum_{k=1}^{\infty}\mathbb{P}\bigl{[}\tau_{x}=\ell_{k}\,,\;x+S(\ell_{k})<-t\bigr{]}$
$\displaystyle\leq\sum_{k=1}^{\infty}\mathbb{P}\bigl{[}x+S(\ell_{k-1})>0\,,\;S(\ell_{k})-S(\ell_{k-1})<-t\bigr{]}$
$\displaystyle=\sum_{k=1}^{\infty}\mathbb{P}\bigl{[}S(\ell_{k-1})\in(-x\,,\,0]\,\bigr{]}\times\mathbb{P}[S(\ell_{1})<-t\bigr{]}=U(x)\,\mathbb{P}[S(\ell_{1})<-t\bigr{]}\,.$

Since $U(x)\leq U(m)$ for $x\leq m$, this concludes the proof. ∎

We shall also need the following Lemma. The first part is in principle known;
the second part is adapted from Pham [28, Lemma 4.5]. For the sake of
completeness we provide a proof.

###### (2.8) Lemma.

Suppose that $\mathsf{E}(X^{2})<\infty$ and $\mathsf{E}(X)=0$. Then for any
$p>2$ there is a constant $c_{p}>0$ such that when
$\mathsf{E}(|X|^{p})<\infty\,$, for each $t>0$ and $n\in\mathbb{N}$

$\mathsf{E}\bigl{(}|S(n)|^{p}\bigr{)}\leq
c_{p}\,n^{p/2}\,\mathsf{E}\bigl{(}|X|^{p}\bigr{)}\quad\text{and}\quad\mathbb{P}[\,\overline{\\!M}(n)>t]\leq
c_{p}\,\mathsf{E}\bigl{(}|X|^{p}\bigr{)}\,n^{p/2}\,t^{-p}\,.$

Furthermore, for any $\alpha>0$,

$\mathsf{E}\bigl{(}n^{1/2}+\overline{\\!M}(n)\,;\,\overline{\\!M}(n)>n^{1/2+\alpha}\bigr{)}\leq
c_{p}\,\mathsf{E}\bigl{(}|X|^{p}\bigr{)}\,\frac{2p-1}{p-1}\,n^{1/2-(p-1)\alpha}\,.$

###### Proof.

Since $\bigl{(}S(n)\bigr{)}$ is a martingale, Doob’s maximal inequality
implies

$\mathbb{P}[\,\overline{\\!M}(n)>t]\leq\mathsf{E}\bigl{(}|S(n)|^{p}\bigr{)}\,t^{-p}\,.$

By a well-known inequality which one finds e.g. in Burkholder [7, Proof of
Thm. 3.2],

$\mathsf{E}\bigl{(}|S(n)|^{p}\bigr{)}\leq
c_{p}\,\mathsf{E}\biggl{(}\Bigl{(}\sum_{k=1}^{n}X(k)^{2}\Bigr{)}^{p/2}\biggr{)}.$

Now Hölder’s inequality concludes the proof of the first two inequalities. For
the third inequality,

$\displaystyle\mathsf{E}\bigl{(}n^{1/2}+\overline{\\!M}(n)$
$\displaystyle;\,\overline{\\!M}(n)>n^{1/2+\alpha}\bigr{)}$
$\displaystyle=\bigl{(}n^{1/2}+n^{1/2+\alpha}\bigr{)}\,\mathbb{P}\bigl{[}\,\overline{\\!M}(n)>n^{1/2+\alpha}\bigr{]}+\mathsf{E}\Bigl{(}\bigl{(}\,\overline{\\!M}(n)-n^{1/2+\alpha}\bigr{)}^{+}\Bigr{)}$
$\displaystyle\leq
2n^{1/2+\alpha}\,\mathbb{P}\bigl{[}\,\overline{\\!M}(n)>n^{1/2+\alpha}\bigr{]}+\int_{n^{1/2+\alpha}}^{\infty}\mathbb{P}\bigl{[}\,\overline{\\!M}(n)>t\bigr{]}\,dt$
$\displaystyle\leq
2\,c_{p}\,\mathsf{E}\bigl{(}|X|^{p}\bigr{)}\,n^{1/2-(p-1)\alpha}+c_{p}\,\mathsf{E}\bigl{(}|X|^{p}\bigr{)}\int_{n^{1/2+\alpha}}^{\infty}n^{p/2}\,t^{-p}\,dt$
$\displaystyle=c_{p}\,\mathsf{E}\bigl{(}|X|^{p}\bigr{)}\,\frac{2p-1}{p-1}\,n^{1/2-(p-1)\alpha}\,,$

as proposed. ∎

Uniform convergence in the following proposition was proved by Doney [10].

###### (2.9) Proposition.

If $\mathsf{E}\bigl{(}|X|^{2}\bigr{)}<\infty$ and $\mathsf{E}(X)=0$, then

$\mathbb{P}[\tau_{x}>n]\sim\kappa\,h_{1}(x)\,n^{-1/2}\,,\quad\text{where}\quad\kappa=\bigl{(}\pi\,\operatorname{\sf
Var}(X)/2\bigr{)}^{-1/2}\,,$

uniformly as $n\to\infty$ and $0<x<\theta_{n}\,n^{1/2}$, where $(\theta_{n})$
is an arbitrary positive sequence that converges to $0$.

##  3\. Dimension two: exit times from the quadrant

This section is devoted to the proof of Theorem 1.6. We return to the
situation of the Introduction, where $X=(X_{1}\,,X_{2})$ and the $X(n)$ are
i.i.d. copies of $X$. Thus, $S(n)=\bigl{(}S_{1}(n),S_{2}(n)\bigr{)}$, and if
$x=(x_{1}\,,x_{2})\in(0\,,\,\infty)^{2}$ then

(3.1)
$\tau_{x}=\min\\{\tau_{x_{1}}\,,\tau_{x_{2}}\\}\,,\quad\text{where}\quad\tau_{x_{i}}=\tau_{i,x_{i}}=\inf\\{n\in\mathbb{N}:x_{i}+S_{i}(n)\leq
0\,,\;i=1,2\\}\,.$

Negative drift in at least one coordinate

###### Proof of Theorem 1.6(a).

It is well known that if $\mathsf{E}(X_{i})<0$ then
$\;\mathsf{E}\bigl{(}(X_{i}^{+})^{r}\bigr{)}<\infty\;$ if and only if
$\;\mathsf{E}(\tau_{x_{i}}^{r})<\infty\,$, see e.g. [12], [16] and [18]. In
view of (3.1), this implies $\mathsf{E}(\tau_{x}^{r})<\infty\,$. ∎

Positive drift in both coordinates

###### Proof of Theorem 1.6(b).

We use Lemma 2.4 and set $\underline{M\\!}\,_{i}=\inf\\{S_{i}(n):n\geq 0\\}$.
These random variables are almost surely finite. Therefore, for every $n$,

$\mathbb{P}[\tau_{x}>n]=\mathbb{P}[\tau_{x_{1}}>n\,,\,\tau_{x_{2}}>n]\geq\mathbb{P}[\underline{M\\!}\,_{1}<-x_{1}\,,\,\underline{M\\!}\,_{2}<-x_{2}]\to
1\,,\quad\text{as }\;x_{1}\,,x_{2}\to\infty.$

Thus, there is $b>0$ such that $\mathbb{P}[\tau_{x}=\infty]\geq 1/2$ if
$x_{1}\,,x_{2}>b$. If $x\in(0\,,\,\infty)^{2}$ is arbitrary then the Basic
Assumption 1.2, namely that $\mathbb{P}[X\in(0\,,\,\infty)^{2}]>0$ yields that
with positive probability, the random walk $x+S(n)$ starting at $x$ can reach
$(b\,,\,\infty)\times(b\,,\,\infty)$ without exiting $(0\,,\,\infty)^{2}$.
Therefore $\mathbb{P}[\tau_{x}=\infty]>0$. ∎

The centered case

###### Proof of Theorem 1.6(c).

We assume that both coordinates of $X$ have finite moment of order
$\max\\{2+\delta\,,\,\pi/\arccos(-\rho)\\}$ and are centered, with some
$\delta>0$ and $\rho=\rho(X_{1}\,,X_{2})\in(-1\,,\,1)$.

The result is in principle stated in [9, Example 2]. For the sake of
completeness, we give a few hints. Let $\mathbb{K}_{\alpha}$ be a standard
closed cone in $\mathbb{R}^{2}$: the sides of the cone are two half-lines
issuing from the origin, which is the cone’s vertex. The opening angle of the
cone is $\alpha\in(0\,,\,\pi)$. On $\mathbb{K}_{\alpha}\,$, the paper [9]
considers a random walk $\tilde{x}+\widetilde{S}(n)$ with
$\tilde{x}\in\mathbb{K}_{\alpha}^{o}$ and
$\widetilde{S}(n)=\widetilde{X}(1)+\dots+\widetilde{X}(n)$, where the
$\widetilde{X}(n)$ are i.i.d. copies of
$\widetilde{X}=(\widetilde{X}_{1}\,,\widetilde{X}_{2})$. The assumptions are
that the coordinates of $\widetilde{X}$ have finite moment of order
$\max\\{2+\delta\,,\,\pi/\alpha\\}$, are centered, with
$\mathsf{E}(\widetilde{X}_{i}^{2})=1$ and
$\rho(\widetilde{X}_{1}\,,\widetilde{X}_{2})=\mathsf{E}(\widetilde{X}_{1}\widetilde{X}_{2})=0$.
For the associated exit time $\widetilde{\tau}_{\tilde{x}}\,$, the main
results of [9] yield that

$\mathbb{P}[\widetilde{\tau}_{\tilde{x}}>n]\sim
V(\tilde{x})\,n^{-1/p}\,,\quad\text{where}\quad p=2\alpha/\pi\,.$

Thus, the method is to decorrelate $X_{1}$ and $X_{2}$ and thereby to pass
from $\mathbb{R}_{+}^{2}$ to a possibly modified cone. This can for example be
achieved by the matrix transformation

$\begin{pmatrix}\widetilde{X}_{1}\\\
\widetilde{X}_{2}\end{pmatrix}=M\,\begin{pmatrix}X_{1}\\\
\widetilde{X}_{2}\end{pmatrix}\,,\quad\text{where}\quad
M=\begin{pmatrix}\frac{1}{\sigma_{1}}&0\\\\[4.0pt]
\frac{-\rho}{\sigma_{1}\sqrt{1-\rho^{2}}}&\frac{1}{\sigma_{2}}\end{pmatrix}$

Here, $\sigma_{i}^{2}=\mathsf{E}(X_{i}^{2})$. Then
$(\widetilde{X}_{1}\,,\widetilde{X}_{2})$ are centered, with variances $=1$,
and non correlated. The mapping $x\mapsto Mx$ transforms $\mathbb{R}_{+}^{2}$
in a cone $\mathbb{K}_{\alpha}$ with $\alpha=\arccos(-\rho)$. Thus, we have

$\mathbb{P}[\tau_{x}>n]=\mathbb{P}[\widetilde{\tau}_{Mx}>n]\sim
V(Mx)\,n^{-1/p}\,,\quad\text{where}\quad p=2\arccos(-\rho)/\pi\,.$

Since $V(\tilde{x})$ is positive harmonic for the random walk killed when
exiting $\mathbb{K}_{\alpha}^{o}$, the function $v(x)=V(Mx)$ is positive
harmonic for the original random walk killed when exiting
$(0\,,\,\infty)^{2}$. ∎

The mixed case positive drift - zero drift

We finally come to the main body of this paper, namely the proof of statement
(d) of Theorem 1.6. We repeat that we assume that $X_{1}$ is centered with
moment of order $2+\delta$ and that $X_{2}$ has finite second moment,
$\mathfrak{m}=\mathsf{E}(X_{2})>0$ and in addition
$\mathsf{E}\bigl{(}(X_{2}^{-})^{3+\delta}\bigr{)}<\infty$ for some $\delta>0$.

The first step consists in finding the right harmonic function for the random
walk restricted to the quadrant. For this, we were inspired by the work of
Ignatiouk-Robert and Loree [17], who however assume exponential moment
conditions.

###### (3.2) Proposition.

Under the assumptions (d), the function

$h(x)=x_{1}-\mathsf{E}\bigl{(}x_{1}+S_{1}(\tau_{x})\,;\,\tau_{x}<\infty\bigr{)}\,,\quad
x\in(0\,,\,\infty)^{2}\,,$

is strictly positive and harmonic for the random walk killed upon exiting the
positive quadrant. It satisfies

(3.3) $h(x)\leq
h_{1}(x_{1})\quad\text{and}\quad\lim_{x_{2}\to\infty}\frac{h(x)}{h_{1}(x_{1})}=1\quad\text{uniformly
for }\;0<x_{1}\leq x_{2}^{2+\delta}\,,$

where $h_{1}$ is the function of Proposition 2.5.

###### Proof.

The proof that $h$ is harmonic is a straightforward adaptation of the proof in
the one-dimensional case, Proposition 2.5.

Write
$g(x)=\mathsf{E}\bigl{(}x_{1}+S_{1}(\tau_{x})\,;\,\tau_{x}<\infty\bigr{)}$.
Then by (3.1),

$\displaystyle g(x)$
$\displaystyle=\tilde{g}(x)+f(x)=g_{1}(x_{1})-\tilde{f}(x)+f(x)\,,\quad\text{where}$
$\displaystyle\tilde{g}(x)$
$\displaystyle=\mathsf{E}\bigl{(}x_{1}+S_{1}(\tau_{x_{1}})\,;\,\tau_{x_{1}}\leq\tau_{x_{2}}\,,\;\tau_{x_{1}}<\infty\bigr{)}\,,$
$\displaystyle f(x)$
$\displaystyle=\mathsf{E}\bigl{(}x_{1}+S_{1}(\tau_{x_{2}})\,;\,\tau_{x_{2}}<\tau_{x_{1}}<\infty\bigr{)}\,,\quad\text{and}\quad$
$\displaystyle\tilde{f}(x)$
$\displaystyle=\mathsf{E}\bigl{(}x_{1}+S_{1}(\tau_{x_{1}})\,;\,\tau_{x_{2}}<\tau_{x_{1}}<\infty\bigr{)}\,,$

and $g_{1}$ is the function from Proposition 2.5. Since $\tilde{f}(x)\leq 0$
and $f(x)\geq 0$, we see that $g(x)\geq g_{1}(x_{1})$, whence $h(x)\leq
h_{1}(x_{1})$.
Claim 1. $\lim\limits_{x_{2}\to\infty}f(x)=0\quad\text{uniformly for
}\;0<x_{1}\leq x_{2}^{2+\delta}\,.$

To prove this, we use Lemma 2.4: since
$\mathsf{E}\bigl{(}(X_{2}^{-})^{3+\delta}\bigr{)}<\infty\,$,

$\mathsf{E}(\tau_{x_{2}}^{2+\delta}\,;\,\tau_{x_{2}}<\infty)<\infty\quad\text{and}\quad\mathsf{E}(\underline{M\\!}\,_{2}^{2+\delta}\,;\,\tau_{x_{2}}<\infty)<\infty\,,$

where $\underline{M\\!}\,_{2}=\inf\\{S_{2}(n):n\geq 0\\}\,$. Write
$\sigma_{1}^{2}=\mathsf{E}(X_{1}^{2})$, and recall that $\tau_{x_{1}}<\infty$
almost surely. For every $k\in\mathbb{N}$, using the Cauchy-Schwarz
inequality,

$\mathsf{E}\bigl{(}x_{1}+S_{1}(k)\,;\,\tau_{x_{1}}>\tau_{x_{2}}=k\bigr{)}\leq
x_{1}\,\mathbb{P}[\tau_{x_{1}}>\tau_{x_{2}}=k]+\underbrace{\mathsf{E}\bigl{(}S_{1}(k)^{2}\bigr{)}^{1/2}}_{\displaystyle\sigma_{1}\,k^{1/2}}\,\mathbb{P}[\tau_{x_{2}}=k]^{1/2}$

We again use the Cauchy-Schwarz inequality in the following estimate.

(3.4) $\displaystyle
f(x)=\sum_{k=1}^{\infty}\mathsf{E}\bigl{(}x_{1}+S_{1}(k)\,;\,\tau_{x_{1}}>\tau_{x_{2}}=k\bigr{)}$
$\displaystyle\leq
x_{1}\,\mathbb{P}[\tau_{x_{1}}>\tau_{x_{2}}]+\sigma_{1}\sum_{k=1}^{\infty}k^{-(1+\delta)/2}\cdot
k^{(2+\delta)/2}\,\mathbb{P}[\tau_{x_{2}}=k]^{1/2}$ $\displaystyle\leq
x_{1}\,\mathbb{P}[\tau_{x_{1}}>\tau_{x_{2}}]+C_{\delta}\,\mathsf{E}(\tau_{x_{2}}^{2+\delta}\,;\,\tau_{x_{2}}<\infty)^{1/2}\,,\quad\text{where}\quad
C_{\delta}=\sigma_{1}\,\left(\sum_{k=1}^{\infty}k^{-(1+\delta)}\right)^{\\!1/2}.$

Now, our moment assumption implies that

(3.5)
$\mathbb{P}[\tau_{x_{2}}<\infty]\leq\mathbb{P}[\underline{M\\!}\,_{2}\leq-
x_{2}]=\mathfrak{o}(x_{2}^{-(2+\delta)})\quad\text{as }\;x_{2}\to\infty\,.$

Therefore

$\lim_{x_{2}\to\infty}x_{1}\,\mathbb{P}[\tau_{x_{1}}>\tau_{x_{2}}]=0\quad\text{uniformly
for }\;0<x_{1}\leq x_{2}^{2+\delta}\,.$

For the second term, we use Lemma 2.4, with $T_{\min}$ referring to the second
coordinate:

$\tau_{x_{2}}^{2+\delta}\,\mathbf{1}_{[\tau_{x_{2}}<\infty]}\leq
T_{\min}^{2+\delta}\,\mathbf{1}_{[\tau_{x_{2}}<\infty]}\;\leq
T_{\min}^{2+\delta}\,,$

and the middle term tends to $0$ almost surely, as $x_{2}\to\infty\,$. By
dominated convergence,

(3.6)
$\lim_{x_{2}\to\infty}\mathsf{E}(\tau_{x_{2}}^{2+\delta}\,;\,\tau_{x_{2}}<\infty)=0.$

This concludes the proof of Claim 1.
Claim 2.
$\lim\limits_{x_{2}\to\infty}\dfrac{\tilde{f}(x)}{h_{1}(x_{1})}=0\quad\text{uniformly
for }\;x_{1}\in(0\,,\,\infty)\,.$

To verify this, we first note that since $0\leq-\tilde{g}(x)\leq-
g_{1}(x_{1})$, we get from Proposition 2.5, resp. the Appendix, that

$\lim_{x_{1}\to\infty}\frac{\tilde{g}(x)}{h_{1}(x_{1})}=\lim_{x_{1}\to\infty}\frac{\tilde{f}(x)}{h_{1}(x_{1})}=0\quad\text{uniformly
in }\;x_{2}\,.$

Second, Lemma 2.7 yields equintegrability of
$R_{x_{1}}=\bigl{(}-x_{1}-S_{1}(\tau_{x_{1}})\bigr{)}\,\mathbf{1}_{[\tau_{x_{1}}<\infty]}$
for $x_{1}\in[0\,,\,m]$, for each $m>0$. Note that $R_{x_{1}}\geq 0\,$. Since
$\mathbb{P}[\tau_{x_{2}}<\infty]\to 0$ as $x_{2}\to\infty$ by (3.5), a
standard argument yields that for each $m>0$,

$\lim_{x_{2}\to\infty}\tilde{f}(x)=0\quad\text{uniformly for
}x_{1}\in[0\,,\,m].$

Indeed, for $x_{1}\in[0\,,\,m]$ and any $t>0$,

$\displaystyle-\tilde{f}(x)$
$\displaystyle\leq\mathsf{E}(R_{x_{1}}\,;\,\tau_{x_{2}}<\infty)$
$\displaystyle\leq t\,\mathbb{P}[R_{x_{1}}\leq
t\,,\;\tau_{x_{2}}<\infty]+\mathsf{E}(R_{x_{1}}\,;\,R_{x_{1}}>t)$
$\displaystyle\leq
t\,\mathbb{P}[\tau_{x_{2}}<\infty]+t\,\mathbb{P}[R_{x_{1}}>t]+\sum_{n\geq
t}\mathbb{P}[R_{x_{1}}>t+n]$ $\displaystyle\leq
t\,\mathbb{P}[\tau_{x_{2}}<\infty]+U(m)\,t\,\mathbb{P}[S(\ell_{1})<-t]+U(m)\sum_{n\geq
t}\mathbb{P}[S(\ell_{1})<-(t+n)]\,.$

Since $S(\ell_{1})$ is negative and integrable, the second and third term in
the last line tend to $0$ as $t\to\infty$. Thereafter, we can chose $x_{2}$
large enough so that also the first term is small. Recalling from (2.6) that
$h_{1}$ is bounded away from zero, we also get that
$\tilde{f}(x)/h_{1}(x_{1})\to 0$ uniformly for $x_{1}\in[0\,,\,m]$ as
$x_{2}\to\infty\,$.

Combining the two parts, we see that Claim 2 is true.

Again using that $h_{1}$ is bounded away from 0, Claims 1 and 2 prove (3.3).
Claim 3. $h(x)\geq 0\quad\text{for all }\;x\in(0\,,\,\infty)^{2}\,$.

To see this, recall that $0\leq-\tilde{g}(x)\leq-g_{1}(x_{1})<\infty$, while
we know from Claim 1 that $0\leq f(x)<\infty$. Therefore

$\mathsf{E}\bigl{(}|x_{1}+S_{1}(\tau_{x})|\,;\,\tau_{x}<\infty\bigr{)}<\infty\,,$

and by dominated convergence and the martingale stopping lemma,

$\displaystyle g(x)$
$\displaystyle=\lim_{n\to\infty}g_{n}(x)\,,\qquad\text{where}$ $\displaystyle
g_{n}(x)$
$\displaystyle=\mathsf{E}\bigl{(}x_{1}+S_{1}(\tau_{x})\,;\,\tau_{x}\leq
n\bigr{)}$
$\displaystyle=\underbrace{\mathsf{E}\bigl{(}x_{1}+S_{1}(\min\\{n,\tau_{x}\\})\bigr{)}}_{\displaystyle=x_{1}}-\mathsf{E}\bigl{(}\underbrace{x_{1}+S_{1}(n)}_{\displaystyle>0}\,;\,\tau_{x}>n\bigr{)}\leq
x_{1}\,.$

This proves Claim 3.

It remains to prove that $h>0$ strictly on $(0\,,\,\infty)^{2}$. Since
$\tilde{g}(x)\leq 0$, the estimate (3.4) plus the first inequality in (3.5)
lead to

$h(x)\geq x_{1}-f(x)\geq
x_{1}\,\mathbb{P}[\,\underline{M\\!}\,_{2}>-x_{2}]-C_{\delta}\,\mathsf{E}(\tau_{x_{2}}^{2+\delta}\,;\,\tau_{x_{2}}<\infty)^{1/2}.$

By (3.6), this yields that for every $b_{1}>0$ (possibly small) there is
$b_{2}>0$ (possibly large) such that $h>0$ on
$(b_{1}\,,\,\infty)\times(b_{2}\,,\,\infty)$. Now, by the Basic Assumption
1.2, there is $(a_{1}\,,a_{2})\in(0\,,\,\infty)^{2}$ such that
$\mathbb{P}[X\in(a_{1}\,,\,\infty)\times(a_{2}\,,\,\infty)]>0$. Inductively,
we get

$\mathbb{P}[S(k)\in(k\,a_{1}\,,\,\infty)\times(k\,a_{2}\,,\,\infty)\;\text{for}\;k=1,\dots,n]>0$

for every $n\in\mathbb{N}$. Now let $x\in(0\,,\,\infty)^{2}$. Given $x_{1}\,$,
by the above there is $b_{2}$ such that $h>0$ on
$(x_{1}\,,\,\infty)\times(b_{2}\,,\,\infty)$. Then there is $n$ such that
$x_{2}+n\,a_{2}\geq b_{2}$. But then

$\mathbb{P}[x+S(n)\in(x_{1}\,,\,\infty)\times(b_{2}\,,\,\infty)\,,\tau_{x}>n]>0\,.$

Therefore, since we already know that $h\geq 0$,

$\displaystyle h(x)$
$\displaystyle=\mathsf{E}\Bigl{(}h\bigl{(}x+S(n)\bigr{)}\,;\,\tau_{x}>n\bigr{)}\Bigr{)}$
$\displaystyle\geq\mathsf{E}\Bigl{(}h\bigl{(}x+S(n)\bigr{)}\,;\,x+S(n)\in(x_{1}\,,\,\infty)\times(b_{2}\,,\,\infty)\,,\tau_{x}>n\bigr{)}\Bigr{)}>0\,.$

This completes the proof of the proposition. ∎

We now choose $\varepsilon\in(0\,,\,1/2)$ and define for
$x=(x_{1}\,,x_{2})\in(0\,,\,\infty)^{2}$

$\nu_{x_{2}}(n)=\inf\\{k\in\mathbb{N}:x_{2}+S_{2}(k)\geq\mathfrak{m}\,n^{1-3\varepsilon/2}\\}.$

(Recall that $\mathfrak{m}=\mathsf{E}(X_{2})$.)

###### (3.7) Lemma.

$\mathbb{P}[\nu_{x_{2}}(n)>n^{1-\varepsilon}]\leq
C\,n^{-(1-\varepsilon)(1+\delta/2)}\,.$

###### Proof.

Let $\sigma_{2}^{2}=\operatorname{\sf Var}(X_{2})$. Setting $p=2+\delta$, we
apply the first inequality in Lemma 2.8 to $X_{2}-\mathfrak{m}$ and use
Markov’s inequality111Here and in many subsequent instances, values such as
$n^{1-\varepsilon}$ should be rounded to the next lower, resp. upper integer.
This is omitted in the notation, since it will be clear from the context.:

$\displaystyle\mathbb{P}\bigl{[}\nu_{x_{2}}(n)>n^{1-\varepsilon}\bigr{]}$
$\displaystyle\leq\mathbb{P}\bigl{[}x_{2}+S_{2}(n^{1-\varepsilon})<\mathfrak{m}\,n^{1-3\varepsilon/2}\bigr{]}$
$\displaystyle\leq\mathbb{P}\bigl{[}S_{2}(n^{1-\varepsilon})-\mathfrak{m}\,n^{1-\varepsilon}<-\mathfrak{m}\,(1-n^{-\varepsilon/2})\,n^{1-\varepsilon}\bigr{]}$
$\displaystyle\leq\mathbb{P}\bigl{[}\,|S_{2}(n^{1-\varepsilon})-\mathfrak{m}\,n^{1-\varepsilon}|^{p}>\bigl{(}\mathfrak{m}\,(1-n^{-\varepsilon/2})\bigr{)}^{p}\,n^{(1-\varepsilon)p}\bigr{]}$
$\displaystyle\leq\frac{c_{p}\,n^{(1-\varepsilon)p/2}\,\mathsf{E}\bigl{(}|X_{2}-\mathfrak{m}|^{p}\bigr{)}}{\bigl{(}\mathfrak{m}\,(1-n^{-\varepsilon/2})\bigr{)}^{p}\,n^{(1-\varepsilon)p}}\,.$

This proves the lemma. ∎

###### Proof of Theorem 1.6(d).

We choose $s$, $\varepsilon$ and $\phi_{n}$ as follows.

(3.8)
$\varepsilon=\frac{1}{2}-\frac{1}{s}\quad\text{and}\quad\phi_{n}=n^{-\varepsilon/s}+n^{-\varepsilon}\,,\quad
s>2\,.$

For the starting point $x\in(0\,,\,\infty)^{2}$, we assume that
$x_{1}<n^{1/2-\varepsilon}=n^{1/s}$ and
$x_{2}<\mathfrak{m}\,n^{1-3\varepsilon/2}$.

$\displaystyle\mathbb{P}[\tau_{x}>n]=\mathbb{P}[\tau_{x}>n\,;\,\nu_{x_{2}}(n)\leq
n^{1-\varepsilon}]$ $\displaystyle+\mathbb{P}[\nu_{x_{2}}(n)\geq\tau_{x}>n]$
$\displaystyle+\mathbb{P}[\tau_{x}>n\,;\,\tau_{x}>\nu_{x_{2}}(n)>n^{1-\varepsilon}]$
$\displaystyle=\mathbb{P}[\tau_{x}>n\,;\,\nu_{x_{2}}(n)\leq
n^{1-\varepsilon}]$ $\displaystyle+\mathfrak{o}(n^{-1/2}),$

because by Lemma 3.7,

$\mathbb{P}[\nu_{x_{2}}(n)\geq\tau_{x}>n]+\mathbb{P}[\tau_{x}>n\,;\,\tau_{x}>\nu_{x_{2}}(n)>n^{1-\varepsilon}]\leq\mathbb{P}[\nu_{x_{2}}(n)>n^{1-\varepsilon}]\leq
C\,n^{-(1-\varepsilon)(1+\delta/2)}\,.$

Now we write

$\displaystyle\mathbb{P}[\tau_{x}>n\,;\,\nu_{x_{2}}(n)\leq n^{1-\varepsilon}]$
$\displaystyle\qquad=\sum_{k=1}^{n^{1-\varepsilon}}\int_{y\,:\,y_{2}\,\geq\,\mathfrak{m}\,n^{1-3\varepsilon/2}}\mathbb{P}[\tau_{x}>k\,,\;\nu_{x_{2}}(n)=k\,,\;x+S(k)=dy]\,\,\mathbb{P}[\tau_{y}>n-k]\,.$

We note that $\mathbb{P}[\tau_{y_{1}}>n-k]-\mathbb{P}[\tau_{y_{2}}\leq
n]\leq\mathbb{P}[\tau_{y}>n-k]\leq\mathbb{P}[\tau_{y_{1}}>n-k]$. By (3.5), we
have for $y_{2}\geq\mathfrak{m}\,n^{1-3\varepsilon/2}$ that

$\mathbb{P}[\tau_{y}>n-k]=\mathbb{P}[\tau_{y_{1}}>n-k]+\mathfrak{o}(n^{-(1-3\varepsilon/2)(2+\delta)})=\mathbb{P}[\tau_{y_{1}}>n-k]+\mathfrak{o}(n^{-1/2})$

by our choices of $\varepsilon$ and $s$. Therefore, independently of the
choice of $x$,

$\displaystyle\mathbb{P}[\tau_{x}>n\,;\,\nu_{x_{2}}(n)\leq n^{1-\varepsilon}]$
$\displaystyle\quad=\sum_{k=1}^{n^{1-\varepsilon}}\int_{y\,:\,y_{2}\,\geq\,\mathfrak{m}\,n^{1-3\varepsilon/2}}\mathbb{P}[\tau_{x}>k\,,\;\nu_{x_{2}}(n)=k\,,\;x+S(k)=dy]\,\,\mathbb{P}[\tau_{y_{1}}>n-k]\;+\mathfrak{o}(n^{-1/2})$
$\displaystyle\quad=\textbf{A}+\textbf{B}+\mathfrak{o}(n^{-1/2})\,,\qquad\qquad\text{where}$
$\displaystyle\quad\textbf{A}=\sum_{k=1}^{n^{1-\varepsilon}}\int_{\scriptstyle
y\,:\,y_{2}\,\geq\,\mathfrak{m}\,n^{1-3\varepsilon/2}\atop\scriptstyle
y_{1}\,\leq\,\phi_{n}\,n^{1/2}}\mathbb{P}[\tau_{x}>k\,,\;\nu_{x_{2}}(n)=k\,,\;x+S(k)=dy]\,\,\mathbb{P}[\tau_{y_{1}}>n-k]\quad\text{and}\quad$
$\displaystyle\quad\textbf{B}=\sum_{k=1}^{n^{1-\varepsilon}}\int_{\scriptstyle
y\,:\,y_{2}\,\geq\,\mathfrak{m}\,n^{1-3\varepsilon/2}\atop\scriptstyle
y_{1}\,>\,\phi_{n}\,n^{1/2}}\mathbb{P}[\tau_{x}>k\,,\;\nu_{x_{2}}(n)=k\,,\;x+S(k)=dy]\,\,\mathbb{P}[\tau_{y_{1}}>n-k]\,.$

By propositions 2.5, 2.9 and 3.2, we have with
$\kappa=(\pi\,\sigma_{2}^{2}/2)^{-1/2}$

$\mathbb{P}[\tau_{y_{1}}>n-k]\sim\kappa\,h_{1}(y_{1})\,n^{-1/2}\sim\kappa\,h(y)\,n^{-1/2}$

uniformly for $y$ in the range of integration of term A and $k\leq
n^{1-\varepsilon}$. Therefore

A
$\displaystyle\sim\kappa\,n^{-1/2}\,\mathsf{E}\biggl{(}h\Bigl{(}x+S\bigl{(}\nu_{x_{2}}(n)\bigr{)}\Bigr{)}\,;\,{\displaystyle\tau_{x}>\nu_{x_{2}}(n)\,,\;\nu_{x_{2}}(n)\leq
n^{1-\varepsilon}\,,\;\atop\displaystyle
x_{1}+S_{1}\bigl{(}\nu_{x_{2}}(n)\bigr{)}\leq\phi_{n}\,n^{1/2}}\biggr{)}$
$\displaystyle=\kappa\,n^{-1/2}(\textbf{C}-\textbf{D})\,,\qquad\text{where}$ C
$\displaystyle=\mathsf{E}\Bigl{(}h\Bigl{(}x+S\bigl{(}\nu_{x_{2}}(n)\bigr{)}\Bigr{)}\,;\,\tau_{x}>\nu_{x_{2}}(n)\,,\;\nu_{x_{2}}(n)\leq
n^{1-\varepsilon}\Bigr{)}\quad\quad\text{and}\quad$ D
$\displaystyle=\mathsf{E}\Bigl{(}h\Bigl{(}x+S\bigl{(}\nu_{x_{2}}(n)\bigr{)}\Bigr{)}\,;\,\tau_{x}>\nu_{x_{2}}(n)\,,\;\nu_{x_{2}}(n)\leq
n^{1-\varepsilon}\,,\;x_{1}+S_{1}\bigl{(}\nu_{x_{2}}(n)\bigr{)}>\phi_{n}\,n^{1/2}\Bigr{)}.$

Also, $\mathbb{P}[\tau_{y_{1}}>n-k]\leq C\,y_{1}\,n^{-1/2}$ for $y$ in the
range of integration of term B. Therefore we get that both
$n^{1/2}\,\textbf{B}$ and D are bounded above by $C\,\textbf{D}^{\prime}$,
where

$\displaystyle\textbf{D}^{\prime}$
$\displaystyle=\mathsf{E}\Bigl{(}x_{1}+S_{1}\bigl{(}\nu_{x_{2}}(n)\bigr{)}\,;\,\tau_{x}>\nu_{x_{2}}(n)\,,\;\nu_{x_{2}}(n)\leq
n^{1-\varepsilon}\,,\;x_{1}+S_{1}\bigl{(}\nu_{x_{2}}(n)\bigr{)}>\phi_{n}\,n^{1/2}\Bigr{)}$
$\displaystyle\leq
C\,\mathsf{E}\bigl{(}n^{1/2-\varepsilon}+\overline{\\!M}_{1}(n^{1-\varepsilon})\,;\,n^{1/2-\varepsilon}+\overline{\\!M}_{1}(n^{1-\varepsilon})>\phi_{n}\,n^{1/2}\bigr{)}\,.$

We now apply Lemma 2.8 to the first marginal. We have
$\phi_{n}\,n^{1/2}-n^{1/2-\varepsilon}=n^{1/2-\varepsilon/s}\,.$ Next, we
choose $p=2+\delta$, where $\mathsf{E}(|X|^{2+\delta})<\infty$. Furthermore,
we substitute $n^{1-\varepsilon}=k=k_{n}\,$, whence

$\displaystyle n^{1/2-\varepsilon/s}$
$\displaystyle=k^{1/2+\alpha}\quad\text{and}\quad
n^{1/2-\varepsilon}=k^{1/2-\beta}\,,\quad\text{where}$ $\displaystyle\alpha$
$\displaystyle=\frac{\varepsilon}{1-\varepsilon}\Bigl{(}\frac{1}{2}-\frac{1}{s}\Bigr{)}\quad\text{and}\quad\beta=\frac{\varepsilon}{2(1-\varepsilon)}.$

Thus, using $k$ in the place of $n$ in Lemma 2.8,

$\displaystyle\mathsf{E}\bigl{(}n^{1/2-\varepsilon}$
$\displaystyle+\overline{\\!M}_{1}(n^{1-\varepsilon})\,;\,n^{1/2-\varepsilon}+\overline{\\!M}_{1}(n^{1-\varepsilon})>\phi_{n}\,n^{1/2}\bigr{)}$
$\displaystyle=\mathsf{E}\bigl{(}k^{1/2-\beta}+\overline{\\!M}_{1}(k)\,;\,\overline{\\!M}_{1}(k)>k^{1/2+\alpha}\bigr{)}\leq
c_{p}\,\mathsf{E}\bigl{(}|X|^{p}\bigr{)}\,\frac{2p-1}{p-1}\,k^{1/2-(p-1)\alpha}\,.$

We need that $1/2-(p-1)\alpha<0$, where $p=2+\delta$. This can be achieved by
choosing $s$ sufficiently large (*). Then $\textbf{D}^{\prime}\to 0$ uniformly
for $x_{1}\leq n^{1/2-\varepsilon}=n^{1/s}$, independently of $x_{2}\,$.

We come to the estimation of the principal term C. With
$\gamma_{x_{2}}(n)=\min\\{\nu_{x_{2}}(n),n^{1-\varepsilon}\\}$,

C
$\displaystyle=\mathsf{E}\Bigl{(}h\Bigl{(}x+S\bigl{(}\gamma_{x_{2}}(n)\bigr{)}\Bigr{)}\,;\,\tau_{x}>\gamma_{x_{2}}(n)\,,\;\nu_{x_{2}}(n)\leq
n^{1-\varepsilon}\Bigr{)}=h(x)-\textbf{F}\,,\quad\text{where}$ F
$\displaystyle=\mathsf{E}\Bigl{(}h\bigl{(}x+S(n^{1-\varepsilon})\bigr{)}\,;\,\tau_{x}>n^{1-\varepsilon}\,,\;\nu_{x_{2}}(n)>n^{1-\varepsilon}\Bigr{)}.$

At last, once more since $h(x)\leq C\,x_{1}$ by propositions 3.2 and 2.5,

F $\displaystyle\leq
C\,\mathsf{E}\bigl{(}x_{1}+S_{1}(n^{1-\varepsilon})\,;\,\tau_{x}>n^{1-\varepsilon}\,,\;\nu_{x_{2}}(n)>n^{1-\varepsilon}\Bigr{)}$
$\displaystyle\leq
C\,\Bigl{(}\mathsf{E}\bigl{(}x_{1}+S_{1}(n^{1-\varepsilon})\bigr{)}^{2}\Bigr{)}^{1/2}\,\Bigl{(}\mathbb{P}[\tau_{x}>n^{1-\varepsilon}\,,\;\nu_{x_{2}}(n)>n^{1-\varepsilon}]\Bigr{)}^{1/2}$
$\displaystyle\leq
C\,\bigl{(}2\,x_{1}^{2}+2\,n^{1-\varepsilon}\sigma_{1}^{2}\bigr{)}^{1/2}\,\Bigl{(}\mathbb{P}[\nu_{x_{2}}(n)>n^{1-\varepsilon}]\Bigr{)}^{1/2},$

which tends to $0$ as $n\to\infty$ by Lemma 3.7 and our assumption that
$x_{1}\leq n^{1/2-\varepsilon}=n^{1/s}$. Recall from (*) above that $s$
depends on the $\delta$ of the moment condition for $X_{1}\,$. ∎

##  4\. The 2-dimensional Lindley process

We first explain how the queueing process is related with the exit times.

###### Proof of Lemma 1.5.

In a good number of references, the increments in the definition of $W(n)$
come with a “plus” sign. We have chosen the “minus” because this is more
convenient when relating the process with the exit times. In Feller’s second
volume [12, VI.9], the “plus” is used, and the one-dimensional case is
considered. See in particular [12, Theorem on p. 198]. That theorem applies
without changes also to higher dimensions, and rewritten in terms of the
“minus” sign, it says the following for
$x=(x_{1}\,,x_{2})\in\mathbb{R}_{+}^{2}\,$.

$\displaystyle\mathbb{P}\bigl{[}W^{0}(n)\in[0\,,\,x_{1})\times[0\,,\,x_{2})\bigr{]}=\mathbb{P}\bigl{[}-\underline{M\\!}\,_{1}(n)<x_{1}\,,\;-\underline{M\\!}\,_{2}(n)<x_{2}\bigr{]}$
$\displaystyle=\mathbb{P}\bigl{[}x+S(k)\in(0\,,\,\infty)^{2}\;\text{ for all
}\;k\leq n\bigr{]}$ $\displaystyle=\mathbb{P}[\tau_{x}>n].$

This concludes the proof. ∎

We now consider recurrence versus transience of the 2-dimensional Lindley
process.

Negative drift in at least one coordinate

###### Proof of Theorem 1.3(a).

Suppose that $\mathsf{E}(X_{1}^{+})<\mathsf{E}(X_{1}^{-})\leq\infty\,$. Then
$S_{1}(n)\to-\infty$ almost surely. The times when the first marginal process
$W_{1}^{0}(n)$ starting at $0$ visits $0$ are the non-strictly increasing
ladder epochs of $S_{1}(n)$, see [24] and [12, VI.9] (and keep in mind the
“plus/minus” sign issue mentioned above). It is well known that the latter
terminates almost surely, so that $W_{1}^{0}(n)\to\infty$ and thus also
$W_{1}^{x_{1}}(n)\to\infty$ almost surely for every $x_{1}\geq 0\,$: the first
marginal process is transient, whence also the 2-dimensional process is
transient. ∎

Zero drift and negative correlation

We now consider the case when both marginals have zero drift, but the
correlation is negative.

###### Proof of Theorem 1.3(c), transient case.

Under the moment conditions of Theorem 1.3(c), when $\rho(X_{1}\,,X_{2})<0$
then the combination of Lemma 1.5 with Theorem 1.6(c) shows that

$\sum_{n=0}^{\infty}\mathbb{P}[W^{0}(n)\in[0\,,\,x_{1})\times[0\,,\,x_{2})]<\infty\quad\text{for
all }\;x_{1}\,,\,x_{2}>0.$

This is the expected number of visits of the process to each of those
rectangles. Therefore, with probability 1, each rectangle is visited only
finitely often, so that $|W^{0}(n)|\to\infty\,$ and the process is transient.
∎

Recurrence

We now turn our attention the the remaining cases, that is, statements (b) and
(d) of Theorem 1.3, as well as (c) with $\rho(X_{1}\,,X_{2})\geq 0$.

###### Conclusion of the proof of Theorem 1.3.

In all of those remaining cases, we have by Theorem 1.6

$\sum_{n=0}^{\infty}\mathbb{P}\bigl{[}W^{0}(n)\in[0\,,\,x_{1})\times[0\,,\,x_{2})\bigr{]}=\infty\quad\text{for
all }\;x_{1}\,,\,x_{2}>0.$

In the case when the distribution of $X=(X_{1}\,,X_{2})$ is non-lattice, this
alone does not guarantee that the process is topologically recurrent. But
thanks to Assumption 1.2(ii), there is
$x=(x_{1}\,,x_{2})\in(0\,,\,\infty)^{2}$ such that for each $n$,

$\mathbb{P}\bigl{[}X(n+1)\in[x_{1}\,,\,\infty)\times[x_{2}\,,\infty)\bigr{]}=\mathbb{P}\bigl{[}X\in[x_{1}\,,\,\infty)\times[x_{2}\,,\infty)\bigr{]}>0\,.$

But if $W^{0}(n)\in[0\,,\,x_{1})\times[0\,,\,x_{2})$ and
$X(n+1)\in[x_{1}\,,\,\infty)\times[x_{2}\,,\infty)$ then $W^{0}(n+1)=0$.
Therefore, for this choice of $(x_{1}\,,x_{2})$, and since $W^{0}(n)$ and
$X(n+1)$ are independent,

$\displaystyle\sum_{n=0}^{\infty}\mathbb{P}[W^{0}(n+1)=0]$
$\displaystyle\geq\sum_{n=0}^{\infty}\mathbb{P}\bigl{[}W^{0}(n)\in[0\,,\,x_{1})\\!\times\\![0\,,\,x_{2})\,,\;X(n+1)\in[x_{1}\,,\,\infty)\\!\times\\![x_{2}\,,\infty)\bigr{]}$
$\displaystyle=\mathbb{P}\bigl{[}X\in[x_{1}\,,\,\infty)\\!\times\\![x_{2}\,,\infty)\bigr{]}\sum_{n=0}^{\infty}\mathbb{P}\bigl{[}W^{0}(n)\in[0\,,\,x_{1})\\!\times\\![0\,,\,x_{2})\bigr{]}=\infty.$

Since $0$ is a single state of our Markov process, this implies via basic
Markov chain theory that it is a recurrent state:

$\mathbb{P}[W^{0}(n)=0\;\text{ infinitely often}\,]=1\,.$

Now let us look at this under the viewpoint of stochastic dynamical systems
(SDS): the random mappings $F_{k}(x)=\max\\{0,x-X(k)\\}$ are elements of the
semigroup $\mathfrak{L}$ of contractions of $\mathbb{R}_{+}^{2}$ with
Liptschitz constants $\leq 1$. We have

$W^{x}(n)=F_{n}\circ\dots\circ F_{1}(x)\,.$

In particular, $|W^{x}(n)-W^{y}(n)|$ is decreasing in $n$, whence
$|W^{x}(n)-W^{0}(n)|\leq|x|$. Consequently, our SDS is non-transient:

$\mathbb{P}\bigl{[}|W^{x}(n)|\to\infty\bigr{]}=0\quad\text{for every
}\;x\in\mathbb{R}_{+}^{2}\,.$

$\mathfrak{L}$ carries the topology of uniform convergence on compact sets.
Denote by $\widetilde{\mu}$ the (common) distribution of the i.i.d. random
mappings $F_{n}\,$. Then the above arguments which led to recurrence of the
state $0$ entail that the constant mapping $x\mapsto 0$ can be approximated in
$\mathfrak{L}$ by a sequence $f_{n}\circ\dots\circ f_{1}\,$,
$n\in\mathbb{N}\,$, where each function $f_{k}$ is in the support of
$\widetilde{\mu}$. At this point, we can invoke a result going back to [23],
developped further in [3] and [26]; see Kloas and Woess [22, Prop. 2.5] for a
compact formulation. It implies the existence of a limit set $\mathsf{L}$ and
recurrence as stated in the Introduction in (1.1) and the preceding paragraph.
∎

Discussion

_Invariant measures._ In the cases where the two-dimensional Lindley process
is recurrent, it follows from [26] that it has a unique invariant measure
$\nu$ up to constant factors. It is supported on the limit set $\mathsf{L}$,
and as a starting measure for the process, it makes the time shift ergodic.
For details, see [26, Thm. 2.13]. In particular, its marginals $\nu_{1}$ and
$\nu_{2}$ are the unique invariant measures for the respective marginal
processes. It is well understood that the invariant measure for a recurrent
one-dimensional Lindley process has finite total mass when the increment has
positive expectation. (Recall that we _substract_ the increment.) Also, that
measure has infinite total mass in the drift-free case. This is the reason why
for the two-dimensional process, $\nu$ has finite total mass (positive
recurrence) in Theorem 1.3(b), while it has infinite total mass (null
recurrence) in Theorem 1.3(c) and (d).

_The roles of Assumption 1.2(ii) and of the condition $\rho(X_{1}\,,X_{2})\geq
0$._ Consider the typical example of a clerk at a counter serving a queue of
customers. In that case, the waiting time of the $n^{\text{th}}$ customer is
modelled by a one-dimensional Lindley process, and recurrence means that the
process returns to state $0$ with probability one - the queue will be empty
and the clerk at the counter will be able to have a break. In the two-
dimensional case, we have two counters and two queues, and in general we
assume that the clerks do not operate independently. Then both Assumption
1.2(ii) and the non-negative correlation can be interpreted in the sense that
the two clerks are co-operative, which will give them the possibility to have
a joint break.

Assumption 1.2(ii) was used in the proof of Proposition 3.2 in order to show
that $h>0$ strictly on all of $(0\,,\,\infty)^{2}$. Without it, our proof does
not allow us to go beyond the statement that for every $b_{1}>0$ (possibly
small) there is $b_{2}>0$ (possibly large) such that $h>0$ on
$(b_{1}\,,\,\infty)\times(b_{2}\,,\,\infty)$.

In the proof of Theorem 1.3(d) this would lead to the restriction that we only
get

$\sum_{n=0}^{\infty}\mathbb{P}\bigl{[}W^{0}(n)\in[0\,,\,x_{1})\times[0\,,\,x_{2})\bigr{]}=\infty$

for sufficiently large $x_{1}$ and $x_{2}$.

Now, in the case when the process is discrete (in which case we assume without
loss of generality that the increments are in $\mathbb{Z}^{2}$ and the process
evolves within $\mathbb{N}_{0}^{2}$), this does imply recurrence in the sense
that the process visits each point of the (integer) limit set infinitely often
with probability one. However, the origin is then not necessarily part of the
limit set: the two clerks will not be able to have a joint break.

On the other hand, when the process is non-discrete then it is by no means
clear that divergence of the above series implies topological recurrence –
here, recurrence was deduced because on the basis of Assumption 1.2(ii) we
could show that $\sum_{n}\mathbb{P}\bigl{[}W^{0}(n)=0]=\infty$.

_The limit set._ $\mathsf{L}$ depends on the support of the distribution of
the increments. In our case, most importantly, it contains the origin. It
appears quite hard to determine the full limit set explicitly, compare with
[22].

_Moment assumptions._ In theorems 1.3(d) and 1.6(d), we have assumed among
other that $\mathsf{E}((X_{2}^{-})^{3+\delta})<\infty\,$. This is used in the
proof of Claim 1 in Proposition 3.2. We believe that a finite moment of order
$2+\delta$ should suffice, but so far we have not succeeded in proving this.

_Higher dimensions._ We can consider the same issues on $\mathbb{R}_{+}^{d}$
for any $d\geq 2$. The model random variable for the increments is then
$X=(X_{1}\,,\dots,X_{d})$, and the definition of $W(n)$ remains the same, as
well as Assumption 1.2 with the obvious adaptation.

If there is one coordinate with
$\mathsf{E}(X_{i}^{+})<\mathsf{E}(X_{i}^{-})\leq\infty\,$ then $W(n)$ is
transient, while if all coordinates satisfy
$\mathsf{E}(X_{i}^{-})<\mathsf{E}(X_{i}^{+})<\infty\,$, then $W(n)$ is
positive recurrent.

Also, if one coordinate is centered and all others have positive expectiation,
then under the same moment conditions as in Theorem 1.3(d) one gets null
recurrence; the proof remains practically the same.

For recurrence, one cannot have more than two centered coordinates. So the
main case still to be studied is the analogue of Theorem 1.3(d) in the case
when there are two centered coordinates and all the other coordinates have
positive expectation. There are several substantial additional issues to be
tackled in this situation, which we reserve for future work.

Remarks on reflected random walk

A model which is very similar to the queueing process is reflected random
walk. In dimension 1, with starting point $x>0$, both processes evolve like a
random walk $x-S(n)$ as long as it stays non-negative. When the walk enters
the negative half-axis, the value is reset to zero for the queueing process
$W^{x}(n)$, while for reflected random walk $R(n)=R^{x}(n)$, the sign is
changed. In arbitrary dimension, this means that reflected random walk is
given by

$R(0)=x\in\mathbb{R}^{+}\,,\quad R(n)=|R(n-1)-X(n)|\,,$

where (attention!) the absolute value is taken coordinate-wise. The one-
dimensional model is very well studied; instead of re-displaying all
references, we refer to [26], as well as to [25] and [22], where the
recurrence of the multidimensional reflected random walk is studied in the
case where $\mathsf{E}(X_{i})>0$ for all coordinates.

In general, it is easy to see that transience of the multi-dimensional
queueing process implies transience of the corresponding reflected random
walk. In other words, the recurrence issue is somewhat harder for reflected
random walk. In the following case, the two processes are recurrent, resp.
transient simultaneously.

###### (4.1) Lemma.

If there is $\Delta>0$ such that $X_{i}\geq-\Delta$ almost surely for
$i=1,\dots,d$ then for the two processes starting at the same point,

$R_{i}(n)\leq X_{i}(n)+\Delta\quad\text{almost surely for $i=1,\dots,d$ and
all $n$.}$

The proof is straightforward. Thus, when the multidimensional Lindley process
visits the origin infinitely often with probability $1$, then the
corresponding multidimensional reflected random walk visits the set
$[0\,,\,\Delta]^{d}$ infinitely often with probability $1$. By the
contractivity properties of $\bigl{(}R^{x}(n)\bigr{)}$, this implies that the
reflected random walk is topologically recurrent on its limit set, compare
with [26] and [22].

In dimension 2, this applies, in particular, to the situation of Theorem 1.3.

##  5\. Appendix: a proof due to D. Denisov and V. Wachtel

In this subsection, the proof of Proposition 2.5 is completed. That is, we
present the elaboration of an argument of Denisov and Wachtel which proves

(2.6) $\lim_{x\to\infty}\frac{h_{1}(x)}{x}=1.$

Given the centered real random variable $X$ with $\mathsf{E}(X^{2})<\infty\,$,
we consider the following functions $a,b,m:\mathbb{R}_{+}\to\mathbb{R}_{+}$
associated with the negative part $X^{-}$ of $X$.

$\displaystyle a(x)$ $\displaystyle=-\mathsf{E}(x+X\,;\,x+X\leq
0)=\int_{x}^{\infty}\mathbb{P}[X\leq-y]\,dy\,,$ $\displaystyle b(x)$
$\displaystyle=\int_{x}^{\infty}a(y)\,dy\,,\quad\text{and}\quad
m(x)=\int_{0}^{x}b(y)\,dy\,,\quad x\geq 0.$

Similarly, we set
$\displaystyle\bar{a}(x)=\int_{x}^{\infty}\mathbb{P}[X>y]\,dy.$ One easily
verifies that $\;\displaystyle
2b(x)=\mathsf{E}\bigl{(}(\max\\{X^{-}-x,0\\})^{2}\bigr{)}=\int_{-\infty}^{x}(x+y)^{2}dF(y)\to
0$ as $x\to\infty\,$, whence also

(5.1) $\lim_{x\to\infty}\frac{m(x)}{x}=0.$

###### (5.2) Proposition.

There are positive constants $R$ (sufficiently large) and $A$ such that the
function

$V(x)=x+A\,m(x)+R\,,\quad x\geq 0\,,$

is superharmonic for the one-dimensional random walk $S(n)$ killed when
exiting $\mathbb{R}_{+}\,$, that is,

$\mathsf{E}\Bigl{(}V\bigl{(}x+S(1)\bigr{)}\,;\,\tau_{x}>1\Bigr{)}\leq
V(x)\quad\text{for all }\;x\geq 0.$

Let us first show how this implies the desired result.

###### Proof of (2.6).

Proposition 5.2 implies that for all $x\geq 0$ and $n\in\mathbb{N}$

$\displaystyle V(x)$
$\displaystyle\geq\mathsf{E}\Bigl{(}V\bigl{(}x+S(n)\bigr{)}\,;\,\tau_{x}>n\Bigr{)}$
$\displaystyle\geq\mathsf{E}\bigl{(}x+S(n)\,;\,\tau_{x}>n\bigr{)}$
$\displaystyle=\mathsf{E}\bigl{(}x+S(\min\\{n,\tau_{x}\\})\,;\,\tau_{x}>n\bigr{)}$
$\displaystyle=x-\mathsf{E}\bigl{(}x+S(\tau_{x})\,;\,\tau_{x}\leq n\bigr{)}.$

The last identity holds by the martingale property, since $S(n)$ is a centered
random walk. We infer that

$-\mathsf{E}\bigl{(}x+S(\tau_{x})\,;\,\tau_{x}\leq n\bigr{)}\leq
V(x)-x=A\,m(x)+R$

We can let $n\to\infty\,$, and by monotone convergence

$0\leq-\mathsf{E}\bigl{(}x+S(\tau_{x})\,;\,\tau_{x}<\infty\bigr{)}\leq
A\,m(x)+R$

By (5.1),

$\lim_{x\to\infty}\frac{1}{x}\,\mathsf{E}\bigl{(}x+S(\tau_{x})\,;\,\tau_{x}<\infty\bigr{)}=0\,.$

Since
$h_{1}(x)=x-\mathsf{E}\bigl{(}x+S(\tau_{x})\,;\,\tau_{x}<\infty\bigr{)}$, the
result follows. ∎

###### Proof of Proposition 5.2.

We want to show that

$\Delta(x)=\mathsf{E}\Bigl{(}V\bigl{(}x+S(1)\bigr{)}\,;\,\tau_{x}>1\Bigr{)}-V(x)\leq
0\quad\text{for }\;x\geq 0.$

We write $F(x)=\mathbb{P}[X\leq x]$ and $\overline{F}(x)=1-F(x)$. Using that
$x=\mathsf{E}(x+X)$,

$\displaystyle\Delta(x)$
$\displaystyle=\mathsf{E}\bigl{(}x+X+A\,m(x+X)+R\,;\,X>-x\bigr{)}-x-A\,m(x)-R$
$\displaystyle=-\mathsf{E}(x+X\,;\,X\leq-x\bigr{)}-R\,F(-x)-A\,m(x)\,F(-x)$
$\displaystyle\hskip
126.61467pt+A\,\,\mathsf{E}\bigl{(}m(x+X)-m(x)\,;\,X>-x\bigr{)}$
$\displaystyle=a(x)-R\,F(-x)-A\,m(x)\,F(-x)+A\int_{-x}^{\infty}\bigl{(}m(x+y)-m(x)\bigr{)}\,dF(y).$

We decompose the last integral and integrate twice by parts, recalling that
$m^{\prime}(x)=b(x),b^{\prime}(x)=-a(x)$, $a^{\prime}(x)=-F(-x)$ and
$\bar{a}^{\prime}(x)=-\overline{F}(x)\,$ :

$\displaystyle\int_{-x}^{\infty}$
$\displaystyle\bigl{(}m(x+y)-m(x)\bigr{)}\,dF(y)$
$\displaystyle=\int_{-x}^{0}\bigl{(}m(x+y)-m(x)\bigr{)}\,dF(y)-\int_{0}^{\infty}\bigl{(}m(x+y)-m(x)\bigr{)}\,d\overline{F}(y)$
$\displaystyle=m(x)\,F(-x)-\int_{-x}^{0}b(x+y)F(y)\,dy+\int_{0}^{\infty}b(x+y)\overline{F}(y)\,dy$
$\displaystyle=m(x)\,F(-x)+\int_{0}^{x}b(x-y)a^{\prime}(y)\,dy-\int_{0}^{\infty}b(x+y)\overline{a}^{\prime}(y)\,dy$
$\displaystyle=m(x)\,F(-x)+b(0)a(x)-b(x)a(0)-\int_{0}^{x}a(x-y)a(y)\,dy$
$\displaystyle\hskip
136.5733pt+b(x)\bar{a}(0)-\int_{0}^{\infty}a(x+y)\bar{a}(y)\,dy\,.$

We observe that
$b(x)\bar{a}(0)-b(x)a(0)=b(x)\bigl{(}\mathsf{E}(X^{+})-\mathsf{E}(X^{-})\bigr{)}=0$,
and recall that $b(0)=\mathsf{E}\bigl{(}(X^{-})^{2}\bigr{)}\big{/}2$.
Combining these computations,

$\displaystyle\Delta(x)$
$\displaystyle=a(x)-R\,F(-x)+A\,\frac{\mathsf{E}\bigl{(}(X^{-})^{2}\bigr{)}}{2}\,a(x)-A\\!\int_{0}^{x}\\!\\!\\!\\!a(x-y)a(y)\,dy-A\\!\int_{0}^{\infty}\\!\\!\\!\\!a(x+y)\bar{a}(y)\,dy$
$\displaystyle\leq
a(x)-R\,F(-x)+A\,\frac{\mathsf{E}\bigl{(}(X^{-})^{2}\bigr{)}}{2}\,a(x)-A\\!\int_{0}^{x}\\!\\!\\!\\!a(x-y)a(y)\,dy\,.$

Using that $a(x)$ is monotone decreasing,

$\displaystyle\int_{0}^{x}\\!\\!a(x-y)a(y)\,dy$
$\displaystyle=2\int_{0}^{x/2}\\!\\!a(x-y)a(y)\,dy$ $\displaystyle\geq
2a(x)\bigl{(}b(0)-b(x/2)\bigr{)}=a(x)\mathsf{E}\bigl{(}(X^{-})^{2}\bigr{)}-2a(x)b(x/2).$

We now choose $A=4\big{/}\mathsf{E}\bigl{(}(X^{-})^{2}\bigr{)}$. Then we get

$\Delta(x)\leq-R\,F(-x)+a(x)\bigl{(}2A\,b(x/2)-1\bigr{)}\leq-R\,F(-x)+3a(x).$

Since $b(x)\to 0$ as $x\to\infty$, there is $x_{0}>0$ such that
$2A\,b(x_{0}/2)-1=0$ and hence $\Delta(x)\leq 0$ for all $x\geq x_{0}\,.$

Now suppose first that $F(-x_{0})>0$. Then we choose
$R=3\mathsf{E}(X^{-})/F(-x_{0})$, and for $x\leq x_{0}$, we have
$\Delta(x)\leq-R\,F(-x_{0})+3a(0)=0$.

Finally suppose that $F(-x_{0})=0$, that is, $\mathbb{P}[X>-x_{0}]=1$. Then
also $a(x_{0})=0$. This time, we choose $R=3x_{0}\,$. For $0\leq x<x_{0}$,
there is $\xi\in(x\,,\,x_{0})$ such that
$a(x)=a(x_{0})-(x_{0}-x)a^{\prime}(\xi)=(x_{0}-x)F(-\xi)$. Then

$\Delta(x)\leq
3a(x)-R\,F(-x)=3(x_{0}-x)\bigl{(}F(-\xi)-F(-x)\bigr{)}-3xF(-x)\leq 0.$

This concludes the proof. ∎

## References

  * [1] Asmussen, S.: _Applied Probability and Queues,_ 2nd edition. Applications of Mathematics 51, Springer-Verlag, New York, 2003.
  * [2] Babillot, M., Bougerol, Ph., and Elie, L.: _The random difference equation $X_{n}=A_{n}X_{n-1}+B_{n}$ in the critical case._ Ann. Probab. 25 (1997) 478–493.
  * [3] Benda, M.: _Schwach kontraktive dynamische Systeme._ Ph. D. Thesis, Ludwig-Maximilans-Universität München (1998).
  * [4] Benda, M.: _Contractive stochastic dynamical systems._ Unpublished preprint, Ludwig-Maximilans-Universität München (1999).
  * [5] Benda, M.: _A reflected random walk on the half line._ Unpublished preprint, Ludwig-Maximilans-Universität München (1999).
  * [6] Borovkov, A.A.: _Stochastic Processes in Queueing Theory._ Springer-Verlag, New York-Berlin, 1976.
  * [7] Burkholder, D. L.: _Distribution function inequalities for martingales._ Ann. Probab. 1 (1973) 19–42.
  * [8] Cygan, W., and Kloas, J.: _On recurrence of the multidimensional Lindley process._ Electron. Commun. Probab. 23 (2018), no. 4, 1–14.
  * [9] Denisov, D., and Wachtel, V.: _Random walks in cones._ Ann. Probab. 43 (2015) 992–1044.
  * [10] Doney, R.A: _Local behaviour of first passage probabilities._ Probab. Theory Related Fields 152 (2012) 559–588.
  * [11] Duraj, J.: _Random walks in cones: the case of nonzero drift._ Stochastic Process. Appl. 124 (2014) 1503–1518.
  * [12] Feller, W.: _An Introduction to Probability Theory and its Applications._ Volume II, 2nd edition, Wiley, New York (1971).
  * [13] Flatto L., and McKean, H.P.: _Two queues in parallel._ Comm. Pure Appl. Math. 30 (1977) 255–263.
  * [14] Garbit, R., and Raschel, K.: _On the exit time from a cone for random walks with drift._ Rev. Mat. Iberoam. 32 (2016) 511–532.
  * [15] Greenwood, P., and Shaked, M.: _Fluctuations of Random Walk in $\mathbb{R}^{d}$ and Storage Systems._ Adv. Applied Probab. 9 (1977), 566–587.
  * [16] Gut, A.: _Stopped Random Walks. Limit theorems and applications._ 2nd edition, Springer, New York, 2009.
  * [17] Ignatiouk-Robert, I., and Loree, Ch.: _Martin boundary of a killed random walk on a quadrant._ Ann. Probab. 38 (2010) 1106–1142.
  * [18] Janson, S.: _Moments for first-passage and last-exit times, the minimum, and related quantities for random walks with positive drift._ Adv. Appl. Prob. 18 (1986) 865–879.
  * [19] Kendall, D. G.: _Some problems in the theory of queues._ J. Roy. Statist. Soc. Ser. B. 13 (1951) 151–173; discussion: 173–185.
  * [20] Kiefer, J., and Wolfowitz, J.: _On the theory of queues with many servers._ Trans. Amer. Math. Soc. 78 (1955) 1–18.
  * [21] Kingman, J. F. C.: _Two similar queues in parallel._ Ann. Math. Statist. 32 (1961),1314–1323.
  * [22] Kloas, J., and Woess, W.: _Multidimensional random walk with reflections_. Stochastic Proc. Appl. 129 (2019) 336–354.
  * [23] Leguesdron, P.: _Marche aléatoire sur le semi-groupe des contractions de $\mathbb{R}^{d}$. Cas de la marche aléatoire sur $\mathbb{R}_{+}$ avec choc élastique en zéro._ Ann. Inst. H. Poincaré Probab. Statist. 25 (1989) 483–502.
  * [24] Lindley, D. V.: _The theory of queues with a single server._ Proc. Cambridge Philos Soc. 48(1952), 277–289.
  * [25] Peigné, M.: _Marches de Markov sur le semi-groupe des contractions de $\mathbb{R}^{d}$. Cas de la marche aléatoire à pas markoviens sur $(\mathbb{R}_{+})^{d}$ avec chocs élastiques sur les axes._ Ann. Inst. H. Poincaré Probab. Stat. 28 (1992) 63–94.
  * [26] Peigné, M., and Woess, W.: _Stochastic dynamical systems with weak contractivity properties, I. Strong and local contractivity._ Colloq. Math. 125 (2011) 31–54.
  * [27] Peigné, M., and Woess, W.: _Stochastic dynamical systems with weak contractivity properties, II. Iteration of Lipschitz mappings._ Colloq. Math. 125 (2011) 55–81.
  * [28] Pham, T. D. C.: _Conditioned limit theorems for products of positive random matrices._ ALEA Lat. Am. J. Probab. Math. Stat. 15 (2018) 67–100.