Showing a queueing system is a Markov Chain

Question

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."

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.