M/G/1 queue has embedded Markov chain

Question

I tried to prove that the M/G/1 queue has an embedded discrete-time Markov chain. But I'm not sure if I have done it right and properly. Specially I'm not 100% sure if i calculated right the conditional probability. It would be really great if someone could have a quick look.

In an M/G/1 queue the customers arrive in the manner of a poisson process with parameter $\lambda$ and the service times $S$ have some general distribution. $D_n$ denotes the departure-time of the $n$th customer from the system. $Q(D_n)$ is the number of customers, that he leaves behind him on his departure. $U_n$ denotes the number of arriving customers in the queue, during the service time $S_{n+1}$ of the $(n+1)$th customer.

Therefore $U_n$ only depends on the service time $S_{n+1}.$

We can write the number of customers as $$Q(D_{n+1})=U_n+Q(D_{n})-h(Q(D_{n})),$$ $$ \text{where } h(x):= \begin{cases} 1 & \text{ if } x>0,\\ 0 & \text{ if } x \leq 0. \end{cases}$$

Claim: $Q(D)=\{ Q(D_n) : n \geq 1 \}$ is a discrete-time Markov chain.

Proof: First I know that $Q(D)$ lies in the Set $E=\{ 0,1,2,... \}$, since it is the number of customers. Therefore the set space $E$ is countable. Now I need to prove the markov property (this is my main problem, I'm not sure how to write it exactly): $$\Pr(Q(D_{n+1})=x_{n+1} \ \vert \ Q(D_0)=x_0, Q(D_1)=x_1, . \ . \ . , Q(D_n)=x_n)\\ =\Pr(U_n+Q(D_{n})-h(Q(D_{n}))=x_{n+1} \ \vert \ Q(D_0)=x_0, Q(D_1)=x_1, . \ . \ . , Q(D_n)=x_n)\\ =\Pr(U_n=x_{n+1}-Q(D_{n})+h(Q(D_{n})) \ \vert \ Q(D_0)=x_0, Q(D_1)=x_1, . \ . \ . , Q(D_n)=x_n)\\ =\Pr(U_n=x_{n+1}-Q(D_{n})+h(Q(D_{n})) \ \vert \ Q(D_n)=x_n)\\ =\Pr(U_n+Q(D_{n})-h(Q(D_{n}))=x_{n+1} \ \vert \ Q(D_n)=x_n)\\ =\Pr(Q(D_{n+1})=x_{n+1} \ \vert \ Q(D_n)=x_n).$$

Are these calculations right?

From this I can conclude that $Q(D)$ is a discrete-time Markov chain (it is not possible to be continuous-time Markov chain, since $Q(D)$ is not in general exponential distributed).

Answer 1

More generally.

Let $(X_n)_{n\geqslant0}$ be defined by $X_{n+1}=G(X_n,Z_{n+1})$ for every $n\geqslant0$, where $(Z_n)_{n\geqslant1}$ is i.i.d. and independent of $X_0$. Then $(X_n)_{n\geqslant0}$ is a Markov chain.

If need be, one can write down the transition probability of $(X_n)_{n\geqslant0}$ as $$P(X_{n+1}\in A\mid (X_k)_{0\leqslant k\leqslant n})=F(X_n,A),\qquad F(x,A)=P(G(x,Z_1)\in A).$$

Unrelated:

"From this I can conclude that $Q(D)$ is a discrete-time Markov chain (it is not possible to be continuous-time Markov chain, since $Q(D)$ is not in general exponential distributed)."

Actually, $Q(D)$ cannot be a "continuous-time Markov chain", simply because $Q(D)$ is indexed by the integers.