\documentstyle[12pt]{article}
\scrollmode
\begin{document}
\baselineskip=24pt
\title{The net output process of a system with infinitely many queues}
\author{{P.A. Ferrari \hspace{10 mm} L. R. G. Fontes}\\
Instituto de Matem\' atica e Estat\'\i stica,
USP }
\maketitle
\begin{abstract}
We study a system of infinitely many queues with Poisson arrivals and
exponential service times. Let the net output process be the difference
between the departure process and the arrival process. We impose certain
ergodicicity conditions on the underlying Markov chain governing the customer
path. These conditions imply the existence of an invariant measure under which
the average net output process is positive and proportional to the time.
Starting the system with that measure we
prove that the net output process is a Poisson
process plus a perturbation of order 1. This generalizes a classical theorem
(Burke (1956), Kelly (1979)) asserting that the departure process is a Poisson
process.
\end{abstract}
\newtheorem{teo}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{rem}{Remark}
\newtheorem{prop}{Proposition}
\renewcommand{\a}{\alpha}
\renewcommand{\b}{\beta}
\renewcommand{\O}{\Omega}
\newcommand{\e}{\eta}
\newcommand{\et}{\eta_t}
\newcommand{\est}{\eta^\ast_t}
\newcommand{\ex}{\eta^{xy}}
\newcommand{\n}{{I\kern-0.3emN}}
\newcommand{\z}{{Z\kern-0.45emZ}}
\renewcommand{\L}{{\bf L}}
\newcommand{\ls}{{\bf L}^\ast_2}
\newcommand{\nur}{\nu_{\rho}}
\newcommand{\nut}{\nu_2}
\newcommand{\si}{\sigma}
\newcommand{\sit}{\si_t}
\newcommand{\siz}{\si_0}
\newcommand{\six}{\si^{xy}}
\newcommand{\siy}{\si^{yx}}
\renewcommand{\ss}{\si^\ast}
\newcommand{\sst}{\ss_t}
\newcommand{\ssz}{\ss_0}
\newcommand{\abst}{|\sst|}
\newcommand{\asz}{|\ss_0|}
\newcommand{\xit}{\xi_t}
\newcommand{\xiz}{\xi_0}
\newcommand{\xix}{\xi^{xy}}
\newcommand{\xiy}{\xi^{yx}}
\newcommand{\xs}{\xi^\ast}
\newcommand{\xst}{\xs_t}
\newcommand{\xsz}{\xs_0}
\newcommand{\p}{p^\ast}
\newcommand{\ps}{p^*_b}
\newcommand{\px}{p^*_r}
\newcommand{\mus}{\mu^\ast}
\newcommand{\Xst}{X^\ast_t}
\newcommand{\fsx}{\frac{\si(x)}{\si(x)+\xi(x)}}
\newcommand{\fsy}{\frac{\si(y)}{\si(y)+\xi(y)}}
\newcommand{\fxx}{\frac{\xi(x)}{\si(x)+\xi(x)}}
\newcommand{\fxy}{\frac{\xi(y)}{\si(y)+\xi(y)}}
\newcommand{\fsu}{\frac{\si(-1)}{\si(-1)+\xi(-1)}}
\newcommand{\fxu}{\frac{\xi(-1)}{\si(-1)+\xi(-1)}}
\newcommand{\black}{$\mbox{\rm black}^\ast\,$}
\newcommand{\red}{$\mbox{\rm red}^\ast\,$}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\beqn}{\begin{eqnarray}}
\newcommand{\eeqn}{\end{eqnarray}}
\newcommand{\beqnn}{\begin{eqnarray*}}
\newcommand{\eeqnn}{\end{eqnarray*}}
\vskip 3truemm
\noindent {\it Keywords and phrases.}
Queuing networks. Zero range process. Burke's theorem. Departure process. Net
output process.
\vskip 2truemm \noindent {\it AMS-MOS 1991 Classification.} 60K35, 60K25, 90B22,
90B15.
\vskip 2truemm \noindent {\it Running head.}
Ouput of infinitely many queues.
\vskip 3truemm
\noindent {\bf 1. Introduction.} We consider a system of infinitely many queues
with arrivals and departures. To describe it let $S=\{-1,0,1,\ldots\}$ and
$p(x,y)$ be the transition rates of a continuous time Markov chain on $S$.
Consider that at each $x\ge 0$ there is a queue formed by a nonnegative number
of indistinguishable customers. If this number is positive, we can think that
one of the customers is being served and the others are waiting for service.
The service time of queue $x \ge 0$ is exponential with rate $\mu(x) = \sum_y
p(x,y)$. Once the customer is served it jumps to queue $y$ with probability
$p(x,y)/\mu(x)$. ``Queue'' $-1$ is out of the system and it is considered as
a queue for notational convenience. We assume that there are infinitely many
customers at $-1$ at all times. This implies that customers are entering from
the outside of the system to queue $y\ge 0$ according to a Poisson process of
rate $p(-1,y)$. This system is a particular case of the called zero range
process with an external source/sink of customers. Under suitable conditions
on the rates $p(x,y)$ ((\ref{eq:ex}) below) it can be shown that the process is well
defined, at least for a class of initial configurations. The techniques of
Andjel (1982) are appropriate to show existence under this condition. We call
$\eta_t$ the resulting process in $\n^\n$ where for $x\ge 0$, $\eta_t(x)$ is
the number of customers at queue $x$ by time $t$.
We are interested in the case when in average there is a positive net flux of
customers out of the system. In order to guarantee this we ask
the transition matrix $p(x,y)$ to satisfy some conditions. One of them is ergodicity. In
other words, we ask ---in (\ref{eq:m}) below---
the transition matrix $p(x,y)$ to accept a unique finite
invariant measure $m$ on $S$ satisfying $m(-1)=1$.
Furthermore we ask $1>m(x)$ for all $x\ge 0$. We also assume that there exists
a sigma finite measure $\rho$ on $S$ satisfying
$$
\rho(y) = \sum_{x\ge -1} \rho(x) p(x,y),\ \ y\ge 0,\ \ \ \ \ \rho(-1)=1
$$
such that $1>\rho(x) > m(x)$, $x\ge 0$.
Let $\nur$ be the product measure on $\Omega$ whose marginals are geometric with
parameter $\rho(x)$. In other words, for any finite set $A\subset {\n}$,
\beqn
\label{eq:nur}
\nur (\eta(x) = k_x, x\in A) = \prod_{x\in A} \rho(x)^{k_x} (1-\rho(x))
\eeqn
If $\rho$ satisfies the conditions above then $\nur$ is invariant for the
system, as a consequence of Proposition 1 below. This was proven by Jackson
(1963) for finite
networks, by Andjel (1982) for infinite conservative systems
and by Ferrari (1986) for a special case of $p(x,y)$ satisfying our conditions.
We assume other mild conditions on the functions $p(x,y)$, $m(x)$ and
$\rho(x)$ stated in (\ref{eq:mx}) and (\ref{eq:ex1}) below. Let the departure
process $D_t$ be the number of customers leaving the system in $[0,t]$ and the
arrival process $A_t$ be the number of customers entering the system in
$[0,t]$. The departure (respectively arrival) process at time $t$ counts the
number of customers jumping to (respectively from) $-1$ in the interval
$[0,t]$. Let the net output process be $X_t = D_t - A_t$. Burke (1956) showed
that for one queue in equilibrium with Poisson arrivals and exponential
service times, the departure process $D_t$ is a Poisson process. This result
was extended to systems with a finite number of queues, see Kelly (1979) and
references therein. The extension to infinitely many queues is immediate:
\begin{teo} Let $p(x,y)$ be the transition rates of a continuous Markov chain
on $S$ satisfying (\ref{eq:ex}) to (\ref{eq:ro}) of next section. Let
$\eta_t$ be a system of queues with rates $p(x,y)$ whose generator is given by
(\ref{eq:L}). Assume that the initial distribution $\nur$ is given by
(\ref{eq:nur}). Then the departure process $D_t$ is a Poisson process of
parameter $\sum_{x\ge 0} \rho(x) p(x,-1)$.
\end{teo}
To prove Theorem 1 one follows Kelly's (1979) idea: construct $\eta^*_t$, the
reverse process of $\eta_t$ with respect to the invariant measure $\nur$ and
verify that in distribution $D_t=A^*_t$, the number of customers entering the
reverse process. By construction $A^*_t$ is a Poisson process with rate
$\sum_{x\ge 0}\rho(x) p(x,-1)$.
If $p(-1,x) \equiv 0$, then $X_t = D_t$ is a Poisson process. When $p(-1,y)$
is not identically zero, customers enter into the system producing memory
which prevent $X_t$ from being a Poisson process. We then have the following
theorem, which is our main result.
\begin{teo} Let $p(x,y)$ be the transition rates of a continuous Markov chain on
$S$ satisfying conditions (\ref{eq:ex}) to (\ref{eq:ex1}) of next section.
Let $\eta_t$ be the system of infinitely many queues on ${\n}^{\n}$ with rates
$p(x,y)$, whose generator is given by (\ref{eq:L}) of next section.
Assume that the initial distribution of $\eta_t$ is the invariant
measure $\nur$ defined in (\ref{eq:nur}). Then
the net output process
$X_t$ can be expressed as the following sum
\beq
X_t=R_t+B_t,
\eeq
where $R_t$ is a Poisson process with rate
\beq
\label{eq:rate}
\sum_{x\ge 0}[\rho(x)-m(x)]p(x,-1)
\eeq
and $B_t$ is a mean zero process such that the distribution
of $|B_t|$ decays exponentially, uniformly in $t$, that is,
there are positive constants $C$ and $\b$ such that
\beq
P(|B_t|>x)\leq Ce^{-\b x},\ x,t\geq0.
\eeq
\end{teo}
This result is not trivial only for systems with infinitely many queues. For
finite systems there is only one invariant measure and one writes $D_t - A_t =
\vert \eta_0 \vert - \vert \eta_t \vert$, where $\vert \eta_t \vert$ is the
total number of customers in the system by time $t$, which is of order $1$ as
in equilibrium $\eta_t$ has the same distribution as $\eta_0$. In this case
$R_t$ is the trivial Poisson process of rate $0$ and $B_t = \vert \eta_0 \vert
- \vert \eta_t \vert$.
We sketch now the proof of Theorem 2 in which we also
use the reverse process but in a somewhat more subtle way.
The main point
is to distinguish between two type of customers: those that enter the system
from $-1$ that we call black customers and the others that we call red
customers. We can think that the red customers come from ``infinity''.
The motion of this two species system is based on the assumption
that black and red customers behave in the same way in the queues $x\ge 0$. When the
server at queue $x$ finishes a service ---this happens at rate $\mu(x)$--- it chooses
uniformly one customer among the ones in its queue. Hence the probability of
choosing a black one is the quocient between the number of black customers
and the total number of customers in that queue. Then this customer
jumps to queue $y$ with probability $p(x,y)/\mu(x)$. The only difference
between black and red customers
occurs at the boundary: only black customers enter into the system from $-1$ and
they do so to queue $y$ at rate $p(-1,y)$. We call $(\si_t,\xi_t)$ the
resulting system, where $\si_t(x)$ (respectively $\xi_t(x)$) is the number of
black (respectively red) customers at queue $x$ by time $t$. The net ouput
processes of black and red customers are denoted $B_t$ and $R_t$
respectively. By construction
$\eta_t = \si_t + \xi_t$ coordinatewise and $X_t = B_t + R_t$.
This means that if we disregard colors
we recover the original system $\eta_t$.
Next step is to find the invariant measure $\nu_2$ for $(\si_t,\xi_t)$ and the
reverse process $(\si_t,\xi_t)^* = (\si^*_t,\xi^*_t)$ with respect to $\nu_2$.
We simply exibit them and show the assertion.
Call $R^*_t$ (respectively $B^*_t$), the net input process of red (respectively
black) customers into the reverse system. In the reverse process the
red customers do not leave the system and $R^*_t$ is a Poisson process. On
the other hand, by mass conservation $B^*_t$ is equal to $\vert\si_0\vert -
\vert\si_t\vert$, that has the required properties under our hypothesis. To
conclude the proof of Theorem 2 we use the same idea of the proof of Theorem
1. By reversing the process $B_t = B^*_t$ and $R_t = R^*_t$ in distribution.
The proof is quite straigthforward but the path we followed to guess the
invariant measure and the reverse process for the two species system was not
so direct. We explain briefly our reasoning now. Following De Masi et al.\/ (1988)
one guess $\eta^*_t$, the reverse process of $\eta_t$ with respect to $\nur$.
This turns out to be a system with infinitely many queues as $\eta_t$ but with
transition rates given by
$$
\p (x,y)=\frac{p(y,x)\rho(y)}{\rho(x)}
$$
(and service rates $\mu^*(x) = \sum_y \p(x,y) = \mu(x)$).
Since $p(x,y)$ accepts a finite invariant
measure, each customer of $\eta_t$ has a drift towards $-1$ and once it arrives to $-1$ we
can think that it will stay there. Hence in the original process $\eta_t$
there is a general flux of customers from infinity to the exit at $-1$. This
implies that in the reverse process $\eta^*_t$, there is a flux of customers
from $-1$ to infinity. But a fraction of these customers fail to go to
infinity and come back to $-1$. One can construct the reverse process by
labeling the customers and keeping track of each customer. Take the labeled
reverse process and make a partition of the trajectory space by specifying
which are the customers that will eventually leave the system by $-1$. These are called
\black customers and the remained customers are called \red. The customers entering
after time zero are specified according to the queue they arrive. If the
probability that a customer at queue $x$ be specified \black is given by
$m(x)/\rho(x)$, the
probability that a chain on $S$ with rates $\p(x,y)$ starting at $x$ hits eventually
$-1$, then the process conditioned in this way to the future is still
Markovian. The transition rates for \black and \red customers are
different and given by the corresponding conditioned chains defined in
(\ref{eq:13}) below.
>From this observation one construct the invariant measure
for $(\si^*_t,\xi^*_t)$ by choosing a $\eta^*$ according to $\nur$ and then
labeling each customer at $x$ independently as black with probability
$m(x)/\rho(x)$ and red with probability $1-m(x)/\rho(x)$. Call the resulting
measure $\nut$. When one looks for
the reverse process of $(\si^*_t,\xi^*_t)$ with respect to $\nut$, one finds
$(\si_t,\xi_t)$. Since the \black
and \red transition rates are different,
the process $\si^*_t+\xi^*_t$ is not Markovian, so it can not be the same as
$\eta^*_t$. Nevertheless it is true that the law of $\si^*_t +
\xi^*_t$ starting with $\nut$ is the same as the law of $\eta^*_t$ starting
with $\nur$.
In Section 2 we state the assumptions needed to show Theorem 2 and define the
process. In Section 3 we introduce the two species process and show Theorem 2.
In Section 4 we give some concluding remarks and extensions.
\vskip 3truemm
\noindent {\bf 2. A system of infinitely many queues.}
\vskip 2truemm
Let $p(x,y)$ be the transition rates of a (continuous time)
Markov chain in the state space $S=\{-1,0,1,\ldots\}$
satisfying
\begin{enumerate}
\item Bounded total rates.
\beq \label{eq:ex}\sup_y\sum_xp(x,y)<\infty,\; \sup_y\sum_xp(y,x)<\infty;
\eeq
\item The chain is ergodic and the invariant measure of $-1$ is strictly
bigger than the measure of any other $x\ge 0$. In other words, the chain
has a unique invariant
finite measure $m$ such that
\beqn
\label{eq:m}
m(y) = \sum_{x\ge -1} m(x) p(x,y),\ \ y\ge -1,\ \ m(-1)=1> m(x),\ x\ge 0.
\eeqn
%\item $m(x)<1,\ x\geq0;$
\item There is a measure $\rho$ such that
\beqn
\label{eq:ro}
&\rho(x)\mu(x)=\sum_y\rho(y)p(y,x),\ x\geq 0,\\
\nonumber
&\rho(-1)=1>\rho(x)>m(x),\ x\geq0,
\eeqn
where $\mu(x)=\sum_yp(x,y)$;
\item The measures $m$ and $\rho$ satisfy
\beq
\label{eq:mx}
\sum_{x\ge 0} \frac{m(x)}{1-\rho(x)+m(x)}<\infty;
\eeq
\item we further require
\beqn
\nonumber&\sup_y\, m(y)\sum_xp(y,x)/{m(x)}<\infty,\\
\label{eq:ex1}&\,\sup_y (\rho(y)-m(y))\sum_xp(y,x)/{(\rho(x)-m(x))}<\infty.
\eeqn
\end{enumerate}
\noindent {\bf Remark.} We see below that
Condition (\ref{eq:ex}) is sufficient to show the existence of the process.
Condition (\ref{eq:m}) is necessary in order to have an invariant measure concentrating
mass on configurations with a finite number of customers with probability one. Condition
(\ref{eq:ro}) guarantees the existence of an invariant measure with infinitely many
customers. Condition (\ref{eq:mx}) is necessary and
sufficient to get the exponential moment of $B_t$.
Condition (\ref{eq:ex1}) is sufficient for the existence of the reverse
process mentioned in the introduction. It is automatically
satisfied if $p(x,y)$ is of finite range.
Let $(\et)_{t\geq0}$ be the infinite system of queues indexed
by $\n=\{0,1,\ldots\}$ with servicing rates $\mu(x)$ and transition rates
$p(x,y)$ given above. The state $-1$ is regarded as
out of the system, from where and to where customers enter
and exit the system.
The process $\et$ counts the number of customers at each queue
at time $t$. It takes values in $\O={\n}^{\n}$ and its generator is
given by
\beqn
\label{eq:L}
\L f(\e)=\sum_{x,y\geq-1}1\{\e(x)>0\}p(x,y)[f(\ex)-f(\e)],
\eeqn
where $\e$ is the initial state of the system ($\e(-1)$ is
defined as $+\infty$), $\ex$ is defined by
$$
\ex(z)=\cases{\e(z),& if $z\ne x,y$\cr
\e(x)-1,& if $z=x$\cr
\e(y)+1,& if $z=y$,\cr}
$$
and $f$ is a local function in $\O$. Condition (\ref{eq:ex}) insures
the existence of this process. This can be
proven as Andjel (1982) does for an infinite system which conserves the number
of customers.
Since the customers are indistinguishable,
we can assume the following rule for each queue. After a service period is
finished, the server chooses the customer that has been served uniformly among
the ones in his queue by that time.
\vskip 5truemm
\noindent {\bf 2. The two species system.}
For the proof of Theorem 1 we introduce the process $(\sit,\xit)\in \O_2 = \O\times\O$
as follows. At each queue we have two types of customers: black and red.
The number of black (respectively red)
customers at queue $x$ at time $t$ is $\si_t(x)$ (respectively $\xi_t(x)$).
Let the system evolve with the provision that only black customers
enter it and they do so at site $y$ with rate $p(-1,y)$. The evolution in the
system is the following. Given that a service time finished at queue $x$, the
probability that a black customer has been served is the number of black customers in
$x$ over the total number of customers in $x$. The service corresponds to a red customer
with the complementar probability. Then the chosen customer jumps to queue $y$
with probability $p(x,y)/\mu(x)$. Notice that this specification implies that
our system is not a classical system of queues with two types of customers. In
a classical system the customer is chosen according to some rule (that may be
random as our rule) at the beginning of the service time interval. In our system the
customer is chosen at the end of this interval. In this way a customer that
has arrived
after the starting of the service time interval can be the one served by the
end of the interval. The generator of this process is given by
\beqnn
\L_2f(\si,\xi)=\sum_{x,y\geq-1}p(x,y)&\!\left\{\frac{\si(x)}
{\si(x)+\xi(x)}[f(\six,\xi)-f(\si,\xi)]\right.\\
+&\!\left.\frac{\xi(x)}{\si(x)+\xi(x)}[f(\si,\xix)-f(\si,\xi)]\right\},
\eeqnn
where $(\si,\xi)$ is the initial state of the system (with
$\si(-1)=+\infty$ and $\xi(-1)=0$), $\six$ and $\xix$ are defined
analogously as $\ex$ with the exception $\xi^{x,-1}(-1) \equiv 0$.
$f$ is a local function in $\O_2$ and we adopt
the convention that $\infty/\infty=1$ and $0/0=0$.
Then we have the following lemma whose proof is
straightforward.
\begin{lemma}
Let the process $(\sit,\xit)$ have initial configuration $(\si,\xi)$. Then
$\sit+\xit$ has the same distribution as $\eta_t$ with initial configuration
$\si+\xi$. In other words, if $f$ is a local function defined on $\O$, then
$L_2f(\si+\xi) = Lf(\si+\xi)$.
\end{lemma}
Define a measure $\nut$ on $\O_2$ as follows. Let $\eta$ be chosen
from $\nur$.
Let $\a(x)=m(x)/\rho(x)$. It is easy to check that $\a(x)$ is the probability
that a Markov chain on $S$ with transition rates $p^*(x,y)$ hits eventually
$-1$. For all $x\geq 0$, each $\eta$ customer in queue
$x$ will be
called black, with probability $\a(x)$ or red, with probability
$1-\a(x)$, independently of each other and of other queues. We call $\nut$ the
resulting measure. From Lemma 1 and the construction of $\nut$ we have
\beqn
\label{eq:nu}
\int d\nut(\si,\xi) L_2 f(\si+\xi) = \int d\nur(\eta) Lf(\eta)
\eeqn
Define new Markov transition rates $\p (x,y)$ on $S$ as follows
\beq
\p (x,y)=\frac{p(y,x)\rho(y)}{\rho(x)}
\eeq
and a new system of queues $\est$ in $\O$ with transition rates
$\p(x,y)$ and service rates
$\mus(x)=\sum_y\p(x,y).$ (Notice that $\mus(x)=\mu(x),\ x\in\n$.)
Like in the system $\et$, we distinguish between two kinds of customers
in this new system, which we call \black and \red. Consider the Markov
rates defined on $S$ as
\beqn
\nonumber
\ps(x,y)=\p(x,y)\a(y)/\a(x),\\
\px(x,y)=\p(x,y)(1-\a(y))/(1-\a(x)),\label{eq:13}\\
\nonumber\px(-1,y)=\p(-1,y)(1-\a(y)).
\eeqn
If we consider a Markov chain on $S$ with transition rates $p^*$ and condition
it to be eventually absorved at $-1$ we get a new Markov chain with transition
rates given by $p^*_b$. If we condition to non absorption we get rates $p^*_r$.
Notice that $\sum_y\ps(x,y)=\sum_y\px(x,y)= \mu^*(x)=\mu(x)$.
We define now a process $(\sst,\xst)$ with the
following evolution. At rate $\mus(x)$, a customer is selected in
queue $x$ uniformly among the $\sst(x)+\xst(x)$ customers. If it is a \black one,
then the customer jumps to $y$ with probability $\ps(x,y)/\mus(x)$ and if it is a \red
one, then the same jump is with probability $\px(x,y)/\mus(x)$. The \black
customers enter the system to queue $y$ at rate $\ps(-1,y)$
and \red ones do it at rate $\px(-1,y)$.
Let $\sst(x)$ and $\xst(x)$ respectively count the number of \black and \red
customers in queue $x$ at time $t$. Then, $(\sst,\xst)$ takes values in
$\O_2$ and has the following generator.
\beqnn
\ls f(\si,\xi)=\sum_{x,y\geq-1}&\!\!\left\{\ps(x,y)\fsx[f(\six,\xi)-f(\si,\xi)]
\right.\\
+&\left.\px(x,y)\fxx[f(\si,\xix)-f(\si,\xi)]\right\},
\eeqnn
where $\fsu=\fxu=1$. Condition (\ref{eq:ex1}) insures the existence of this process.
Here is the main ingredient in the proof of Theorem 1.
\begin{prop}
The processes $(\sit,\xit)$ and $(\sst,\xst)$ are the reverse of
one another with respect to $\nut$.
\end{prop}
\noindent{\bf Proof of Theorem 1:} From Proposition 1 and (\ref{eq:nu}) it
follows that $\nur$ is invariant for
the process $\eta_t$. From Lemma 1, we have $\et=\sit+\xit$ and
\beq
X_t = B_t + R_t
\eeq
where $B_t$ and $R_t$ are the net output process of black and red
customers of the process $(\si_t,\xi_t)$ under initial distribution $\nut$.
Proposition 1 implies
\beq
B_t= B_t^*,\ \ \ R_t= R_t^*
\eeq
in distribution, where $B^*_t$ (respectively $R_t^*$)
is the net input process of \black\/ (respectively \red) customers for the reverse
system. Since \red\/ customers do not leave the system,
$R_t^*$ is a Poisson process of rate given by (\ref{eq:rate}). On the
other hand
$$
B_t^*=\abst-\asz,
$$
which has mean zero since $\sst$ and $\ssz$ have
the same distribution. This and the exponential decay of $\asz$ completes
the proof, the decay being the consequence of the fact that $\asz$
is the series of independent geometric random variables with summable
parameters (it is here that (\ref{eq:mx}) enters).
\noindent{\bf Proof of Proposition 1:}
We want to show that
\beq
\label{eq:rev}
\int f\L_2gd\nut=\int g\ls f d\nut,
\eeq
for local functions $f$ and $g$ on $\O_2$. The above equality will be established
if we prove the following equalities
\beqn
\nonumber
&p(x,y)\displaystyle{\int\fsx} f(\six,\xi)g(\si,\xi)d\nut(\si,\xi)\\
\label{eq:si}
&=\ps(y,x)\displaystyle{\int\fsy} f(\si,\xi)g(\siy,\xi)d\nut(\si,\xi)
\eeqn
and
\beqn
\nonumber
&p(x,y)\displaystyle{\int\fsx} f(\si,\xix)g(\si,\xi)d\nut(\si,\xi)\\
\label{eq:xi}
&=\px(y,x)\displaystyle{\int\fsy} f(\si,\xi)g(\si,\xiy)d\nut(\si,\xi),
\eeqn
for $x,y\in S$ and
\beqn
\nonumber
&\sum_{x,y}p(x,y)\displaystyle{\int1}\{\si(x)+\xi(x)>0\}f(\si,\xi)g(\si,\xi)d\nut(\si,\xi)\\
\nonumber
&=\sum_{x,y}\ps(x,y)\displaystyle{\int\fsx} f(\si,\xi)g(\si,\xi)d\nut(\si,\xi)\\
\label{eq:sum}
&+\sum_{x,y}\px(x,y)\displaystyle{\int\fxx} f(\si,\xi)g(\si,\xi)d\nut(\si,\xi),
\eeqn
where the above sums are done in the set
$\{x,y: x \ \mbox{\rm or}\ y\in[-1,\ldots,N]\}$, where $N$ is big
enough so that $[0,N]$ contains the supports of $f$ and $g$.
To prove (\ref{eq:si}) and (\ref{eq:xi}), we can take $f,\ g$
of the type
$$\prod_{v\in A}1\{\si(v)=k_v\}\prod_{w\in B}1\{\xi(w)=l_w\},$$
where $A$ and $B$ are arbitrary finite subsets of $\n$ and $k_v$
and $l_w$ are arbitrary nonnegative integers.
Since $\nut$ is a product measure, it is then sufficient to consider the cases
\beqnn
&f(\si,\xi)=1\{\si(x)=k_x+1,\si(y)=k_y,\xi(x)=l_x,\xi(y)=l_y\}\\
&g(\si,\xi)=1\{\si(x)=k_x,\si(y)=k_y+1,\xi(x)=l_x,\xi(y)=l_y\}
\eeqnn
and
\beqnn
&f(\si,\xi)=1\{\si(x)=k_x,\si(y)=k_y,\xi(x)=l_x+1,\xi(y)=l_y\}\\
&g(\si,\xi)=1\{\si(x)=k_x,\si(y)=k_y,\xi(x)=l_x,\xi(y)=l_y+1\}
\eeqnn
respectively for (\ref{eq:si}) and (\ref{eq:xi}), when $x,y\in\n$.
When $y=-1$, take
\beqnn
&f(\si,\xi)=1\{\si(x)=k_x+1,\xi(x)=l_x\}\\
&g(\si,\xi)=1\{\si(x)=k_x,\xi(x)=l_x\}
\eeqnn
and
\beqnn
&f(\si,\xi)=1\{\si(x)=k_x,\xi(x)=l_x+1\}\\
&g(\si,\xi)=1\{\si(x)=k_x,\xi(x)=l_x\}
\eeqnn
respectively for (\ref{eq:si}) and (\ref{eq:xi}).
When $x=-1$, (\ref{eq:xi}) is trivially satisfied (both sides vanish), for (\ref{eq:si})
one should take
\beqnn
&f(\si,\xi)=1\{\si(y)=k_y,\xi(y)=l_y\}\\
&g(\si,\xi)=1\{\si(y)=k_y+1,\xi(y)=l_y\}.
\eeqnn
For all these cases, it is a simple calculation to verify
(\ref{eq:si}) and (\ref{eq:xi}).
The equality (\ref{eq:sum}) is easily verified for the sums taken in
the set $\{0\leq x\leq N,\ y\geq-1\}$ from the equalities
$$
\sum_yp(x,y)=\sum_y\ps(x,y)=\sum_y\px(x,y),\ x\geq0.
$$
So it suffices to show that
\beqn
\nonumber
&\displaystyle{\int} f(\si,\xi)g(\si,\xi)\sum_yp(-1,y) d\nut(\si,\xi)\\
&+\sum_{x>N}\sum_{y\leq N}p(x,y)
\displaystyle{\int} 1\{\si(x)+\xi(x)>0\}f(\si,\xi)g(\si,\xi)d\nut(\si,\xi)\\
\nonumber
&=\displaystyle{\int} fg\sum_y\ps(-1,y)d\nut+\displaystyle{\int} fg\sum_y\px(-1,y)d\nut\\
\nonumber
&+\sum_{x>N}\sum_{y\leq N}\ps(x,y)
\displaystyle{\int\fsx}f(\si,\xi)g(\si,\xi)d\nut(\si,\xi)\\
\label{eq:sumu}
&+\sum_{x>N}\sum_{y\leq N}\px(x,y)
\displaystyle{\int\fxx} f(\si,\xi)g(\si,\xi)d\nut(\si,\xi).
\eeqn
The second term in the l.h.s. and the third and fourth terms
in the r.h.s. equal respectively
\beqnn
&\displaystyle{\int} fg\sum_{x>N}\sum_{y\leq N}\rho(x)p(x,y)d\nut,\\
&\displaystyle{\int}fg\sum_{x>N}\sum_{y\leq N}\a(x)\rho(x)\ps(x,y)d\nut,\\
&\displaystyle{\int} fg\sum_{x>N}\sum_{y\leq N}(1-\a(x))\rho(x)\px(x,y)d\nut,
\eeqnn
so (\ref{eq:sumu}) can be rewritten (when $\int fgd\nut\ne0$,
otherwise we are done) as
\beqnn
&\sum_yp(-1,y)+\sum_{x>N}\sum_{y\leq N}\rho(x)p(x,y)\\
=&\sum_y\ps(-1,y)+\sum_y\px(-1,y)+\sum_{x>N}\sum_{y\leq N}\rho(y)p(y,x).
\eeqnn
So, it suffices to prove the equality
\beqn
\nonumber
&\sum_{x>N}\sum_{y\leq N}\rho(x)p(x,y)-
\sum_{x>N}\sum_{y\leq N}\rho(y)p(y,x)\\
\label{eq:sumd}
&=\sum_y\rho(y)p(y,-1)-\sum_yp(-1,y),
\eeqn
which we do by rewriting the l.h.s. as
$$\sum_{x\geq-1}\sum_{y\leq N}\rho(x)p(x,y)-
\sum_{x\geq-1}\sum_{y\leq N}\rho(y)p(y,x).$$
This equals the r.h.s. of (\ref{eq:sumd}) plus
$$\sum_{x\geq-1}\sum_{0\leq y\leq N}\rho(x)p(x,y)-
\sum_{x\geq-1}\sum_{0\leq y\leq N}\rho(y)p(y,x)$$
and the equality of these two terms follows from (\ref{eq:ro}).
\vfill\eject
\noindent {\bf 4. Final remarks.}
\vskip 5truemm
The method of proof of
Theorem 1 allows one to show that the departure process from queue $y$ is
a Poisson process of parameter $\rho(y)p(y,-1)$. Furthermore the departure
processes from different queues are independent (Kelly (1979)). One is tempted
to extend the result to the net flux out of queue $y$. But this is more difficult.
It is true that the departure process of red customers from different queues
are independent Poisson processes with rate $[\rho(y)-m(y)]p(y,-1)$. But it is
hard to control the net ouput process of black customers
because they can enter in other queues different from $y$ and the compensation
that allows one to prove Theorem 2 does not occur.
One particular case of transition function satisfying
(\ref{eq:ex})-(\ref{eq:ex1})
is the nearest neighbor asymmetric random walk
$$
p(x,y)=\cases{p,& if $y=x+1$\cr
q,& if $x\geq0,\,y=x-1$\cr
0,& otherwise,\cr}
$$
where $p+q=1$ and $q>p$. In this case
$$
m(x)=(p/q)^{x+1},
$$
and since $p(x,y)$ is doubly stochastic we can take
$$
\rho(x)=m(x)+(1-m(x))\rho,
$$
where $\rho$ is any number in the interval $(0,1)$ (Ferrari (1986)). When
$p=0$ Theorem 1 applies and $X_t$ is a Poisson process.
For nearest neighbor jumps, the system of queues is isomorphic to the simple exclusion
process as seen from the leftmost particle.
This is mentioned for this model by
Spitzer (1970) quoting an oral communication of Kesten who noticed that Theorem
1 holds for this last process. Liggett (1985) (Theorem 4.7) proves Theorem 1 by a direct
computation for the exclusion process.
Kipnis (1986) makes the relationship between Burke's result and Kesten's
observation.
It is possible to prove Theorem 2 for the net flux of customers between two
consecutive queues in a doubly infinite system. To be more precise, let
$\zeta_t$ be the process on ${\z}^{\n}$ with transition rates $p$ and $q$
respectively for customer jumps to the right (respectively left) nearest
neighbor. Let $\nur$ be the product measure of geometrics of parameter $\rho$.
Let $Y_t$ be the net flux of customers between queues $0$ and $-1$. Then $Y_t$
is a Poisson process of parameter $(q-p)\rho$ plus a perturbation of order one
as in Theorem 2. The case $p=0$ is immediate. The proof for the case $p> q >
0$ is based in a coupling between the semi infinite process $\eta_t$ and the
double infinite process $\zeta_t$ via the asymmetric simple exclusion process.
This proves a conjecture of Arratia (1983) and will appear in Ferrari and
Fontes (1993).
\vskip 5truemm
\noindent {\bf Acknowledgements.} We thank Marcos Magalh\~aes for discussions
on the background of queuing theory and for indicating us the relevant
references. This work is partially supported by FAPESP,
Projeto Tem\'atico, 90/3918-5 and CNPq.
\vfill\eject
\noindent {\bf References.}
\baselineskip 14pt
\parskip 3truemm
\parindent 0pt
E. Andjel (1982) Invariant measures for the zero range process. {\sl Ann
Probab}{ \bf 10}
No 3 525-547.
R. Arratia (1983) The motion of a tagged particle in the simple symmetric
exclusion system on $\z$. {\sl Ann. Probab.}{ \bf 11} 362-373.
P.J. Burke (1956) The output of a queueing system. {\sl Oper. Res.}{ \bf 4} 699-704.
A.\ De Masi, C.\ Kipnis, E.\ Presutti, E.\ Saada (1988).
Microscopic structure at the shock in the asymmetric simple exclusion. {\sl
Stochastics }{\bf 27}, 151-165.
P.A. Ferrari (1986) The simple exclusion process as seen from a tagged
particle {\sl Ann. Prob.}{ \bf 14} 4:1277 - 1290 (1986).
P.A. Ferrari, L. R. Fontes (1993) In preparation.
J. R. Jackson (1963) Jobshop-like queueing systems. {\sl Management Science}{
\bf 10}
131-142
F. P. Kelly (1979) {\sl Reversibility and stochastic networks.} Wiley series in
probability and mathematical statistics.
C. Kipnis (1986). Central limit theorems for infinite series of queues and
applications to simple exclusion. {\sl Ann.\ Probab.\ }{ \bf 14} 397-408.
T.\ M.\ Liggett (1985). {\sl Interacting Particle Systems.}
Springer, Ber\-lin.
F.\ Spitzer (1970). Interaction of Markov processes. {\sl Adv. Math.,}{ \bf 5}
246-290.
\vskip 7truemm
Instituto de Matem\'atica e Estat\'\i stica --- Universidade de S\~ao Paulo ---
Cx.~Postal 20570 --- 01498-970 S\~ao Paulo SP --- Brasil
pablo@ime.usp.br, lrenato@ime.usp.br
\end{document}