Let $(\lambda_n)_{n\geq0}$ be a sequence of positive numbers such that $\lambda_n\rightarrow \lambda$ as $n\rightarrow +\infty$. These $\lambda_n$ are the parameters of a sequence of Poisson Processes $N(\lambda_n)$. Let $(S_i)_{i\geq0}$ be a sequence of reasonably smooth, positive i.i.d. random variables (say they have finite first and second moment).

To these objects we can associate a sequence of $M/G/1$ queues $(Q_n(t))_{n\geq0}$ by defining the arrival process as $N(\lambda_n)$ and the service times as $(S_i)_{i\geq0}$. If $\rho_n := \lambda_n/\mathbb E [ S_1] < 1$, their stationary distributions exists and are defined as $(Q_n)_{n\geq0}$. Assume also that $\rho := \lambda /\mathbb E[S_1] <1$.

My question is: is it true that $Q_n \stackrel{\text{d}}{\rightarrow} Q$, where $Q$ is the stationary distribution of the $M/G/1$ queue with input rate $\lambda$ and service times $(S_i)_{i\geq0}$?


Yes. To be precise about this you might have to specify more about what space you are working on, etc. For example, the number of customers in the queue is not Markov for a general service time distribution, so you have to be careful what you mean by "stationary distribution". You could look at the total amount of work in the queue, or alternatively at the number of customers in the queue along with the remaining service time of the customer currently in service.

In any case, by coupling the arrival processes for different arrival rates, and using a coupling-from-the-past construction (i.e. Loynes construction) to define a stationary evolution of the queue, you can obtain convergence in distribution (indeed, convergence in total variation). Couple the Poisson arrival processes so that the arrival points in $N(\lambda_i)$ are included in those of $N(\lambda_j)$ for whenever $\lambda_i < \lambda_j$. Couple the service time processes so that a customer arriving at the same time in different systems has the same service time.

Now consider the state of the queue at time 0. Fix some $\delta$ with $\lambda+\delta<\mathbb{E}[S_1]$. Let $\epsilon>0$. For $T$ large enough, with probability at least $1-\epsilon$ the queue with arrival rate $\lambda+\delta$ is empty at some point in $[-T, 0]$. From the coupling, all systems with arrival rate $\lambda_n <\lambda+\delta$ will also be empty whenever the $(\lambda+\delta)$-system is empty. Now, as $n\to\infty$ so that $\lambda_n\to\lambda$, the probability that the arrival process at rate $\lambda_n$ is identical to the arrival process at rate $\lambda$ on the interval $[-T,0]$ tends to 1. In particular, for $n$ large enough this even happens with probability at least $1-\epsilon$.

But if two systems are empty at the same point in $[-T,0]$, and their arrival processes coincide on $[-T,0]$, then they are in the same state at time $0$. So we have that for $n$ large enough, the time-0 state in the $\lambda$ system and the time-$0$ state in the $\lambda_n$-system are the same with probability at least $1-2\epsilon$.

So indeed the total variation distance between the time-0 state in the $\lambda_n$ system and the time-0 state in the $\lambda$ system tends to 0. But everything is stationary, so the time-0 state is just a sample from the stationary distribution.

  • $\begingroup$ Hi @James ! Thank you for your answer. The answer itself is very clear, but I am not familiar with the technique, so I have a a question. It looks like you are proving that for every $t$ there exists a coupling such that the queues with $\lambda_n$ input and a queue with $\lambda$ input agree from $t$ on with high probability.. How does stationarity enter the picture here? $\endgroup$ – Indigo Sep 17 '14 at 15:06
  • 1
    $\begingroup$ From a stationary arrival process, you can construct a stationary evolution for the queue. This is sometimes called "Loynes' construction"; for example, you might want to look at the book by Baccelli and Bremaud. For $s<t$ let $W[s,t]$ be the amount of work arriving during the interval $[s,t]$. Then the amount of work in the queue at time t is given by $X(t)=\sup_{s<t}(W[s,t]-t)$. $\endgroup$ – James Martin Sep 18 '14 at 11:20
  • 1
    $\begingroup$ Now for $\lambda_i<\lambda_j$, couple the arrival processes so that $W_i[s,t]\leq W_j[s,t]$ for all $s$ and $t$. Then $X_i(t)\leq X_j(t)$ for all $t$. In particular if the $j$-system is empty at some time in $[−T,0]$, then so is the $i$-system. If, further, the two arrival processes are identical on $[−T,0]$, then also $X_i(0)=X_j(0)$. But the system is stationary so 0 is just a typical time. If we can show that with high probability two systems have the same state at time 0, then their stationary distributions are close in total variation distance. $\endgroup$ – James Martin Sep 18 '14 at 11:44
  • $\begingroup$ I edited the end of the explanation in the answer also to try to make it a bit clearer. $\endgroup$ – James Martin Sep 18 '14 at 11:45
  • $\begingroup$ What do you mean by stationary arrival process? A Poisson process has stationary increments, but it's not itself stationary (meaning: the distribution of $N(t)$ is different from the distribution of $N(t+h)$). $\endgroup$ – Indigo Sep 18 '14 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.