1 Introduction

Tandem queueing systems (TQ) are classical models in queueing theory consolidated from many decades of research and generalized to stochastic networks with diverse structures. A tandem queue is a system of queues where there is an initial arrival process \(A^1\) and a sequence \(\{ S^n \}_{n \ge 1}\) of service processes, all independent. The system is defined recursively: the initial queue is fed from the arrival process \(A^1\) and has departures determined by the service process \(S^1\). For \(n \ge 2\), the arrival process for the n-th queue is defined as the departure process of the (n-1)-th queue, and the departures are determined by the service process \(S^n\). One fundamental result in queueing theory is Burke’s theorem, which states that, given a Poisson process as arrival and an independent Poisson process as service (where the service intensity is strictly larger than the arrival one), the departure process is a Poisson process. This type of result, where there is an invariant law of the process under the queueing operator, is known as an Output theorem in the literature, and it allows us to compute explicitly many features of tandem queues systems.

It is natural to consider the convergence of the departure process law from the n-th queue, as n goes to infinity, when the initial arrival process is arbitrary. This was answered in [20] in the case when the service processes are Poisson: there is convergence to a Poisson process, under weak conditions on the initial arrival process. In [23], the result was generalized to the case when the service processes are not Poisson but independent and identically distributed. In this work, we study the same question when the service processes are Brownian motions.

Let us start by introducing the Brownian Tandem Queues (TQ). We follow the notation introduced in [21]. For real and continuous functions \(f \in \mathcal C ({\mathbb R})\), set \(f(x,y):=f(y)-f(x)\). Let \(a=(a(x)\): \(x\in {\mathbb R})\) denote some continuous arrival process and for \(\mu >0\) define the service process by \(s^{(1)}(x):=\mu x-B^{(1)}(x)\), where \(B^{(1)}=( B^{(1)} (x)\): \(x \in {\mathbb R})\) is a two-sided Brownian motion independent of a. The queue-length process is defined as

$$\begin{aligned} q^{(1)}(x):=\sup _{z \le x} \left\{ a(z,x)-s^{(1)} (z,x) \right\} . \end{aligned}$$
(1)

In order for \(q^{(1)}\) to be stable (positive recurrent), we impose that the service process \(s^{(1)}\) has a drift larger than that of the arrival process. We do this by requiring

$$\begin{aligned} \lim _{x\rightarrow -\infty } \frac{a(x)}{x} = 0 \text{ and } \lim _{x\rightarrow \infty } \frac{a(x)}{x} = 0. \end{aligned}$$

The departure process is defined by

$$\begin{aligned} d^{(1)}(x,y):=a(x,y) - q^{(1)}(x,y) , \end{aligned}$$
(2)

with the convention that \(d^{(1)}(0)=0\), and hence we put \(d^{(1)}(x):= d^{(1)}(0,x)\).

The tandem queue model, in words, consists of a line of queues, where each queue uses as input (arrival) process the output (departure) process of the queue that is just in front of it in the line. In this context, we have an initial arrival process a and service processes \(\{ s^{(n)} \}_{n \in {\mathbb N}} \), where \(s^{(n)}(x)=\mu x-B^{(n)}(x)\) and \(\left\{ B^{(n)}\,:\,n\in {\mathbb N}\right\} \) is a collection of independent (two-sided) Brownian motions. One can define inductively the queue-length and departure processes of the n-th Brownian queue. Assume that the departure process \((d^{(n)} (x) : x \in \mathbb R)\) is already defined. Then, we can define the queue-length process of the (\(n+1\))-th Brownian queue as

$$\begin{aligned} q^{(n+1)}(x):=\sup _{z\le x}\left\{ d^{(n)}(z,x)-\mu (x-z)+B^{(n+1)}(z,x)\right\} , \end{aligned}$$

and the departure process from the n-th Brownian queue as

$$\begin{aligned} d^{(n+1)}(x,y):=d^{(n)}(x,y)- q^{(n+1)}(x,y), \end{aligned}$$

with the similar convention \(d^{(n+1)}(0)=0\) and \(d^{(n+1)}(x):= d^{(n+1)}(0,x)\).

A measure on the space of continuous arrival functions with zero drift is called invariant for the queueing operator (in equilibrium) if the departure process has the same law as the arrival process. For the Brownian queue operator, the measure induced by an independent standard Brownian motion B is an invariant (ergodic) measure [21]. Our result is the uniqueness of such a measure, by proving attractiveness:

Theorem 1

Start the process of queues in tandem with a zero mean ergodic arrival process. Then,

$$\begin{aligned} \lim _{n\rightarrow \infty }d^{(n)}{\mathop {=}\limits ^\mathrm{dist.}}B\,. \end{aligned}$$
(3)

In our proof of Theorem 1, we will only use that B is an invariant ergodic measure for the queue system. Uniqueness will follow from our method.

Essential for our proof is the connection of the Brownian TQ model to two related Brownian models, namely the Brownian last-passage percolation (LPP) and the totally asymmetric Brownian exclusion process (TABEP). We will introduce these models in Sect. 3 and point out the relationships between the three models.

All of these models have been previously studied, and the connection between them has been known for a while. Hambly et al. [11] defined the LPP Brownian model and derived concentration results for the associated Brownian growth model. The related Brownian particle system model has been studied in [5, 6]: particles are driven by Brownian motions, and each particle is reflected (only) on its left closest particle. While models of Brownian motions interacting by exclusion on the real line have been an active research topic [13, 14, 22], Ferrari, Spohn and Weiss successfully constructed a strong version of a two-sided system with an infinite amount of particles in a stationary regime [6], governed by an asymmetric Skorokhod-type reflection, easily related to the LPP model. They accomplished this by a technique resembling Loynes’ stability theorem for G / G / 1 queues [17], and studied the finite-dimensional distributions of the system, characterized in terms of the Airy process. For simplicity, we name this Brownian particle system as the totally asymmetric Brownian exclusion process (TABEP), as suggested by P. A. Ferrari. The queueing model related to this particle process is exactly our Brownian TQ.

1.1 Contribution

In this article, we first revisit the connection between these three models: the LPP Brownian model, the TABEP process and the TQ Brownian system. The relationship between the LPP model and the TABEP process is mentioned in [6], while the relation between the LPP model and the TQ system is described in [21]. This is completely analogous to the known relationship between standard Markovian Tandem Queues, LPP on \({\mathbb Z}^2\) with exponential weights and the TASEP (totally asymmetric exclusion process). For the sake of completeness, these models are presented in Sect. 2.

Relying on these relations, we prove a result concerning the uniqueness of the invariant measure for the Brownian queueing operator, by proving attractiveness to that measure. In words, if we start with some zero mean ergodic process as initial arrival process and let it pass through the Brownian queues in tandem, then the departure process from the n-th queue converges in distribution to a Brownian motion as n goes to infinity. This is precisely stated in Theorem 1.

For this purpose, we only use that the invariant measure under the queueing operator is known [12]: it is the random measure associated with the Brownian motion. The method of proof is a coupling technique developed in the LPP Brownian setting: starting with two different initial arrival processes (called mass profiles in the LPP Brownian model), we use the same service processes (the random environment in the LPP context) to define the coupled evolution. Then, we can prove that the difference between the associated departure processes (mass profiles) at each stage of the system is converging to zero on compact sets. This is our main result, Theorem 3, which implies the desired conclusion in the queueing context, Theorem 1. We point out that this result can also be translated to an attractiveness result for a semi-infinite TABEP system; see Theorem 2.

A key step in the method involves local comparison techniques which allow us to bound the difference between mass profiles in terms of the so-called exit points in the LPP literature. This implies that it is only necessary to control the exit points for a given system (done in Lemma 4) and then to control the difference between the exit points defined for each of the coupled systems. These exit points are naturally defined in the LPP context, but we give an interpretation in the queueing setting in the following: First, consider an arbitrary initial arrival process and a single node Brownian queue. The exit point associated with time x is the last time Z(x, 1) before time x when the Brownian queue was empty. Given node n of a tandem Brownian queue system and some time x, define \(I_{n-1}(x,n)\) as the last time the n-th queue was empty before time x, then \(I_{n-2}(x,n)\) to be the last time the (n-1)-th queue was empty before time \(I_{n-1}(x,n)\), and so on, until we find the exit point \(Z(x,n)=I_0(x,n)\). Hence, the exit time can be found from this iterative process of marking the beginning of the current excursion of the queue in each stage of the tandem system. This property is described in more detail in Sect. 4.1.

Our method of proof differs substantially from the methods developed for discrete-valued queueing systems: In [20], a coupling between the departure times in every step of the tandem queue of each user is accomplished, while in [23] the waiting times of each user in every node of the tandem queue system are considered for the coupling.

A rather simplified version of this result was presented in [15] where, using a path coupling of the departures processes, a non-stationary and one-sided (in time) system is studied with some particular initial conditions. Those techniques are non-applicable to the current bi-infinite stationary setting.

1.2 Structure of the paper

In Section 2, we first review the classical discrete models. Then, we define the totally asymmetric Brownian exclusion process (Sect. 3.1) and the last-passage percolation system (Sect. 3.2). In each of these subsections, our result is stated in the corresponding context (Theorems 2 and 3) and the explicit relations between the models are shown. In Sect. 3.2, the coupled dynamics are defined. In Sect. 3, we first present the definition of exit points and the results concerning their control (Sect. 4.1) and then proceed to show the comparison results and the proof of Theorem 3 (Sects. 4.2 and 4.3).

2 The discrete models

In this section, we review some fundamental relationships between the classical Markovian tandem queue model (TQ), the exponential last-passage percolation model (LPP) and the totally asymmetric simple exclusion process (TASEP).

Assume that we have K Markovian queues in tandem working under a FIFO discipline. At time zero, the first queue starts working with N users in the line, while all the other queues are empty. Define a collection of rate-one independent exponential random variables \(\{ X(n,k)\}_{ n=1,\ldots ,N, k=1,\ldots ,K}\), where X(n, k) represents the service time of the n-th user at server k. Define D(n, k) as the time where the n-th user exits the k-th server. Note that server k only starts to serve user n after user \(n-1\) has exited server k and the service from server \(k-1\) to user n has been finished. Then, we have the following recurrence structure:

$$\begin{aligned} D(n,k)= X(n,k) + \max ( D(n,k-1), D(n-1,k) ), \end{aligned}$$
(4)

with boundary conditions \(D(0,0)=0\) and \(D(n,k)=0\) if \(n<0\) or \(k<0\). We will show how this structure is related to the aforementioned models.

Consider a collection of i.i.d. random variables \(\{W_{\mathbf x}\,:\,{\mathbf x}\in ({\mathbb Z}_+)^2\}\) (also called weights), distributed according to an exponential distribution function of parameter one. In last-passage site percolation (LPP) models, each number \(W_{\mathbf x}\) is interpreted as the percolation (passage) time through vertex \({\mathbf x}=(x(1),x(2))\). For a lattice vertex \({\mathbf x}= (n,k)\) in \(({\mathbb Z}_+)^2\), denote by \(\Gamma ({\mathbf x})\) the set of all up-right oriented paths \(\gamma =({\mathbf x}_0,{\mathbf x}_1,\dots ,{\mathbf x}_k)\) from \({\mathbf 0}\) to \({\mathbf x}\), i.e., \({\mathbf x}_0={\mathbf 0}\), \({\mathbf x}_k={\mathbf x}\) and \({\mathbf x}_{j+1}-{\mathbf x}_j\in \{{\mathbf e}_1,{\mathbf e}_2\}\), for \(j=0,\dots ,k-1\), where \({\mathbf e}_1=(1,0)\) and \({\mathbf e}_2=(0,1)\). The weight (or passage time) along \(\gamma \) is defined as

$$\begin{aligned} W(\gamma ):=\sum _{j=0}^{k} W_{{\mathbf x}_i}. \end{aligned}$$

The last-passage time between \({\mathbf 0}\) and \({\mathbf x}\) is defined as

$$\begin{aligned} L({\mathbf x}) \equiv L(n,k):=\max _{\gamma \in \Gamma ({\mathbf x})} W(\gamma ). \end{aligned}$$

By the up-right path structure and the dynamic programming principle, we have the following Bellman equation:

$$\begin{aligned} L(n,k)= W(n,k) + \max ( L(n,k-1), L(n-1,k) ). \end{aligned}$$
(5)

This equation is the same as (4) with the same boundary conditions, so the last-passage percolation function is an equivalent way to describe the departure times from a tandem queue system.

Let us define the related interacting particle system. Let \(\Omega \) be the space of binary sequences \(\eta : {\mathbb Z}\rightarrow \{0, 1\}\). The elements \(\eta \) in \(\Omega \) will be configurations of particles. We will say that a configuration \(\eta \) such that \(\eta (x)=1\) has a particle at position x. If \(\eta (x)=0\), we say that position x is empty or that we have a hole in that position. The dynamics are defined by the infinitesimal generator

$$\begin{aligned} \mathcal L [f] (\eta )= \sum _{ x \in \mathbb Z} \eta (x) (1 - \eta (x-1)) ( f ( \eta ^{x,x-1}) - f(\eta )), \end{aligned}$$

where \(\eta ^{x,x-1}\) is defined as the configuration that is identical to \(\eta \) except for the positions x and \(x-1\), where the original values are exchanged. The interpretation is the following: from each possible site x, we have a constant rate of jump of the particles. (If there is no particle at site x, nothing happens.) Once the clock at position x rings, the particle in that place tries to jump to the site \(x-1\) and this is accomplished if the site \(x-1\) is empty; otherwise, the jump is disregarded. This last condition emulates an exclusion principle, which is the reason that this process is known as the totally asymmetric simple exclusion process. It is a standard microscopic model for transport; see, for example, [4].

Finally, we show the relationship between the TASEP process and the tandem queue model defined by (4). Let \(\{ \eta _t : t \ge 0 \}\) be a TASEP process with initial configuration \(\eta _0\). Assume the initial configuration \(\eta _0\) is such that \(\eta _0(x)= 1_{ [0, \infty ) } (x)\) for every \(x \in \mathbb Z\), which means that all the particles are to the right of the origin in consecutive positions. Label each particle with its initial position, and define \(x_{l}(t)\) to be the position of the l-th particle at time t (so \(x_l(0) = l\) for every \(l \in \mathbb N\)). Define

$$\begin{aligned} q_l (t) := x_l(t)- x_{l+1}(t)-1, \end{aligned}$$
(6)

that is, the number of users in server l at time t is equal to the number of holes between particles l and \(l+1\) at time t. Note that (6) translates exactly the movement of particles in the exclusion process to the tandem queue dynamics: every time that the particle l moves to the left, one user is entering the l-th queue. Moreover, if the particle l which is moving is not the first one, the number of users in the (l-1)-th queue diminishes by one, so the user is leaving that queue. The exclusion property for particles translates into the restriction of having a nonnegative number of users in each queue. Consider now that holes are labeled in the starting configuration \(\eta _0\): the hole at position \(l <0\) will have label \(-l\). The model is symmetric in particles and holes: one can think of holes traveling to the right which satisfy the exclusion property between them. Therefore, using (6), we have another interpretation of the departure time D(n, k): it is exactly the time when particle k exchanges position with hole n.

The previous presented relationships are known and studied; see [19]. In the last two decades, great progress has been made for LPP models and this has given insight into an important question originally posed in queueing theory: the asymptotic distribution of the departure time of the n-th user in line from the m-th queue (its order in the line of queues), when the whole system starts empty, by making m and n grow to infinity while keeping fixed the ratio between them [9, 24]. On the other hand, strong results from queueing theory concerning the existence and attractiveness of invariant measures under the queueing operator [18, 23] have been used to shed light on difficult questions concerning LPP models, as for example the existence of semi-infinite geodesics and Busemann functions for the lattice model in \(\mathbb {Z}^2\) with generally distributed weights; see [7, 8].

3 Convergence of the Brownian models

Theorem 1 states our convergence result for the Brownian TQ. In this section and the next, we will restate basically the same result in the context of two different Brownian models.

3.1 Convergence in the totally asymmetric Brownian exclusion process

Consider a semi-infinite system of Brownian interacting particles defined for all real times x. Take some stationary, ergodic and continuous process \(\{X^{(0)}(x): x \in \mathbb {R} \}\) and define \(X^{(0)}(x)\) as the position of the leftmost particle at time x. We introduce a collection \(\{B^{(n)}:n\ge 1\}\) of independent two-sided standard Brownian motions. Then, for \(n \ge 1\), define

$$\begin{aligned} X^{(n)}(x) = \sup _{ y \le x} (X^{(n-1)}(y) + B^{(n)}(x) - B^{(n)}(y)), \qquad x \in \mathbb R \, . \end{aligned}$$
(7)

The system \(\{X^{(n)}(x): x \in \mathbb {R} \}_{ n \ge 0}\) will be called the totally asymmetric Brownian exclusion process (TABEP) with leftmost particle \(X^{(0)}\). By definition, the order of the particles is preserved: \(X^{(0)}(x) \le X^{(1)}(x) \le \cdots \) for every real time x (choosing \(y=x\) in the argument of the supremum in (7) shows that \(X^{(n-1)}(x) \le X^{(n)}(x)\)). Note that (7) implies that the TABEP is Markovian in n: conditionally on the information of the process \(X^{(n)}\), the process \(X^{(n+1)}\) is independent of the collection \(\{X^{(k)} \}_{ k=1,\ldots ,n-1}\). These two properties can be combined to give an informal interpretation: the n-th particle is obtained by reflecting an independent Brownian motion to its left-side neighbor (the (n-1)-th particle), and this is the only possible interaction between particles. (Note that a particle does not notice the particles to the right of it.)

A sufficient condition to have a well-defined system is that for some positive constant \(\mu \), \(X^{(0)}\) satisfies

$$\begin{aligned} \liminf _{x\rightarrow -\infty }\frac{ X^{(0)} (x)}{x}\ge \mu \quad \text{ and }\quad \limsup _{x\rightarrow \infty }\frac{ X^{(0)} (x)}{x}\le \mu . \end{aligned}$$
(8)

Note that the whole system is time stationary: one can prove inductively that the distribution of \(X^{(n)}(x)\) does not depend on x, for every \(n\ge 0\).

Let us remark that the system defined above is a two-sided time stationary extension of a TABEP system with initial positions, defined by Ferrari et al. [6]. In that work, they considered the particular case of initial positions where the starting positions of the particles are given by a rate \(\mu \) Poisson process on \([0,\infty )\) and the leftmost particle is given by

$$\begin{aligned} X^{(0)}(x) = B^{(0)}(x) + \mu x, \end{aligned}$$

where \(\{ B^{(0)}(x): x \in \mathbb R \}\) is a Brownian motion. Using Burke’s theorem for Brownian motion [21], they constructed a stationary bi-infinite system of ordered particles

$$\begin{aligned} \cdots \le X^{(-1)} (x) \le X^{(0)} (x) \le X^{(1)}(x) \le \cdots , \qquad \forall x \ge 0, \end{aligned}$$

where each particle has the distribution of a standard Brownian motion (where the initial position is not zero) and, for each positive time x, the set of positions is distributed as a rate \(\mu \) Poisson process on the line.

Now, we show the relation to the tandem Brownian queues. Consider a TABEP system \(\{ X^{(n)} \}_{n \ge 0}\), defined by (7). Define the arrival process \(a(x):=\mu x -X^{(0)}(x)\) and the service processes \(s^{(n)}(x):=\mu x -B^{(n)}(x) \) for each \(n \ge 1\). (Note that a has zero drift and \(s^{(n)}(x)\) has positive drift \(\mu \).) Then, the associated first queue-length process is given by

$$\begin{aligned} q^{(1)}(x) = \sup _{ y \le x} (X^{(0)}(y) - X^{(0)}(x)+ B^{(1)}(x) - B^{(1)}(y) ), \quad \forall x \in \mathbb {R}, \end{aligned}$$

the first departure process is

$$\begin{aligned} d^{(1)}(x) = q^{(1)}(0) +X^{(0)}(0) + \mu x - \sup _{ y \le x } (X^{(0)}(y) + B^{(1)}(x) - B^{(1)}(y) ), \quad \forall x \in \mathbb {R}, \end{aligned}$$

and, by (7), we conclude that \(d^{(1)}(x) = X^{(0)}(0) + q^{(1)}(0) + \mu x - X^{(1)}(x)\) (we are using the convention \(d^{(1)}(0)=0\)).

Analogous formulae hold for any \(n\ge 1\), by induction: Suppose now that for a fixed natural k we have

$$\begin{aligned} d^{(k)} (x)= X^{(0)}(0) + \sum _{i=1}^{k} q^{(i)}(0) + \mu x - X^{(k)}(x), \quad \forall x \in \mathbb R. \end{aligned}$$

Then,

$$\begin{aligned} q^{(k+1)}(x)= & {} \sup _{ y \le x} ( d^{(k)} (y,x) - s^{(n)}(y,x) )\\= & {} \sup _{ y \le x} (X^{(k)}(y) - X^{(k)}(x)+ B^{(k)}(x) - B^{(k)}(y) ), \quad \forall x \in \mathbb {R}. \end{aligned}$$

Since \(d^{(k+1)}(0)=d^{(k)}(0)=0\), this implies that

$$\begin{aligned} d^{(k+1)} (x)= & {} d^{(k)} (x) - q^{(k+1)}(x) + q^{(k+1)}(0) \end{aligned}$$
(9)
$$\begin{aligned}= & {} X^{(0)}(0) + \sum _{i=1}^{k+1} q^{(i)}(0) + \sup _{ y \le x} (X^{(k)}(y) + B^{(k)}(x) - B^{(k)}(y) ), \quad \forall x \in \mathbb {R},\nonumber \\ \end{aligned}$$
(10)

where we also used the induction hypothesis. By (7), it follows that

$$\begin{aligned} d^{(k+1)} (x)= X^{(0)}(0) + \sum _{i=1}^{k+1} q^{(i)}(0) + \mu x - X^{(k+1)}(x), \quad \forall x \in \mathbb {R}. \end{aligned}$$

An important remark is that, by using (7), we get that

$$\begin{aligned} q^{(n)}(x) = X^{(n)}(x) - X^{(n-1)}(x), \end{aligned}$$

so the distance between the particles \(n-1\) and n is equal to the n-th queue-length process at time x. Thus, (3) is equivalent to Theorem 2.

Theorem 2

Start a two-sided TABEP with an ergodic process as the leftmost particle which satisfies (8) for some positive constant \(\mu \). Then, the limit of the (centered) n-th particle converges to a two-sided Brownian motion with drift \(\mu \), that is,

$$\begin{aligned} \lim _{n\rightarrow \infty }\left( X^{(n)}(x) -X^{(n)}(0) \right) {\mathop {=}\limits ^\mathrm{dist.}} B(x) + \mu x \, . \end{aligned}$$
(11)

3.2 Convergence of the Brownian last-passage percolation system

In this section, we define the elements of the theory of last-passage percolation systems [3] with Brownian passage times, as developed in [11], and show its relationship with tandem Brownian queues. Let \(\omega :=\left\{ B^{(n)}\,:\,n\in {\mathbb Z}\right\} \) be a collection of i.i.d. two-sided Brownian motions. Define the order “<” in \({\mathbb R}\times {\mathbb Z}\) as the coordinate-wise order. For \({\mathbf x}=(x,k)< {\mathbf y}=(y,l)\in {\mathbb R}\times {\mathbb Z}\), denote by \(\Gamma ({\mathbf x},{\mathbf y})\) the set of all real increasing sequences \(\gamma =(x=z_0\le z_{1}\le \dots \le z_{l-k+1}=y)\). The passage time of \(\gamma \) is defined as

$$\begin{aligned} L(\gamma ):=\sum _{i=0}^{l-k} B^{(k+i)}(z_i,z_{i+1}). \end{aligned}$$

The last-passage time between \({\mathbf x}\) and \({\mathbf y}\) is given by

$$\begin{aligned} L({\mathbf x},{\mathbf y}):=\sup _{\gamma \in \Gamma ({\mathbf x},{\mathbf y})}L(\gamma )\,. \end{aligned}$$
(12)

The passage time of a path \(\gamma \) can be seen as a continuous real-valued process \(X=(X(z): z \in \Gamma )\), where

$$\begin{aligned} \Gamma = \{ z=(z_1,\ldots ,z_{l-k}) : x \le z_1 \le \cdots \le z_{l-k} \le y \} \subseteq {\mathbb R}^{l-k}. \end{aligned}$$

Since \(\Gamma \) is compact, by continuity, we have that the maximum is attained at some location. In [16] is proven that, for \({\mathbf x}\) and \({\mathbf y}\) fixed, the maximum is attained at a unique location with probability one. However, it is not true that this uniqueness holds simultaneously for all points \({\mathbf x}, {\mathbf y}\in \mathbb {R} \times \mathbb {N}\). To see an example, for \(x>0\) define

$$\begin{aligned} \mathcal {Z}(x) = \{ z \in [0,x] \, : \, B^{(0)}{(0,z)} + B^{(1)}{(z,x)} = L({\mathbf 0}, (x,1) ) \}, \end{aligned}$$

where \({\mathbf 0}=(0,0)\). Put \(W_x:= B^{(0)}(x) - B^{(1)}(x)\) and note that \(z \in \mathcal {Z}(x)\) is equivalent to \(W_{z} = \sup _{ u \in [0,x] } W_u\). Thus, by Lévy’s theorem, we have that

$$\begin{aligned} \{ x \ge 0 \, : \, \# \mathcal {Z}(x)> 1 \} {\mathop {=}\limits ^\mathrm{dist.}} \{ x \ge 0 \, : \, \sqrt{2} \, l_x \text { is strictly increasing} \}, \end{aligned}$$

where \(l_x\) is the local time of a standard Brownian motion.

We will call the geodesic (or the maximizer) between \({\mathbf x}\) and \({\mathbf y}\) to be the path \(\gamma ({\mathbf x},{\mathbf y})\) such that

$$\begin{aligned} L(\gamma ({\mathbf x},{\mathbf y}))=L({\mathbf x},{\mathbf y}). \end{aligned}$$

To introduce the last-passage percolation system, we consider an initial profile \(\nu =(\nu (x)\,,x\in {\mathbb R})\) such that \(\nu (0)=0\) and

$$\begin{aligned} \liminf _{ y \rightarrow -\infty } \frac{ \nu (y) }{y} >0 , \end{aligned}$$
(13)

and define the (discrete time) evolution of \(\nu \) as the Markov process \((M^{(n)}_\nu \): \(n\ge 0)\), where \(M^{(0)}_{\nu }=\nu \),

$$\begin{aligned} L_\nu (x,n):=\sup _{z\le x}\left\{ \nu (z)+L\left( (z,1),(x,n)\right) \right\} \,\, \text{ and } \,\,M^{(n)}_\nu (x):=L_\nu (x,n)-L_\nu (0,n)\,. \end{aligned}$$
(14)

The Markov property follows from the following fact: for all \(n\ge 1\) and \(k\in \{0,\ldots ,n-1\}\)

$$\begin{aligned} L_\nu (x,n) - L_\nu (0,k) =\sup _{z\le x}\left\{ M^{(k)}_\nu (z)+L\left( (z,k+1),(x,n)\right) \right\} \,, \end{aligned}$$
(15)

which is an application of the dynamic programming principle. This is a graphical construction of the process where the space-time random environment is given by the collection of Brownian motions \(\omega = \left\{ B^{(n)}\,:\,n\in {\mathbb Z}\right\} \). The variational formula expresses the profile at time n as a function of the profile at time \(k<n\) plus some strip of the space-time environment which is independent of the profile at time k. We note that this construction allows us to run the last-passage percolation system, started with two arbitrary initial profiles \(\nu _1\) and \(\nu _2\), simultaneously with the same environment \(\omega \) (basic coupling). Formally speaking, we define the joint process \((M^{(n)}_{\nu _1},M^{(n)}_{\nu _2})_{n\ge 0}\) by setting

$$\begin{aligned} (x,n)\,\mapsto \,\left\{ \begin{array}{ll} L_{\nu _1}(x,n):=\sup _{z\le x}\left\{ \nu _1(z)+L\left( (z,1),(x,n)\right) \right\} \,,&{}\\ L_{\nu _2}(x,n):=\sup _{z\le x}\left\{ \nu _2(z)+L\left( (z,1),(x,n)\right) \right\} \, ,&{} \end{array} \right. \end{aligned}$$
(16)

and putting \(M^{(n)}_{\nu _i}(x):= L_{\nu _i}(x,n)- L_{\nu _i}(0,n)\) for x real and \(i=1,2\). Notice that \(L\left( (z,1),(x,n)\right) \) is a function that only depends on \(\omega \).

The analogy with the queueing system is as follows: Assume that \(\nu (x)\) has drift \(\mu \) and take

$$\begin{aligned} a(x)=\mu x - \nu (x)\quad \text{ and }\quad \,s^{(n)}(x):=\mu x-B^{(n)}(x). \end{aligned}$$
(17)

Then,

$$\begin{aligned} q^{(1)}(x):= \sup _{z\le x}\left\{ a(z,x)-s^{(1)}(z,x)\right\} =L_{\nu }(x,1)-\nu (x), \end{aligned}$$

and

$$\begin{aligned} d^{(1)}(x):=a(x) + q^{(1)}(0) - q^{(1)}(x)=\mu x - M_\nu ^{(1)}(x). \end{aligned}$$

From this, using definitions (1), (2), (14) and induction, one can check the analogous relation for all \(n\ge 2\):

$$\begin{aligned} q^{(n)}(x)= \sup _{z\le x}\left\{ d^{(n-1)}(z,x)-s^{(n)}(z,x)\right\} =L_{\nu }(x,n)-L_{\nu }(x,n-1), \end{aligned}$$

and

$$\begin{aligned} d^{(n)}(x)=a(x) + q^{(n)}(0) - q^{(n)}(x)=\mu x - M_\nu ^{(n)}(x). \end{aligned}$$

Thus, (3) and (11) are consequences of (19). Define

$$\begin{aligned} B_\mu (x)=\mu x+B(x), \end{aligned}$$

where B is a standard Brownian motion. Using the invariance of the Brownian measure under the queueing operator, it is immediate that \(B_\mu \) is invariant:

$$\begin{aligned} M_{\mu }^{(n)}\equiv M_{B_\mu }^{(n)}{\mathop {:=}\limits ^\mathrm{dist.}}B_\mu ,\quad \text{ for } \text{ all }\quad n\ge 0. \end{aligned}$$

The main contribution of this article is the next theorem, from which (3) [and (11)] will follow.

Theorem 3

Let \(\mu \in (0,\infty )\) and assume that, almost surely,

$$\begin{aligned} \liminf _{x\rightarrow -\infty }\frac{\nu (x)}{x}\ge \mu \,\,\,\text{ and }\,\,\,\limsup _{x\rightarrow \infty }\frac{\nu (x)}{x}\le \mu \,. \end{aligned}$$
(18)

Consider the basic coupling \((M_{\nu }^{(n)},M^{(n)}_\mu )_{n\ge 0}\) constructed by running the last-passage percolation system, started with \(\nu \) and \(B_\mu \), simultaneously with the same environment \(\omega =\left\{ B^{(n)}\,:\,n\in {\mathbb Z}\right\} \). Then, for all compact \(K\subseteq {\mathbb R}\) and \(\epsilon >0\),

$$\begin{aligned} \lim _{n\rightarrow \infty }{\mathbb {P}}\left( \sup _{x\in K}|M_{\nu }^{(n)}(n,\mu ^{-2}n+x)-M_\mu ^{(n)}(n,\mu ^{-2}n+x)|>\epsilon \right) =0\,. \end{aligned}$$
(19)

It should be clear that an ergodic initial profile satisfies (18) almost surely (note that in that case, we have translation invariance of the law of \(M_\nu ^{(n)}\) and \(M_\mu ^{(n)}\), so that we can get rid of the translation by \(\mu ^{-2}n\)). We note that (19) implies local convergence for initial profiles beyond the ergodic condition: one could take a deterministic profile satisfying (18).

4 Proofs

4.1 Shape theorem and exit points

First proven in [1, 10], using that \(L( {\mathbf 0}, (n,n))\) has the same law as the largest eigenvalue of a \(n \times n\) GUE random matrix, the shape theorem below is presented by Hambly et al. [11] as a consequence of concentration results for the Brownian directed percolation paths:

$$\begin{aligned} \lim _{n\rightarrow \infty }\frac{1}{n} L ({\mathbf 0}, (xn,tn)) {\mathop {=}\limits ^{a.s.}} 2 \sqrt{xt}. \end{aligned}$$
(20)

Note that, by Brownian scaling,

$$\begin{aligned} \left\{ L({\mathbf 0}, (rn,n))\,:\,r\in [0,x]\right\} {\mathop {=}\limits ^\mathrm{dist.}}\left\{ \sqrt{x}L({\mathbf 0},(sn,n))\,:\,s\in [0,1]\right\} . \end{aligned}$$
(21)

Remark

By Lemma 7 in [11], there exist constants \(c_1,c_2 \ge 0\) such that

$$\begin{aligned} \mathbb {P} \Big ( \Big | \frac{ L ( {\mathbf 0}, (n,n))}{n} - 2 \Big | \ge 2 y \Big ) \le c_1 \exp \{-c_2 \, n (y- \epsilon _n)^2 \}, \end{aligned}$$
(22)

for all \(n \ge 0\), and \(y > \epsilon _n\), where

$$\begin{aligned} \epsilon _n := 2 - \frac{{\mathbb E}L ({\mathbf 0},(n,n))}{n} + \frac{1}{n^{1/4}}. \end{aligned}$$

Since \(\epsilon _n \rightarrow 0\), we can choose n large such that \(\epsilon _n < 4^{-1} \delta \) and take \(y=2^{-1} \delta \). This implies that there exist constants \(c_3,c_4>0\) such that for all \(\delta >0\) there exists \(N>0\) such that

$$\begin{aligned} \mathbb {P} \Big ( \Big | \frac{ L ( {\mathbf 0}, (n,n))}{n} - 2 \Big | \ge \delta \Big ) \le c_3 \exp \{-c_3 \, n \delta ^2 \}, \end{aligned}$$

for all \(n \ge N\). We notice that a better upper bound could be produced by using the coupling method [2] to prove that

$$\begin{aligned} {\mathbb E}|L( {\mathbf 0}, (n,n))-2n|=O(n^{1/3}), \end{aligned}$$

which would imply that \(\epsilon _n=O(n^{-1/4})\). For the Brownian last-passage percolation model, we have all the ingredients necessary for the coupling method: we know explicitly the invariant regime and the shape function.

From now on, we will treat \(\nu \) as a fixed deterministic profile satisfying (18). Define the exit point from (x, n) as

$$\begin{aligned} Z_{\nu } (x,n) = \sup \left\{ z \le x : L_{\nu } (x,n) = \nu (z) + L( (z,1),(x,n) ) \right\} . \end{aligned}$$
(23)

We note that it is well defined. First, since we have the same asymptotic hypothesis (13) on the profile \(\nu \), one can use similar arguments to Proposition 4.1 of [3] to prove that the function \(L_{\nu } (x,n)\) is well defined. By Brownian continuity, the map \(z \rightarrow L( (z,1),(x,n) )\) is continuous, as is the profile \(\nu \) (by hypothesis). Then, the set \( \left\{ z \in \mathcal C : L_{\nu } (x,n) = \nu (z) + L( (z,1),(x,n) ) \right\} \) is non-empty for any compact set C. To prove that the supremum over \(z \le y\) can be restricted to some compact set, one can mimic the proof of Lemma 4.3 in [3].

The name exit point comes from the next geometric interpretation in last-passage percolation: \(Z_{\nu } (x,n)\) is the time before x when the path which maximizes the quantity \(\nu (z) + L( (z,1),(x,n) )\) leaves the initial profile \(\nu \) (that can be visualized on the line \(\{ (x,0) : x \in \mathbb R \}\)) to percolate to the point (x, n).

The exit point (23) can also be described in terms of the tandem queueing system. First, let us examine the interpretation for \(Z_{\nu } (x,1)\). Let \(z^*\) be in \(\left\{ z \le x : L_{\nu } (x,1) = \nu (z) + L( (z,1),(x,1) ) \right\} \). Then,

$$\begin{aligned} \nu (z^*) + L( (z^*,1),(x,1)) \ge \nu (z) + L( (z,1),(x,1)), \quad \forall z \le x, \end{aligned}$$

and, by (17), this implies that

$$\begin{aligned} a(z)-s^{(1)}(z) \ge a(z^*)-s^{(1)}(z^*), \quad \forall z \le x. \end{aligned}$$

In other words,

$$\begin{aligned} a(z^*,x) - s^{(1)}(z^*,x) \ge a(z,x) - s^{(1)}(z,x), \quad \forall z \le x, \end{aligned}$$

so \(q^{(1)}(x)= a(z^*,x) - s^{(1)}(z^*,x)\) [by the definition (1)]. This implies that \(q^{(1)} (z^*)=0\), so the value \(Z_{\nu } (x,1)\) is the last time when the queue-length process \(q^{(1)}\) was empty before time x. For n arbitrary, using the expression (15), one can check that the value \(Z_{\nu } (x,n)\) can be obtained inductively: let \(I_{n-1}(x,n)\) be the last time when \(q^{(n)}\) was empty before time x, then \(I_{n-2}(x,n)\) is the last time when \(q^{(n-1)}\) was empty before time \(I_{n-1}(x,n)\), and so on, until we find the exit point \(Z_{\nu }(x,n)=I_0(x,n)\).

In the next result, we show that, in probability, the exit point is asymptotically sublinear.

Lemma 1

Let \(\mu \in (0,\infty )\) and assume (18). Then, for all \(C\in {\mathbb R}\) and \(\epsilon >0\),

$$\begin{aligned} \lim _{n\rightarrow \infty }\mathbb {P} \left( n^{-1}|Z_\nu (\mu ^{-2}n+C,n)|>\epsilon \right) =0. \end{aligned}$$

Proof

By Brownian scaling (21), one can restrict attention to \(\mu =1\). For fixed \(\delta >0\), take \(B_{1+\delta }\) and construct \(L_{1+\delta }\) and \(L_\nu \) simultaneously using the basic coupling (16). Since

$$\begin{aligned} L\left( (z,1),(n+C,n)\right) \le L_{1+\delta }(n+C,n) - B_{1+\delta }(z), \end{aligned}$$

and

$$\begin{aligned} L\left( (1,0),(n+C,n)\right) =L\left( (1,0),(n+C,n)\right) +\nu (0)\le L_\nu (n+C,n)\, \end{aligned}$$

(recall that \(\nu (0)=0\)), we have that

$$\begin{aligned} \left\{ Z_\nu (n+C,n)\ge u \right\} =\left\{ \exists \,z\in [u,n+C]\,:\,\nu (z)+L\left( (z,1),(n+C,n)\right) =L_\nu (n+C,n)\right\} \, \end{aligned}$$

is contained in the event

$$\begin{aligned} \left\{ \exists \,z\in [u,n+C]\,:\,B_{1+\delta }(z)-\nu (z)\le L_{1+\delta }(n+C,n)-L\left( (1,0),(n+C,n)\right) \right\} . \end{aligned}$$

By (18), there exists \(K_0>0\) such that \(\nu (z)\le (1+\delta /2)z\) for all \(z>K_0\). Hence, if \(u>K_0\), then \(\left\{ Z_\nu (n+C,n)\ge u \right\} \) is contained in the event

$$\begin{aligned} \left\{ \exists \,z\in [u,n+C]\,:\,B_{2^{-1}\delta }(z)\le L_{1+\delta }(n+C,n)-L\left( (1,0),(n+C,n)\right) \right\} \,. \end{aligned}$$
(24)

Now, we recenter the Brownian motion with drift at position u by writing

$$\begin{aligned} B_{2^{-1}\delta }(z):=B_{2^{-1}\delta }(u)+\bar{B}_{2^{-1}\delta }(z), \end{aligned}$$

where \(\bar{B}_{2^{-1}\delta }(z):= B_{2^{-1}\delta }(z)-B_{2^{-1}\delta }(u)\) for \(z\ge u\). Notice that \(\{ \bar{B}_{2^{-1}\delta }(z) : z \ge u \}\) has the same distribution as the process \( \{ B_{2^{-1}\delta }(z) : z\ge 0 \}\) and it is independent of \(B_{2^{-1}\delta }(u)\). Let

$$\begin{aligned} A(u):=B_{2^{-1}\delta }(u)+\min _{z\ge u} \bar{B}_{2^{-1}\delta }(z). \end{aligned}$$

This minimum is well defined because \(\bar{B}_{2^{-1}\delta }\) has a positive drift, and its distribution is given by minus an exponential random variable of parameter \(2^{-1}\delta \) (its value will not play an important role when n grows to infinity, since \(\delta \) is fixed). Thus, by (24),

$$\begin{aligned} \left\{ Z_\nu (n+C,n)\ge u \right\} \subseteq \left\{ A(u)\le L_{1+\delta }(n+C,n)-L\left( (1,0),(n+C,n)\right) \right\} , \qquad \forall u \le n+C \,. \end{aligned}$$
(25)

The strategy is to show that if \(u=\epsilon n\), we can choose \(\delta >0\) such that the event on the r.h.s. of (25) has small probability. For \(\epsilon _1>0\), to be defined later, we have that the event on the r.h.s. of (25) has probability bounded by

$$\begin{aligned} {\mathbb {P}}\Big (L (\left( 1,0),(n+C,n)\right) -2n\le -\epsilon _1 n\Big )+{\mathbb {P}}\Big (A(u)\le L_{1+\delta }(n+C,n)-2n+\epsilon _1 n\Big ). \end{aligned}$$

By the shape theorem,

$$\begin{aligned} \lim _{n\rightarrow \infty }{\mathbb {P}}\Big (L\left( (1,0),(n+C,n)\right) -2n\le -\epsilon _1 n\Big )=0. \end{aligned}$$

On the other hand,

$$\begin{aligned} {\mathbb {P}}\Big (A(u)\le L_{1+\delta }(n+C,n)-2n+\epsilon _1 n\Big )\le & {} {\mathbb {P}}\Big (2^{-1}\delta u-2\epsilon _1 n\le L_{1+\delta }(n+C,n)-2n\Big )\nonumber \\&+{\mathbb {P}}\Big (A(u)\le 2^{-1}\delta u-\epsilon _1 n\Big ). \end{aligned}$$
(26)

We now use a result in Section 4 of [21], where it is shown (in our notation) that \(L_\lambda (0,n) - L_\lambda (0,0)\) (this is the vertical increment) is distributed as the sum of nindependent exponential random variables, each with expectation \(1/\lambda \). We already know that \(x\mapsto L_\lambda (x,n)-L_\lambda (0,n)\) (the horizontal increment) is distributed as Brownian motion with drift \(\lambda \). This shows us how to recenter \(L_{1+\delta }(n+C,n)\):

$$\begin{aligned}&{\mathbb {P}}\Big (2^{-1}\delta u-2\epsilon _1 n\le L_{1+\delta }(n+C,n)-2n\Big )\\&\quad ={\mathbb {P}}\left( \Delta -2\epsilon _1 n\le L_{1+\delta }(n+C,n)-\left( (1+\delta )+\frac{1}{1+\delta }\right) n\right) , \end{aligned}$$

where

$$\begin{aligned} \Delta:= & {} 2n-\left( (1+\delta )+\frac{1}{1+\delta }\right) n+\frac{\delta }{2}u\\= & {} -\frac{\delta ^2}{(1+\delta )}n+\frac{\delta }{2}u\\> & {} \left( \frac{\delta }{2}\frac{u}{n}-\delta ^2\right) n\,. \end{aligned}$$

If \(u=\epsilon n\) and we pick \(\delta :=4^{-1}\epsilon \), we get the next lower bound for \(\Delta \):

$$\begin{aligned} \Delta> & {} \left( \frac{\delta }{2}\epsilon -\delta ^2\right) n\\= & {} \frac{\epsilon ^2}{16}n\,. \end{aligned}$$

Thus, for \(\epsilon _1:=\frac{\epsilon ^2}{64}\),

$$\begin{aligned}&{\mathbb {P}}\Big (2^{-1}\delta u-2\epsilon _1 n\le L_{1+\delta }(n+C,n)-2n\Big )\\&\quad \le {\mathbb {P}}\left( 32^{-1}\epsilon ^2 n\le L_{1+\delta }(n+C,n)-\left( (1+\delta )+\frac{1}{1+\delta }\right) n\right) . \end{aligned}$$

We have already seen that \(L_{1+\delta }(0,n)-n/(1+\delta )\) has expectation 0 and variance of order n, and also that \(L_{1+\delta }(n+C,n)-L_{1+\delta }(0,n) - (1+\delta )n\) has expectation \(C(1+\delta )\) and variance of order n, so we conclude that

$$\begin{aligned} \lim _{n\rightarrow \infty }{\mathbb {P}}\left( 32^{-1}\epsilon ^2 n\le L_{1+\delta }(n+C,n)-\left( (1+\delta )+\frac{1}{1+\delta }\right) n\right) =0, \end{aligned}$$

and hence

$$\begin{aligned} \lim _{n\rightarrow \infty }{\mathbb {P}}\Big (2^{-1}\delta u-2\epsilon _1 n\le L_{1+\delta }(n+C,n)-2n\Big )=0. \end{aligned}$$

To bound the second summand in (26), take \(u=\epsilon n\) and write

$$\begin{aligned} \lim _{n\rightarrow \infty } {\mathbb {P}}\Big ( A(u)\le 2^{-1}\delta u-\epsilon _1 n\Big ) = \lim _{n\rightarrow \infty } {\mathbb {P}}\Big ( \frac{B( \epsilon n)}{n} + \frac{\min _{ z\ge \epsilon n } \bar{B}_{2^{-1}\delta }(z) }{n} \le -\epsilon _1 \Big )=0. \end{aligned}$$

By (24), this concludes the proof of

$$\begin{aligned} \lim _{n\rightarrow \infty }{\mathbb {P}}\left( Z_\nu (n+C,n)>\epsilon n \right) =0\,. \end{aligned}$$

To get the analogous result for \(\left\{ Z_\nu (n+C,n)<-\epsilon n \right\} \), one just needs to adapt the same argument. \(\square \)

4.2 Local comparison and attractiveness

In the next lemmas, we will always construct \(L_{\nu _1}\) and \(L_{\nu _2}\) simultaneously using the basic coupling (16).

Lemma 2

If \(x<y\) and \(Z_{\nu _1}(y,n)\le Z_{\nu _2}(x,n)\), then

$$\begin{aligned} L_{\nu _1}(y,n)-L_{\nu _1}(x,n)\le L_{\nu _2}(y,n)-L_{\nu _2}(x,n). \end{aligned}$$

Proof

Recall the definition of the geodesic \(\gamma ({\mathbf x},{\mathbf y})\) between two points \({\mathbf x}< {\mathbf y}\) in \(\mathbb R \times \mathbb Z\) in Sect. 3.2. Denote by \(\gamma _n^z(x)\) the geodesic between (z, 1) and (x, n). Notice that

$$\begin{aligned} L\left( (z,1),(x,n)\right) =L\left( (z,1),(y,m)\right) +L((y,m),(x,n)), \end{aligned}$$

for any \((y,m)\in \gamma _n^z(x)\).

Assume that \(Z_{\nu _1}(y,n)\le Z_{\nu _2}(x,n)\) and let \(z_1\equiv Z_{\nu _1}(y,)\) and \(z_2\equiv Z_{\nu _2}(x,n)\). Let \({\mathbf c}\) be a crossing point between the two geodesics \(\gamma _n^{z_1}(y)\) and \(\gamma _n^{z_2}(x)\). Such a crossing point always exists because \(x\le y\) and \(z_1\le z_2\) (by assumption). We remark that, by superadditivity of L,

$$\begin{aligned} L_{\nu _2}(y,n) \ge \nu _2(z_2) + L\left( (z_2,1),(y,n)\right) \ge \nu _2(z_2) + L\left( (z_2,1),{\mathbf c}\right) + L\left( {\mathbf c},(y,n)\right) . \end{aligned}$$

We use this, and that (since \({\mathbf c}\in \gamma _n^{z_2}(x)\))

$$\begin{aligned} \nu _2(z_2) + L\left( (z_2,1),{\mathbf c}\right) -L_{\nu _2}(x,n)= -L\left( {\mathbf c},(x,n)\right) \end{aligned}$$

in the following inequality:

$$\begin{aligned} M^{(n)}_{\nu _2}(x,y)= & {} L_{\nu _2}(y,n) - L_{\nu _2}(x,n) \\\ge & {} \nu _2(z_2)+L\left( (z_2,1),{\mathbf c}\right) + L\left( {\mathbf c},(y,n)\right) - L_{\nu _2}(x,n)\\= & {} L\left( {\mathbf c},(y,n)\right) - L\left( {\mathbf c},(x,n)\right) . \end{aligned}$$

By superadditivity,

$$\begin{aligned} - L\left( {\mathbf c},(x,n)\right) \ge L_{\nu _1}({\mathbf c})-L_{\nu _1}(x,n), \end{aligned}$$

and hence (since \({\mathbf c}\in \gamma _{z_1}(y,n)\))

$$\begin{aligned} M^{(n)}_{\nu _2}(x,y)\ge & {} L\left( {\mathbf c},(y,n)\right) - L\left( {\mathbf c},(x,n)\right) \\\ge & {} L\left( {\mathbf c},(y,n)\right) + L_{\nu _1}({\mathbf c})-L_{\nu _1}(x,n)\\= & {} L_{\nu _1}(y,n)-L_{\nu _1}(x,n)\\= & {} \Delta M^{(n)}_{\nu _1}(x,y). \end{aligned}$$

\(\square \)

Lemma 3

Assume that \(\nu _1(y)-\nu _1(x)\le \nu _2(y)-\nu _2(x)\) for all \(x<y\). Then,

$$\begin{aligned} L_{\nu _1}(y,n)-L_{\nu _1}(x,n)\le L_{\nu _2}(y,n)-L_{\nu _2}(x,n),\quad \forall \,x<y. \end{aligned}$$

Proof

Let

$$\begin{aligned} z_1:=Z_{\nu _1}(y,n)\,\, \text{ and } \,\,z_2:=Z_{\nu _2}(x,n). \end{aligned}$$

If \(z_1 \le z_2\), then this follows from Lemma 2 (we do not need to use the assumption). If \(z_1>z_2\), then

$$\begin{aligned}&L_{\nu _2}(y,n)-L_{\nu _2}(x,n) -\big (L_{\nu _1}(y,n)-L_{\nu _1}(x,n)\big )\\&= L_{\nu _2}(y,n)-\big (\nu _2(z_2)+L\left( (z_2,1),(x,n)\right) \big )-\Big (\big (\nu _1(z_1)+L\left( (z_1,1),(y,n)\right) \big )-L_{\nu _1}(x,n)\Big )\\&= L_{\nu _2}(y,n)-\big (\nu _2(z_2)+L\left( (z_1,1),(y,n)\right) \big )-\Big (\big (\nu _1(z_1)+L\left( (z_2,1),(x,n)\right) \big )-L_{\nu _1}(x,n)\Big )\\&= L_{\nu _2}(y,n)-\big (\nu _2(z_2)+L\left( (z_1,1),(y,n)\right) \big )+\Big (L_{\nu _1}(x,n)- \big (\nu _1(z_1)+L\left( (z_2,1),(x,n)\right) \big )\Big )\\&= L_{\nu _2}(y,n)-\big (\nu _2(z_1)+L\left( (z_1,1),(y,n)\right) \big )+\Big (L_{\nu _1}(x,n)- \big (\nu _1(z_2)+L\left( (z_2,1),(x,n)\right) \big )\Big )\\&\quad +\big (\nu _2(z_1)-\nu _2(z_2)\big )-\big (\nu _1(z_1)-\nu _1(z_2)\big ). \end{aligned}$$

By superadditivity,

$$\begin{aligned} L_{\nu _2}(y,n)-\big (\nu _2(z_1)+L_{z_1}(y,n)\big )\ge 0, \end{aligned}$$

and

$$\begin{aligned} L_{\nu _1}(x,n)- \big (\nu _1(z_2)+L_{z_2}(x,n)\big )\ge 0, \end{aligned}$$

while, by assumption,

$$\begin{aligned} \nu _2(z_1)-\nu _2(z_2)\ge \nu _1(z_1)-\nu _1(z_2), \end{aligned}$$

since \(z_1>z_2\). \(\square \)

4.3 Proof of Theorem 3

Without loss of generality, we will assume that \(\mu =1\) [again by Brownian scaling (21)] and that \(K=[0,C]\) with \(C>0\). We take as an initial profile a Brownian motion with drift 1,

$$\begin{aligned} B_1(x):=x+B(x), \end{aligned}$$

and also

$$\begin{aligned} B_{\mu _\pm }:=\mu _{\pm }x+B(x), \end{aligned}$$

with \(\mu _\pm :=1\pm \delta \) and \(\delta >0\). Thus,

$$\begin{aligned} B_{\mu _-}(y)-B_{\mu _-}(x)\le B_{1}(y)-B_{1}(x)\le B_{\mu _+}(y)- B_{\mu _+}(x). \end{aligned}$$

Lemma 4

Let \(\mu \in (0,\infty )\) and assume (18). Then, for all \(C>0\),

$$\begin{aligned} \lim _{n\rightarrow \infty }{\mathbb {P}}\Big (Z_{\mu _-}(n+C,n)\le Z_\nu (n,n)\, \text{ and } \,Z_{\nu }(n+C,n)\le Z_{\mu _+}(n,n)\Big )=1. \end{aligned}$$

Proof

Let us first prove that

$$\begin{aligned} \lim _{n\rightarrow \infty }{\mathbb {P}}\left( Z_{\mu _-}(n+C,n)\le Z_\nu (n,n)\right) =1. \end{aligned}$$

For any \(\epsilon >0\),

$$\begin{aligned} {\mathbb {P}}\left( Z_{\mu _-}(n+C,n)> Z_\nu (n,n)\right) \le {\mathbb {P}}\left( Z_{\mu _-}(n+C,n) > -\epsilon n\right) +{\mathbb {P}}\left( Z_\nu (n,n)<-\epsilon n\right) . \end{aligned}$$

Thus, by Lemma 1, it is enough to show that (for fixed \(\delta ,C>0\)) we can choose \(\epsilon >0\) such that

$$\begin{aligned} \lim _{n\rightarrow \infty }{\mathbb {P}}\left( Z_{\mu _-}(n+C,n)\le -\epsilon n\right) =1\,. \end{aligned}$$
(27)

By shift invariance of Brownian motion (\(B(x+C)-B(C){\mathop {=}\limits ^\mathrm{dist.}}B(x)\)),

$$\begin{aligned} {\mathbb {P}}\left( Z_{\mu _-}(n+C,n)>-\epsilon n\right) ={\mathbb {P}}\left( Z_{\mu _-}(n,n)>-\epsilon n-C\right) \le {\mathbb {P}}\left( Z_{\mu _-}(n,n)>-2\epsilon n\right) , \end{aligned}$$

for \(n\ge C/\epsilon \). Since

$$\begin{aligned} n=\mu ^{-2}_{-}n+\left( 1-\mu ^{-2}_{-}\right) n \quad \text{ and }\quad \left( 1-\mu ^{-2}_{-}\right) <-\delta , \end{aligned}$$

(recall that \(\delta \in (0,1/2)\)) by using shift invariance again,

$$\begin{aligned} {\mathbb {P}}\left( Z_{\mu _-}(n,n)>-2\epsilon n\right) \le {\mathbb {P}}\left( Z_{\mu _-}(\mu ^{-2}_{-}n,n) >(\delta -2\epsilon )n\right) . \end{aligned}$$

Hence, if \(\epsilon <\delta /2\), Lemma 1 implies (27). The proof of

$$\begin{aligned} \lim _{n\rightarrow \infty }{\mathbb {P}}\left( Z_{\nu }(n+C,n)\le Z_{\mu _+}(n,n) \right) =1 \end{aligned}$$

is analogous. \(\square \)

If \(Z_{\mu _-}(n+C,n)\le Z_\nu (n,n)\) and \(Z_{\nu }(n+C,n)\le Z_{\mu _+}(n,n)\), then \(Z_{\mu _-}(n+x,n)\le Z_\nu (n,n)\) and \(Z_{\nu }(n+x,n)\le Z_{\mu _+}(n,n)\) for all \(x\in [0,C]\). We use that \(Z_\nu (y,n)\) is a non-decreasing function of y (for fixed n). By Lemma 2,

$$\begin{aligned} M_{\mu _-}^{(n)}(n,n+x)\le M_\nu ^{(n)}(n,n+x)\le M_{\mu _+}^{(n)}(n,n+x), \end{aligned}$$

for all \(x\in [0,C]\), and, by Lemma 3,

$$\begin{aligned} M_{\mu _-}^{(n)}(n,n+x)\le M_1^{(n)}(n,n+x)\le M_{\mu _+}^{(n)}(n,n+x), \end{aligned}$$

for all \(x\in [0,C]\). Therefore,

$$\begin{aligned} |M_\nu ^{(n)}(n,n+x)-M_1^{(n)}(n,n+x)|\le & {} M_{\mu _+}^{(n)}(n,n+x)-M_{\mu _-}^{(n)}(n,n+x)\\\le & {} M_{\mu _+}^{(n)}(n,n+C)-M_{\mu _-}^{(n)}(n,n+C)\,, \end{aligned}$$

for all \(x\in [0,C]\). We use that \(M_{\mu _+}^{(n)}(n,n+x)-M_{\mu _-}^{(n)}(n,n+x)\) is a non-decreasing function of x (Lemma 3). Hence, if \(Z_{\mu _-}(n+C,n)\le Z^\nu (n,n)\) and \(Z_{\nu }(n+C,n)\le Z_{\mu _+}(n,n)\), then

$$\begin{aligned} \sup _{x\in [0,C]}|M_\nu ^{(n)}(n,n+x)-M_1^{(n)}(n,n+x)|\le M_{\mu _+}^{(n)}(n,n+C)-M_{\mu _-}^{(n)}(n,n+C)\,. \end{aligned}$$
(28)

Since \(M_{\mu _+}^{(n)}(n,n+C)-M_{\mu _-}^{(n)}(n,n+C)\ge 0\) (Lemma 3) and

$$\begin{aligned} {\mathbb E}\left( M_{\mu _+}^{(n)}(n,n+C)-M_{\mu _-}^{(n)}(n,n+C)\right) = (\mu _+-\mu _-)C=2\delta C, \end{aligned}$$

we have that

$$\begin{aligned} {\mathbb {P}}\left( M_{\mu _+}^{(n)}(n,n+C)-M_{\mu _-}^{(n)}(n,n+C)>\epsilon \right) \le \frac{2C}{\epsilon }\delta . \end{aligned}$$

Together with Lemma 4 and (28), this implies that

$$\begin{aligned} \limsup _{n\rightarrow \infty }{\mathbb {P}}\left( \sup _{x\in [0,C]}|M_\nu ^{(n)}(n,n+x)-M_1^{(n)}(n,n+x)|>\eta \right) \le \frac{2C}{\epsilon }\delta , \end{aligned}$$

under (18). Since \(\delta >0\) is arbitrary, we must have that

$$\begin{aligned} \limsup _{n\rightarrow \infty }{\mathbb {P}}\left( \sup _{x\in [0,C]}|M_\nu ^{(n)}(n,n+x)-M_1^{(n)}(n,n+x)|>\epsilon \right) =0 \end{aligned}$$

under hypothesis (18), and Theorem 3 is proven. \(\square \)

5 Conclusion

We proved that under mild conditions an initial flow passing through an infinite system of Brownian tandem queues converges in distribution to a Brownian motion. The strong relationship between the queueing system and the last-passage Brownian percolation model is fundamental for the proof since it allows us to construct a coupling between different initial configurations using the concept of exit points in the LPP setting. This is a convenient way to manipulate the busy periods associated with the tandem queues. One wonders if this relation, or the one with the TABEP system, could be useful to compute non-asymptotic formulae for the queueing system. An example of this kind of result, whose interpretation in the Brownian tandem queues setting has not yet been studied, is presented in [5], where an explicit determinantal formula is obtained for the joint distribution of particles in a periodic finite system of particles interacting by one-sided reflection.