 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. ThenConditional 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.