I generally understand how to do this but I'm having trouble with a formal proof.

"Consider an $M/M/1/m+1$ queue with exponential arrivals rate $\lambda$, exponential service rate $\mu$, and finite waiting room capacity $m$.

Let $X_{n}$ be the number of customers in the system just after the $n$th departure. Show that $\{X_n; \: n \geq 0\}$ is a Markov Chain with state space $E = \{0,...,m\}$ and derive it's transition matrix $P$.

I understand the definition of a Markov Chain says that $$P\{X_n = x_{n} | X_{n-1} = x_{n-1}, .... X_{0} = x_{0}\} = P\{X_{n} = x_{n} | X_{n-1} = x_{n-1}\}$$ or that given the present, the future is independent of the past.

How can that be shown for this particular queue though? As far as showing the state space $E = \{0,...,m\}$ I can reason it out that there are only $m$ states that this chain can be in since there are only $m$ spots in the waiting room and therefore anyone else must leave, but again not sure how to formally prove it.

My thoughts are that since this is a birth-death process, the system can only increase by one, decrease by one, or remain the same. And the transition matrix would have rows with

$\mu_{i} - (\lambda_{i}+\mu_{i}) \lambda_i$ (besides the first and last rows)

Is this the correct way to proceed, or is this a different scenario since we are considering the number of customers in the system "just after the $n$th departure."


1 Answer 1


Conditioned on $X_n = i$, the distribution of $X_{n+1}$ is determined by the number of customers that arrive between the $n^{\mathrm{th}}$ and $(n+1)^{\mathrm{th}}$ departures, and is independent of $\sigma(X_0,\ldots, X_{n-1})$, so the Markov property holds.

$\{X_n:n\geqslant 0\}$ is not a birth-death chain, however. For example, the probabilities $\mathbb P(X_1=j\mid X_0=0)$ are positive for $j=0,1,\ldots,m$. In general, $\mathbb P(X_{n+1}=j\mid X_n=i)$ is the probability that $j+1-i$ arrivals during the service of customer $n+1$, so the transition probabilities are $$ p_{ij} = \begin{cases} a_j,& 0=i\leqslant j\leqslant m\\ a_{j+1-i},& 0<i<j+1<m+1. \end{cases} $$ Let the first service time be $S_1$. Conditioned on $S_1=t$ (and the queue being empty at time zero), the number of customers that arrive during this service time follows a truncated Poisson distribution, that is, $a_n=\frac{(\lambda t)^n}{n!}e^{-\lambda t}$ for $n=0,1,\ldots,m-1$ and $a_m = 1 - \sum_{n=0}^{m-1}a_n$. The rest of the transition probabilities may be computed similarly.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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