From a Continuous-Time Queue to a Discrete-Time State
An M/G/1 queue is observed in continuous time: customers arrive at random times, and their service durations need not be exponential. For many questions, however, a useful description records the system only at successive departures. This changes the clock from ordinary time to departure number. The essential modeling choice is what to count at each observation: the embedded state is the number of customers left in the system immediately after a departure.
Here “M” means that arrivals form a Poisson process, “G” means that service times have a general distribution, and “1” means there is one server. The departure-epoch process is discrete-time even though its observations occur at random continuous times. Defining this process does not require that the queue be stable or that it have a stationary distribution.
The count includes every customer still in the system. If \(Y_n>0\), the next customer starts service immediately after \(D_n\), but that customer is still included in \(Y_n\). If \(Y_n=0\), the system is empty just after the departure and remains idle until a later arrival. The observation time is the instant just after a departure, not an arbitrary time and not the instant just before that departure.
For definiteness, the history observed through the \(n\)th departure includes past arrival times and completed services, but does not reveal the service requirements of customers who have not yet begun service. Denote this departure-indexed history by \((\mathcal{F}_n)_{n\ge1}\). The natural history of the embedded process is \(\mathcal{G}_n=\sigma(Y_1,\ldots,Y_n)\), a smaller filtration. We will see that the post-departure count is Markov even when conditioning on the observed queue history \(\mathcal{F}_n\).
Why the Departure-Epoch Count Is a Markov State
A state is useful when it retains the information needed to describe the next step without retaining the entire past. At a departure, the count tells whether the server is busy or idle and how many customers are waiting or about to be served. FCFS and independent, identically distributed service requirements ensure that the next service requirement is fresh; the Poisson assumption ensures that future arrivals have the appropriate residual-arrival law.
Proof. Fix a departure index \(n\) and condition on the observed history through \(D_n\). If \(Y_n>0\), the next customer in FCFS order begins service immediately. Its service requirement has distribution \(G\) and is independent of the observed history, because service requirements are independent and identically distributed and the requirement of a customer who has not started service has not been revealed. The arrivals after \(D_n\) have the Poisson residual-arrival law, independent of that fresh service requirement. If the server was busy immediately before \(D_n\), the time \(D_n\) may lie within an interarrival interval; the exponential interarrival distribution has the memoryless property \(\mathbb{P}(E>u+v\mid E>u)=e^{-\lambda v}\) for \(u,v\ge0\), so the residual time to the next arrival does not depend on the elapsed part of that interval.
If \(Y_n=0\), the server waits for the next arrival. The same memoryless property gives an exponential waiting time of rate \(\lambda\), independent of the observed past. That arrival begins a fresh service with distribution \(G\); subsequent arrivals during that service again follow the Poisson law and are independent of the service requirement. In either case, the customers present after the next departure are determined by the current count, a fresh service requirement, and arrivals during the relevant future interval. The conditional law of those inputs does not depend on earlier queue history. Hence the conditional distribution of \(Y_{n+1}\) depends on \(\mathcal{F}_n\) only through \(Y_n\), proving the assertion. \(\square\)
This proposition identifies the process as an embedded Markov chain. It does not assert that its transition probabilities have already been calculated, nor that the chain has a stationary distribution. A later calculation can obtain those probabilities by conditioning on the service duration and counting arrivals during service. The modeling step here is to specify the observation epochs and the state that makes the future description possible.
Worked Departure-Epoch Sample Paths
Worked Example: Tracking Three Successive Departures
Suppose one customer begins service at time \(0\). The service durations of the first three customers are \(2\), \(2\), and \(2\) time units. There are arrivals at times \(\tfrac12\) and \(\tfrac52\), and there are no other arrivals through time \(6\), including at time \(6\). Find the first three post-departure counts.
The first customer completes service at \(D_1=0+2=2\). The arrival at \(\tfrac12\) is waiting, so immediately after this departure \(Y_1=1\). That waiting customer begins service at time \(2\) and completes at \(D_2=2+2=4\). The customer arriving at \(\tfrac52\) is then waiting, so \(Y_2=1\). This customer begins service at time \(4\) and completes at \(D_3=4+2=6\). No other customer has arrived through time \(6\), including at the endpoint, so \(Y_3=0\).
Check: The sequence of departure times is \(2,4,6\). At the first two departures exactly one customer remains, and at the third none remains. Thus \((Y_1,Y_2,Y_3)=(1,1,0)\). Specifying the endpoint matters: without the information about arrivals at time \(6\), the count immediately after \(D_3\) would not be determined by the stated sample path.
Worked Example: An Empty System and a Later Departure
Suppose a departure at time \(3\) leaves the system empty, so \(Y_1=0\). The next arrival is at time \(5\), its service duration is \(2\), and two more arrivals occur at times \(6\) and \(\tfrac{13}{2}\). There are no other arrivals through time \(7\), including at time \(7\). Find the next departure time and post-departure count.
The system is idle from time \(3\) until the arrival at time \(5\). That customer begins service at \(5\) and completes at \(D_2=5+2=7\). The arrivals at \(6\) and \(\tfrac{13}{2}\) both occur during this service. Neither has departed by time \(7\), and the endpoint condition rules out an additional arrival exactly at \(7\). Therefore \(Y_2=2\).
Check: Immediately before the departure at \(7\), there are three customers in the system: one in service and two waiting. The departing customer leaves, and the two waiting customers remain, giving \(Y_2=3-1=2\). The earlier empty state \(Y_1=0\) describes the system just after time \(3\), not the entire interval before the next departure.
Worked Example: A General Service Distribution Affects the Embedded State
Suppose the service duration of a customer starting service is \(1\) with probability \(\tfrac12\) and \(2\) with probability \(\tfrac12\), independently of arrivals, and the arrival rate is \(\lambda=1\). If a departure leaves the system empty, what is the probability that the next departure also leaves it empty?
After an empty departure, the next arrival starts service. Conditional on a service duration \(s\), the number of further arrivals during that service is Poisson with mean \(\lambda s=s\). The next departure leaves the system empty exactly when there are zero such arrivals. For \(s=1\), this probability is \(e^{-1}\); for \(s=2\), it is \(e^{-2}\). Averaging over the two possible service durations gives \[ \mathbb{P}(Y_{n+1}=0\mid Y_n=0) =\tfrac12 e^{-1}+\tfrac12 e^{-2} =\frac{e^{-1}+e^{-2}}{2}. \]
Check: The two conditional cases have probabilities \(\tfrac12\) and \(\tfrac12\), which sum to \(1\); their weighted zero-arrival probabilities are therefore \(\tfrac12 e^{-1}\) and \(\tfrac12 e^{-2}\). This calculation uses the service distribution, not merely its mean. It illustrates why a general service-time law must be retained in the M/G/1 model.
What the Embedded State Does—and Does Not—Say
The sequence \((Y_n)\) records customer counts at departure epochs; it does not record the elapsed time between those epochs. Two successive transitions of the embedded chain may be separated by different amounts of real time, both because service durations vary and because an empty queue waits for an arrival. Consequently, a statement about the long-run fraction of departure indices in a state is not automatically a statement about the fraction of clock time spent there.
No traffic-intensity or stability condition was imposed to define \(Y_n\). The assumptions \(\lambda>0\) and finite service durations ensure that arrivals continue and each customer has finitely many customers ahead under FCFS, so its departure occurs after finitely many finite services. Hence successive departures can be indexed. Stability conditions become important for questions about recurrence or stationary distributions, but those are separate from defining the model and its embedded state.
Common pitfall: counting the departing customer. If there is one customer in service and two waiting just before a departure, the count just before departure is \(3\). It is incorrect to set the post-departure state to \(3\): that counts the customer who has just left. The correct count immediately after the departure is \(3-1=2\). If no customers were waiting, the correct post-departure state would be \(0\), even though the pre-departure count was \(1\).
A second pitfall is to describe a sample path as having no arrivals “before” a departure and then infer the count just after it. That wording leaves open an arrival exactly at the departure time. State explicitly that there is no arrival at the endpoint, or use the standard probability-one fact that a Poisson arrival does not coincide with a departure under the assumptions here. The sample-path examples above specify the endpoint to make their counts unambiguous.
| Item | M/G/1 departure-epoch meaning |
|---|---|
| Arrival model | Poisson process of rate \(\lambda>0\) |
| Service model | Independent, identically distributed durations with law \(G\) |
| Service discipline | One server, FCFS, no loss, unlimited waiting space |
| Observation time | Immediately after each departure \(D_n\) |
| Embedded state | \(Y_n\), the number of customers then remaining |
| Embedded state space | \(\{0,1,2,\ldots\}\) |
Check Your Understanding
Use the modeling assumptions and the precise “immediately after departure” convention in your answers.
- Which assumptions are represented by the letters M, G, and 1 in M/G/1?
- At a departure, one customer is in service and four are waiting. What is the post-departure state, assuming no simultaneous arrival?
- Why does an empty post-departure state not mean that the next departure occurs immediately?
- Explain why the departure-epoch count can be Markov even though the service-time distribution is not exponential.
- A sample path says there are no arrivals strictly before a departure time. Is that enough to determine the post-departure count? Explain the endpoint issue.
- Does defining the embedded chain require assuming that the queue has a stationary distribution? Why or why not?