A review of Burke’s theorem for Brownian motion

Abstract

Burke’s theorem is a well-known fundamental result in queueing theory, stating that a stationary M/M/1 queue has a departure process that is identical in law to the arrival process and, moreover, for each time t, the following three random objects are independent: the queue length at time t, the arrival process after t and the departure process before t. Burke’s theorem also holds for a stationary Brownian queue. In particular, it implies that a certain “complicated” functional derived from two independent Brownian motions is also a Brownian motion. The aim of this overview paper is to present an independent complete explanation of this phenomenon.

1 Introduction

Consider two independent standard Brownian motions $B^1_t$, $B^2_t$ and an independent exponential random variable Z with mean 1. The following often comes as a surprise.

Theorem 1

For any $\lambda > 0$, the process

$$\begin{aligned} {D^{(\lambda )}_t :}= \inf _{0 \le s \le t} \left\{ \frac{1}{\lambda } Z + B^1_s + B^2_t-B^2_s + \lambda (t-s) \right\} \wedge (B^2_t+\lambda t), \quad t \ge 0, \end{aligned}$$

(1)

is a standard Brownian motion.

Recall that a Brownian motion $B_t$ is 1 / 2-self-similar, meaning that ($B_{\alpha t}, t \ge 0) {\mathop {=}\limits ^\mathrm{(d)}} (\alpha ^{1/2} B_t, t \ge 0)$, for all $\alpha > 0$, where ${\mathop {=}\limits ^\mathrm{(d)}}$ means equality in distribution (of the two objects as random elements in the space of continuous functions). However, it is not possible to deduce that $D^{(\lambda )}_t$ is 1 / 2-self-similar directly from the formula. The only thing directly observable is that

$$\begin{aligned} \big (D^{(\lambda )}_t, t \ge 0\big ) \mathop {=}\limits ^\mathrm{(d)}\left( \lambda ^{-1} D^{(1)}_{\lambda ^ 2 t}, t \ge 0\right) , \end{aligned}$$

by the 1 / 2-self-similarity of $B^i_t$, $i=1,2$, implying that proving the theorem for $\lambda =1$ proves it for all $\lambda$.

To understand what this formula says it is worth our while playing with it until we realize its “geometric” meaning. Let $x: [0,\infty )\rightarrow \mathbb {R}$ be any function representing the motion of a particle. Let $\alpha :[0,\infty )\rightarrow \mathbb {R}$ be another function such that $\alpha (0) \le x(0)$ and define¹

$$\begin{aligned} {z(t) :}= x(t)-\inf _{0\le s \le t} (x(s)-\alpha (s)) \wedge 0. \end{aligned}$$

(2)

Clearly, $z(t) \ge x(t)-(x(t)-\alpha (t)) = \alpha (t)$ for all t, whereas ${\ell (t) :}= -\inf _{0\le s \le t} (x(s)-\alpha (s)) \wedge 0$ satisfies $\ell (0)=0$ and $\ell (t_1) \le \ell (t_2)$ if $t_1 < t_2$ ($\ell$ is increasing). Now take any increasing function $m:[0,\infty )\rightarrow \mathbb {R}$ such that $m(0)=0$. Then $\ell (t) \le m(t)$ for all $t \ge 0$. We call the function z the reflection of x upwards at $\alpha$, and this conveys a natural physical meaning. See Fig. 1 for an example. Reversing directions, we can reflect x downwards at some function $\beta : [0,\infty ) \rightarrow \mathbb {R}$, so long as $x(0) \le \beta (0)$, via the formula

$$\begin{aligned} w(t) = x(t) + \inf _{0\le s \le t} \left( \beta (s)-x(s)\right) \wedge 0. \end{aligned}$$

(3)

This is natural: if $R_\uparrow$ is the mapping $(x,\alpha ) \mapsto z$ then the mapping $R_\downarrow : (x,\beta ) \mapsto w$ is obtained by applying $R_\uparrow$ to $(-x, -\alpha )$ and then reversing the sign. That is, $R_\downarrow (x,\beta ) = - R_\uparrow (-x,-\beta )$. We call w the reflection of x downwards at $\beta$ and can easily ascribe physical meaning to it.

Fig. 1

An example of reflection of a function x(t) upwards at the lower barrier function $\alpha (t)= \sin t$. The free process is of the form $x(t)=c-t\,\sin (\omega t)$ for some $c > 0$ and $\omega > 1$. The reflected process is denoted by z(t). See Eq. (2)

Fig. 2

The figure shows the simulation (done in Maple™and labeled in Gimp™) of a Brownian motion with drift, $X(t)=B^2_t+\lambda t$, and a Brownian motion started from an exponential random variable, $\beta (t)=\frac{Z}{\lambda }+B^2_t$. The process $D^{(\lambda )}_t$ is obtained by reflecting X(t) downwards at $\beta (t)$ and is a standard Brownian motion

If we now take a look and rewrite the formula (1) for $D^{(\lambda )}_t$ as

$$\begin{aligned} D^{(\lambda )}_t = \left( B_t^2+\lambda t\right) + \inf _{0 \le s \le t} \left\{ \frac{1}{\lambda } Z + B^1_s -\left( B^2_s + \lambda s\right) \right\} \wedge 0, \end{aligned}$$

(4)

we see, by comparison to (3), that $D^{(\lambda )}_t$ is the reflection of $x(t) = B^2_t+\lambda t$ (a Brownian motion with drift $\lambda$) downwards at $\beta (t)=\frac{1}{\lambda } Z + B^1_t$ (a Brownian motion starting from an independent exponential random variable with rate $\lambda$). See Fig. 2, why this reflection is a standard Brownian motion, for any $\lambda$, is what we will explain later.

However, let us look at the limiting cases $\lambda \rightarrow 0$ and $\lambda \rightarrow \infty$. When $\lambda$ tends to 0, the boundary process $\beta (t)$ tends to $+\infty$ (so the effect of the reflection vanishes), whereas x(t) tends to $B^2_t$. Hence, the process $D^{(\lambda )}_t$ tends to $B^2_t$. When $\lambda$ tends to $\infty$, the boundary process $\beta (t)$ tends to $B^1_t$, whereas x(t) assumes arbitrarily large drift. The effect of reflection in this case forces the process to get stuck at the boundary process, that is, $D^{(\lambda )}_t$ tends to $B^1_t$. Thus, intuitively, in either of the limiting cases, $\lambda \rightarrow 0$ or $\lambda \rightarrow \infty$, $D^{(\lambda )}_t$ is a Brownian motion.

The goal of this paper is to summarize existing results. First of all, there is Burke’s theorem, first presented in [2] for an M/M/1 queue. Second, there is the analog of this theorem for a Brownian queue. This appeared, in a more general context, in Harrison and Williams [6] and was expanded by O’Connell and Yor [10]. Instead of proving Theorem 1, we shall prove its more general version: see Corollary 1. We first review Burke’s theorem (Sect. 2), then construct the Brownian queue (Sect. 3) and finally prove the Brownian version of Burke’s theorem (Sect. 4) by reviewing the standard heavy traffic limit theorem in Theorem 3.

2 Burke’s theorem

Consider a single-server queue Q(t), $t \ge 0$, that is, define Q via the equation

(5)

where A, S are increasing counting functions with $A(0)=S(0)=0$. (By a counting function F we mean an increasing function with values in the set $\mathbb {Z}_+$ of nonnegative integers such that ${\Delta F(t) :}= F(t+)-F(t-)\in \{0,1\}$ for all t.) By convention, we let A and S be right-continuous. That the solution of (5) is unique follows easily from the fact that A and S are piecewise constant. Physically, (5) conveys the following meaning: customers arrive at the times of jumps of the function A. Assume that $Q(0)>0$. Then on some interval $[0,\tau ]$, the function Q satisfies $Q(t)=Q(0)+A(t)-S(t)$, $0 \le t \le \tau$. The time $\tau$ can be taken to be the first time at which Q becomes 0. At this time, the argument of S freezes at value $\tau$ until the first time after $\tau$ at which A has a new jump (a new customer arrives at an empty queue). Therefore, (5) is a mathematical expression of what we usually understand as a single-server queue. A G/M/1 queue is obtained when we let S be a Poisson process independent of A, both independent of Q(0). In such a case, Q is equal in distribution [3] to the process

(6)

Abusing notation, we use the same symbol, Q, for both the original process (5) and its version (6). Pathwise, Eq. (6) does not describe a queue in the usual sense but a so-called gated queue. That is, customers arrive according to A and queue up in front of a gate. At the jump times of S the gate opens instantaneously, a customer is released, and then the gate closes again immediately. Obviously, (5) and (6) describe different physical phenomena. They happen to be equal in distribution when S is an independent Poisson process. Rewriting (6) as

(7)

we see that

(8)

satisfies the following: $L(0)=0$, L is increasing, and $\int _0^\infty Q(t-) L(dt)=0$. By a version of Skorokhod’s lemma (see [4, Lemma 8.1] for the case of one-sided reflection of a continuous function and see [1, Sect. 4] for the more general cases of a two-sided reflection for a function with discontinuities of the first kind), it follows that

(9)

and so Q(t) is the reflection of $Q(0)+A(t)-S(t)$ upwards at 0; see Eq. (2). By (9) and (8), Eq. (7) is equivalently written as

$$\begin{aligned} Q(t) = \sup _{0 \le u \le t} \left( A(t)-A(u)-S(t)+S(u)\right) \vee \left( Q(0)+A(t)-S(t)\right) . \end{aligned}$$

Further manipulation of this formula shows that, for $0 \le s \le t$,

$$\begin{aligned} Q(t)= & {} \sup _{s \le u \le t} \left( A(t)-A(u)-S(t)+S(u)\right) \nonumber \\&\vee \, \left( Q(s)+A(t)-A(s)-S(t)+S(s)\right) . \end{aligned}$$

(10)

Let $F_{s,t}$ be the (random) mapping taking Q(s) into Q(t) [that is, $F_{s,t}(x)$ is obtained by letting $Q(s)=x$ in (10)]. Then the family $\{F_{s,t}: 0 \le s \le t\}$ satisfies the state transition property , for $t_1 \le t_2 \le t_3$. Moreover, the law of $F_{s,t}$ depends on s, t only through $t-s$. Since A and S have independent increments, we obtain that Q has the Markov property. Indeed, Q is a Markov chain with transition rates

$$\begin{aligned} q(n, n+1)=\lambda , \quad q(n+1, n)=\mu , \quad n \in \mathbb {Z}_+, \end{aligned}$$

(11)

whereas $q(i,j)=0$ if $i \ne j$ and $|i-j| > 1$, and $q(i,i) = -\lambda -\mu$. To “put Q in steady-state” we have two options: either do it in law or do it explicitly on some probability space. We choose the latter. To construct the probability space, extend A and S on the whole of $\mathbb {R}$. That is, take A, S be two independent stationary Poisson processes on the whole real line and ask whether there is a stationary process $(Q(t), t \in \mathbb {R})$ satisfying $Q(t)=F_{s,t}(Q(s))$ for all $s \le t$.The answer is the usual one: such a process exists if and only if $\lambda < \mu$ and is given by

$$\begin{aligned} Q(t) = \sup _{-\infty < u \le t} \left( A(t)-A(u)-S(t)+S(u)\right) . \end{aligned}$$

(12)

The ergodic theorem, together with the assumption that $\lambda < \mu$, implies that Q(t) is an a.s. finite random variable. The fact that A, S have stationary increments implies that Q is a stationary process. A little algebra shows that formula (12) satisfies (10). Hence, (12) is a stationary version of the M/M/1 queue. Put otherwise, (12) is a pathwise representation of a stationary birth and death process on the integers with transition rates (11). In fact, we also have uniqueness, i.e., Q is the unique stationary process on the probability space defined by A and S that satisfies the given dynamics. What we have done here is, of course, an application of the standard Loynes’ scheme. For this process we also have that

The point process having points at the jump times of A is the arrival process (and will still be denoted by A), whereas the point process having points at the times t such that $Q(t-)>0$ and t is a jump time of S is the departure process and will be denoted by D.

Burke’s theorem can now be stated as follows.

Theorem 2

(Burke) For the stationary M/M/1 queue Q, the following three random objects:

$$\begin{aligned} Q(0), \quad A|_{(0, \infty )}, \quad D|_{(-\infty ,0)} \end{aligned}$$

are independent. Moreover, D is a Poisson process with rate $\lambda$.

Proof

It is based on the observation that Q is time-reversible. That is, $(Q(t), t \in \mathbb {R})$ has the same finite-dimensional distributions as $(Q(-t), t \in \mathbb {R})$. (By making the latter right-continuous we can also ensure that they have the same law.) Indeed, time-reversing a stationary process possessing the Markov property gives a stationary process also possessing the Markov property with the same marginal distributions. It is more than well-known that the marginal distribution of Q(t) is geometric:

$$\begin{aligned} \mathbb {P}(Q(t)=i) = (\lambda /\mu )^i(1-\lambda /\mu ) =: \pi (i), \quad i \in \mathbb {Z}_+. \end{aligned}$$

To check this, note that

$$\begin{aligned} \pi (i) q(i,j) = \pi (j) q(j,i), \quad i \ne j, \; i,j \in \mathbb {Z}_+, \end{aligned}$$

and this implies that $\sum _{i \in \mathbb {Z}_+} \pi (i) q(i,j) = 0$, for all $j \in \mathbb {Z}_+$. It remains to check that the transition probabilities of the time-reversed process are the same as those of Q. Since transition probabilities are determined by the transition rates (we are in the best possible situation of all worlds here, since the rate matrix is bounded), we only have to check that the transition rates are the same for both processes. Fix $i,j \in \mathbb {Z}_+$, $i \ne j$. Then the transition rate for the reversed process is

$$\begin{aligned} q^{-}(i,j) = \pi (j) q(j,i)/\pi (i) = q(i,j). \end{aligned}$$

By the Markov property, we have that $A|_{(0, \infty )}$ and $D|_{(-\infty ,0)}$ are independent conditional on Q(0). By the reversibility, we have that the law of $(Q(0),D|_{(-\infty ,0)})$ is the same as the law of $(Q(0), A|_{(0, \infty )})$. Hence, in particular, $D|_{(-\infty ,0)}$ has the law of $A|_{(0, \infty )}$, and so it is a Poisson point process with rate $\lambda$. By the fact that A has independent increments, it follows that Q(0) is independent of $A|_{(0, \infty )}$. Therefore, $D|_{(-\infty ,0)}$, Q(0) and $A|_{(0, \infty )}$ are independent. Since we can replace 0 by any point of time t, it follows that $D|_{(-\infty ,t)}$ is a Poisson process with rate $\lambda$ and so D itself is Poisson with the same rate. $\square$

Usually, Burke’s theorem is stated as saying that the departure process in a stationary M/M/1 queue is Poisson with the same rate as the arrival process. However, the actual theorem says more: that past departures, future arrivals and current state are independent. This property is known as quasi-reversibility [7] and, in this case, follows from reversibility.

3 The Brownian queue

Since (12) was obtained under very minimal assumptions, we can replace the increments $A(t)-A(u)$ and $S(t)-S(u)$ by increments of very general processes X and Y, as long as we have some kinds of joint stationarity and ergodicity. For example, we can let $X^a=(X^a_t, t \in \mathbb {R})$, $Y^b=(Y^b_t, t \in \mathbb {R})$ be two independent Brownian motions with drifts a and b, respectively. As long as $a< b$, the random variable

$$\begin{aligned} {q_t :}= \sup _{-\infty < u \le t} \left( X^a_t-X^a_u-Y^b_t+Y^b_u\right) , \quad t \in \mathbb {R}, \end{aligned}$$

(13)

is a.s. finite, and the process $(q_t, t \in \mathbb {R})$ is stationary (by the stationarity of the increments of $X^a$ and $Y^b$) and Markovian; the latter follows by observing that [just as we did in (10)]

$$\begin{aligned} q_t = \sup _{s \le u \le t} \left( X^a_t-X^a_u-Y^b_t+Y^b_u\right) \vee \left( q_s+X^a_t-X^a_s-Y^b_t+Y^b_s\right) , \quad t \in \mathbb {R}, \end{aligned}$$

(14)

together with the fact that the processes $X^a$ and $Y^b$ have independent increments. (In fact, if we replace them by any processes with independent increments, we can still have the Markovian property for q, under the right stability condition, i.e., the analog of $a < b$.) We call $q_t$, $t \ge 0$, a Brownian queue with “arrival” process $X^a$ and “service” process $Y^b$. The physical meaning has been lost because (except in trivial cases) neither $X^a$ nor $Y^b$ is increasing. However, it will be regained in the next section. The point I wish to make here is this: unlike in a real queue, like the one of (5), observing the path of q cannot determine the arrival and departure processes. Indeed, if we write $X^a_t = \sigma _1 B^1_t + at$, $Y^b_t = \sigma _2 B^2_t + bt$, where $B^1$ and $B^2$ are two independent standard Brownian motions, then $X^a_t-Y^b_t \mathop {=}\limits ^\mathrm{(d)}\sqrt{\sigma _1^2+\sigma _2^2} \,B_t + (a-b)t$, where B is a standard Brownian motion, so q can, for example, be thought of having arrival process $\sqrt{\sigma _1^2+\sigma _2^2} \,B_t$ and service process $(a-b)t$.

However, when we want to talk about the “departure” process from a Brownian queue, it is important to fix the arrival process. That is, of all possibilities that result in the same q, we must pick one and call it the arrival process. For instance, let us say that $X^a$ is the arrival process. Having made our choice, we manipulate (14) further:

$$\begin{aligned} q_t&= \sup _{s \le u \le t} \big (X^a_t-X^a_u-Y^b_t+Y^b_u\big ) \vee \big (q_s+X^a_t-X^a_s-Y^b_t+Y^b_s\big )\\&= q_s+X^a_t-X^a_s-Y^b_t+Y^b_s - \inf _{s \le u \le t} \big (q_s+X^a_u-X^a_s-Y^b_u+Y^b_s\big ) \wedge 0. \end{aligned}$$

We now define $L_t$, $t\in \mathbb {R}$, by letting $L_0=0$ and

$$\begin{aligned} {L_t-L_s :}= - \inf _{s \le u \le t} \big (q_s+X^a_u-X^a_s-Y^b_u+Y^b_s\big ). \end{aligned}$$

Therefore,

$$\begin{aligned} q_t = q_s + \big (X^a_t-X^a_s\big )-\big (Y^b_t-Y^b_s\big ) + (L_t-L_s), \quad -\infty < s \le t < \infty . \end{aligned}$$

We now define the departure process by letting $D_0=0$ and

$$\begin{aligned} {D_t-D_s :}= \big (Y^b_t-L_t\big ) - \big (Y^b_s-L_s\big ), \quad -\infty < s \le t < \infty . \end{aligned}$$

Setting $s=0$ in the last expression, we have

$$\begin{aligned} D_t = Y^b_t - L_t = Y^b_t + \inf _{0 \le u \le t} \big (q_0+X^a_u-Y^b_u\big ) \wedge 0, \quad t \ge 0. \end{aligned}$$

In other words, $D_t$ is obtained by reflecting $Y^b_t$ downwards at $q_0+X^a_t$; see Eq. (3). If $t \in \mathbb {R}$, positive or negative, then

$$\begin{aligned} q_t = q_0 + X^a_t -D_t, \quad t \in \mathbb {R}, \end{aligned}$$

(15)

and so, having defined $(q_t, t \in \mathbb {R})$ through (13), the latter gives a formula for $D_t$ valid for all $t \in \mathbb {R}$, and $D_0=0$.

4 The Brownian Burke’s theorem

Consider now a sequence of stationary M/M/1 queues such that the n-th queue has Poisson service process S with rate $\mu =1$ and Poisson arrival process $A_n$ with rate ${\lambda _n:}=1-\lambda /\sqrt{n}$. We shall remind the reader how a limit is obtained. Let $Q_n(t)$, $t \in \mathbb {R}$, be the queue length process. By (12)

$$\begin{aligned} Q_n(t) = \sup _{-\infty \le u \le t}\big (A_n(t)-A_n(u)-S(t)+S(u)\big ). \end{aligned}$$

Let $D_n(t)$, $t \in \mathbb {R}$, be the departure process. That is, for all $-\infty < s \le t < \infty$,

$$\begin{aligned} D_n(t)-D_n(s)&= S(t)-S(s) - \left[ L_n(t)-L_n(s)\right] ,\\ L_n(t)-L_n(s)&= - \inf _{s \le u \le t} \big (Q_n(s) + A_n(u)-A_n(s)-S(u)+S(s)\big ) \wedge 0. \end{aligned}$$

Define

$$\begin{aligned} {\widetilde{Q_n}}(t) := & {} \frac{Q_n(nt)}{\sqrt{n}}, {\widetilde{A_n}}(t) := \frac{A_n(nt)-\lambda _n nt}{\sqrt{n}}, {\widetilde{D_n}}(t) := \frac{D_n(nt)-\lambda _n nt}{\sqrt{n}}, \quad t \in \mathbb {R}. \end{aligned}$$

Theorem 3

(Heavy traffic limit) The sequence $({\widetilde{A_n}}, {\widetilde{Q_n}}, {\widetilde{D_n}})$ converges in distribution to $(B^1, q, D^{(\lambda )})$ where $B^1$ is a standard Brownian motion, $q_t$ is a Brownian queue with arrival process $B^1$ and service process $B^2_t+\lambda t$ (with $B^2$ being an independent standard Brownian motion), and $D^{(\lambda )}$ the departure process from this Brownian queue.

Proof

By stationarity, it suffices to show that the convergence happens when we restrict all processes to any interval of the form $[s,\infty )$ and, without loss of generality, we take $s=0$. Since $\mathbb {P}(Q_n(0) \ge k) = (\lambda _n/\mu )^k$, we have $\mathbb {E}Q_n(0) = \lambda _n/(\mu -\lambda _n) = \sqrt{n}/\lambda -1$. (Recall $\mu =1$.) Since $\mathbb {E}Q_n(0)/\sqrt{n} \rightarrow 1/\lambda$, it follows that $Q_n(0)$ converges in distribution to the law of $Z/\lambda$, where Z is a rate-1 exponential random variable: For $x \ge 0$, $\mathbb {P}(Q_n(0)/\sqrt{n} > x) \rightarrow e^{-\lambda x}$, as $n \rightarrow \infty$. On the other hand, by a simple modification of Donsker’s theorem, we have that

$$\begin{aligned} \left( \frac{S(nt) - nt}{\sqrt{n}}, ~ \frac{A_n(nt) - n\lambda _{n}t}{\sqrt{n}}\right) _{t \ge 0} \; \xrightarrow {{\mathrm{(d)}}}\big (B^1, B^2\big ), \end{aligned}$$

with $B^1, B^2$ being two standard Brownian motions. Let

$$\begin{aligned} {X_n(t) :}= Q_n(0)+A_n(t)-S(t). \end{aligned}$$

Then

$$\begin{aligned} X_n(nt) = Q_n(0) + \left[ A_n(nt)-n \lambda _nt\right] - \left[ S(nt)-nt\right] - \lambda t \sqrt{n}. \end{aligned}$$

Therefore,

$$\begin{aligned} \left( \frac{X_n(nt)}{\sqrt{n}}\right) _{t\ge 0} \xrightarrow {{\mathrm{(d)}}}\left( \frac{Z}{\lambda } + B^1_t-B^2_t-\lambda t\right) _{t \ge 0}. \end{aligned}$$

However, [see (7), (8), (9)]

$$\begin{aligned} \frac{Q_n(nt)}{\sqrt{n}} = \frac{X_n(nt)}{\sqrt{n}} -\inf _{0\le u \le t} \frac{X_n(nu)}{\sqrt{n}}\wedge 0, \end{aligned}$$

and, since the mapping $\varphi : x \mapsto (\inf _{0\le u \le t} x(u) \wedge 0)_{t\ge 0}$ satisfies $\Vert \varphi (x)-\varphi (y)\Vert _T \le \Vert x-y\Vert _T$, where $\Vert f\Vert _T = \sup _{0 \le s \le t}|f(s)|$, it follows that

$$\begin{aligned}&\frac{Q_n(nt)}{\sqrt{n}} \xrightarrow {{\mathrm{(d)}}}\left( \frac{Z}{\lambda } + B^1_t-B^2_t-\lambda t\right) -\inf _{0 \le u \le t} \left( \frac{Z}{\lambda } + B^1_u-B^2_u-\lambda u\right) \wedge 0\\&\quad = \sup _{0\le u \le t}\left( B^1_t-B^1_u - \big (B^2_t-B^2_u\big ) - \lambda (t-u)\right) \vee \left( \frac{Z}{\lambda } + B^1_t-B^2_t-\lambda t\right) , \end{aligned}$$

where $\xrightarrow {{\mathrm{(d)}}}$ means convergence in distribution when both sides are interpreted as processes. Now let $q_t$ be defined by

$$\begin{aligned} q_t = \sup _{0 \le u \le t} \big (X_t-X_u-Y_t+Y_u\big ) \vee \big (q_0+X_t-X_s-Y_t+Y_s\big ), \end{aligned}$$

with $X_t=B^1_t$ and $Y_t = B^2_t+\lambda t$; see (14), and $q_0=Z/\lambda$. Since each of the M/M/1 queues is stationary, it follows that $q_t$ is stationary (its law is invariant under forward shifts). This means that the unique extension of $q_t$, $t \ge 0$, to $q_t$, $t \in \mathbb {R}$, is the stationary process defined by

$$\begin{aligned} q_t = \sup _{-\infty < u \le t} \big (X_t-X_u-Y_t+Y_u\big ). \end{aligned}$$

Consider now the departure process of the n-th queueing system. We have

$$\begin{aligned} {\widetilde{D_n}}(t)= & {} \frac{D_n(nt)- n\lambda _n t }{\sqrt{n}} = \frac{S(nt)-nt}{\sqrt{n}} + \lambda t + \inf _{0\le u \le t} \frac{X_n(nu)}{\sqrt{n}}\\&\xrightarrow {{\mathrm{(d)}}}B^2_t +\lambda t + \inf _{0\le u \le t} \left( \frac{Z}{\lambda } + B^1_u-B^2_u-\lambda u\right) =: D^{(\lambda )}_t, \end{aligned}$$

where $D^{(\lambda )}_t$ is the departure process from the Brownian queue. We have proved that each entry of the triple $({\widetilde{A_n}}, {\widetilde{Q_n}}, {\widetilde{D_n}})$ converges in distribution to the corresponding entry of the triple $(B^1, q, D^{(\lambda )})$. However, going back to the arguments, we have actually shown that the triple converges jointly. Moreover, by stationarity, we have shown that the convergence is actually on the whole of $\mathbb {R}$. $\square$

Corollary 1

(Brownian Burke’s theorem) Let $q_t$ be the stationary Brownian queue with arrival process $B^1_t$ and service process $B^2_t+\lambda t$, for some $\lambda > 0$. That is,

$$\begin{aligned} q_t = \sup _{-\infty < u \le t} \left( B^1_t-B^1_u -\big (B^2_t-B^2_u\big )-\lambda (t-u)\right) , \quad t \in \mathbb {R}. \end{aligned}$$

Let $(D^{(\lambda )}_t, t \in \mathbb {R})$ be its departure process. That is,

$$\begin{aligned} D^{(\lambda )}_t - D^{(\lambda )}_s= & {} B^2_t-B^2_s + \lambda (t-s) +\inf _{s\le u \le t} \big (q_s + B^1_u-B^1_s \\&-\big (B^2_u-B^2_s\big )-\lambda (u-s)\big )\wedge 0. \end{aligned}$$

Then

$$\begin{aligned} q_0, \quad \big (B^1_t, t \ge 0\big ), \quad \big (D^{(\lambda )}_t, t < 0\big ) \end{aligned}$$

are independent. Moreover, $q_0$ is exponential with rate $\lambda$ and $(D^{(\lambda )}_t, t \in \mathbb {R})$ is a standard two-sided Brownian motion.

Proof

Consider the n-th M/M/1 queue defined earlier. By Burke’s theorem (Theorem 2) $n^{-1/2}Q_n(0)$, $({\widetilde{A_n}}(t), t \ge 0)$, $({\widetilde{D_n}}(t), t \le 0)$ are independent. By Theorem 3, the triple converges in distribution to $Z/\lambda$, $(B^1_t, t \ge 0)$, $(D^{(\lambda )}_t, t < 0)$. Since independence is preserved in the limit, it follows that the $Z/\lambda$, $(B^1_t, t \ge 0)$, $(D^{(\lambda )}_t, t \le 0)$ are independent. By the last assertion of Burke’s theorem, $D_n$ is a stationary Poisson process with rate $\lambda _n=1-\lambda /\sqrt{n}$. By Donsker’s theorem, ${\widetilde{D_n}}$ converges in distribution to a standard two-sided Brownian motion. By Theorem 3 again, ${\widetilde{D_n}}$ converges in distribution to $D^{(\lambda )}$. Therefore, $D^{(\lambda )}$ is a standard two-sided Brownian motion. $\square$

We have actually proved Theorem 1 as well. Namely, the process (1) is a standard Brownian motion regardless of the value $\lambda$, including the cases $\lambda =0$ and $\lambda =+\infty$.

Caveat By scaling, we can replace $B^1$, $B^2$ by zero-mean independent Brownian motions with the same variance. However, we may not pick different variances. That is,

$$\begin{aligned} {w(t):}=\inf _{0 \le s \le t} \left\{ \frac{1}{\lambda } Z + \sigma _1 B^1_s + \sigma _2 B^2_t-\sigma _2 B^2_s + \lambda (t-s) \right\} \wedge \left( \sigma _2 B^2_t+\lambda t\right) , \quad t \ge 0, \end{aligned}$$

is not a Brownian motion if $\sigma _1 \ne \sigma _2$. For some intuition, suppose $\sigma _2^2 \gg \sigma _1^2$. Recall that w(t) is the reflection of $x(t) = \sigma _2 B_t^2 + \lambda t$ downwards at ${\beta (t):}= (1/Z) + \sigma _1 B^1_t$. When w(t) is close to $\beta (t)$, the increments will tend to have smaller variance than when it is far away, thus violating the fact that a standard Brownian motion has homoscedastic increments.

Note The formula

$$\begin{aligned} D^{(\lambda )}_t = B^2_t+\lambda t + \inf _{-\infty < u \le t} \big (B^1_u-B^2_u-\lambda u\big ) - \inf _{-\infty < u \le 0} \big (B^1_u-B^2_u-\lambda u\big ), \quad t \in \mathbb {R}, \end{aligned}$$

also holds and is a two-sided standard Brownian motion for any $\lambda \ge 0$. To see this, use (15) and (13).

5 Further comments

The idea of quasireversibility, explored in the classic work by Kelly [7], tells us how to “connect” stable Markovian quasireversible queues (or, more generally, positive recurrent quasireversible Markov chains) in order to obtain a bigger system that has a simple stationary distribution. This was a topic of intense research in the past. (See Walrand [11].) Appropriately connecting quasireversible Brownian queues leads to a network with product form distribution. One possible way to do this is by connecting the queues in tandem. That the stationary distribution is product form here is a simple consequence of Corollary 1. In fact, López [9] shows the following: Assume that the input to the overall system is a fairly arbitrary stochastic process and that all service processes are independent Brownian motions with the same positive drift. Then the output from n queues converges in distribution to a Brownian motion, as $n \rightarrow \infty$. For a necessary and sufficient condition so that the stationary distribution of a general network of Brownian queues is of product form, see [5]. For failure of product form when Brownian motions are replaced by Lévy processes, see [8]. However, neither of the last two papers actually uses quasireversibility in order to prove their results.