Why is M/G/1 queue viewed only at departure times?

Question

It is said in the book that for M/G/l queue, viewed only at departure times, leads to an imbedded discrete-time Markov chain. Viewing the queue only at arrival times does not yield a Markov chain.

Let X n be the number of customers in an M/G/1 queue just prior to the arrival of the nth customer. why Xl, X 2, ... is not a discrete-time Markov chain

Answer 1

In an M/G/1 queue, the times between arrivals are exponentially distributed, and therefore memoryless: if you want to know how long to wait until the next arrival, you don't have to know how long you've been waiting. However, the same is not true for times between departures.

So, if you want to describe the entire state of the network after a departure, it's sufficient to specify $X_n$: the number of jobs in the queue.

However, if you want to describe the entire state of the network after an arrival (or at any other time), you need to give the ordered pair $(X_n, t_n)$: $X_n$ is still the number of jobs in the queue, and $t_n$ is the amount of time that the job currently at the server has been there.

That's the intuition for why only looking at $X_n$ is probably not going to work. To prove this formally, we need to argue that viewing the M/G/1 queue at arrival times can sometimes violate the Markov property.

Examples are pretty annoying to compute with, even if the processing time distribution is very simple. But the idea is that knowing the history of the Markov chain gives us a hint about $t_n$.

For example, if $X_n = 1$, that tells us that before the $n^{\text{th}}$ arrival, there was one job being processed. That looks very different in the two cases where:

• $X_{n-1} = 100$ and $X_n = 1$: before the $(n-1)^{\text{th}}$ arrival, there were lots of jobs in the system, and then they all got cleared. This makes it very likely that $t_n$ is very small.
• $X_{n-1} = 0$ and $X_n = 1$: before the $(n-1)^{\text{th}}$ arrival, there were no jobs in the system. Then $t_n$ is the entire inter-arrival time between jobs $n-1$ and $n$.

When service time is not memoryless, our guess at the value of $t_n$ is also going to affect the distribution of $X_{n+1}$. So that distribution is going to be different in the two cases above, contradicting the Markov property.