= Solution
An <M G 1 queue> has <Poisson process> arrivals of rate $\lambda$, independent identically distributed service times of law $G$, one server, and here infinite waiting capacity. Use first-come-first-served service. Let $X_n$ be the number left just after the $n$th departure. During the next service, let $A_n$ be the number of arrivals. Then
$$
\boxed{X_n=(X_{n-1}-1)^++A_n}.
$$
Conditional on the next service time $S_n=s$, $A_n$ is Poisson with mean $\lambda s$. If $X_{n-1}=0$, the server waits for one arrival to start service; that arrival is the customer being served, and is not counted in $A_n$. This constructs the embedded <Markov chain>.
Back to article page
