The M/M/1 Queue as a Stochastic Process
An M/M/1 queue models customers arriving to a system with one server. Its notation summarizes three structural choices: arrivals are Poisson, service times are exponential, and one server serves customers. The queue has unlimited capacity, so an arriving customer is admitted even when many customers are already present. The model is useful in part because its assumptions reduce a potentially detailed history—arrival times, service ages, and customer identities—to a simple state: the number of customers currently in the system.
We define the model on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \(A(t)\) count arrivals during the time interval from \(0\) to \(t\), where \((A(t))_{t\geq 0}\) is a Poisson process with rate \(\lambda>0\). Each customer has a service requirement with exponential distribution of rate \(\mu>0\). Service requirements are independent and identically distributed, and are independent of the arrival process. There is one server, and the system has no limit on the number of customers it can hold.
FCFS means that customers begin service in the order they arrive. If the server is busy, a new arrival joins the end of the waiting line; if the server is idle, an arrival begins service. The count \(N(t)\) does not record customer identities or the order of the waiting customers. Those details matter for questions about a particular customer, but, under the M/M/1 assumptions, they are not needed to describe the future evolution of the count.
For conditioning, let \((\mathcal{F}_t)_{t\geq0}\) represent the observed history of arrivals and service up to time \(t\). The Markov property for \(N(t)\) means that, for every \(s\geq0\) and every subset \(C\subseteq S\), the conditional probability of \(N(t+s)\in C\), given \(\mathcal{F}_t\), depends on the past only through \(N(t)\). More precisely, it equals the probability of being in \(C\) after time \(s\) for a queue started in state \(N(t)\). We next establish why the stated assumptions give this property.
Why Exponential Service Matters
If the system is nonempty, one customer is in service. The time already spent in service is part of the observed history, but it does not change the distribution of the remaining service time when service is exponential. For an exponential service requirement \(S\) with rate \(\mu\), the survival probability is \(\mathbb{P}(S>x)=e^{-\mu x}\) for \(x\geq0\).
Proof. The event \(S>a\) has probability \(e^{-\mu a}>0\), so the conditional probability is defined. The event \(S-a>x\), together with \(S>a\), is exactly the event \(S>a+x\). Therefore, \[ \mathbb{P}(S-a>x\mid S>a) =\frac{\mathbb{P}(S>a+x)}{\mathbb{P}(S>a)} =\frac{e^{-\mu(a+x)}}{e^{-\mu a}} =e^{-\mu x}. \] This holds for every \(a,x\geq0\), including \(a=0\) and \(x=0\). \(\square\)
The statement applies at a random service age as well: once the observed history specifies that service has lasted \(a\) units without completing, the conditional distribution of the remaining time is the same exponential distribution. Independence of arrivals and service ensures that observing arrivals does not alter this residual-service calculation.
Worked Example: Residual Service After an Elapsed Time
Suppose service times have exponential rate \(\mu=2\). A customer has already been in service for \(a=\tfrac12\) time unit. Find the conditional probability that service lasts at least another \(x=\tfrac14\) time unit, given that it has lasted the first \(\tfrac12\) unit.
The required conditional probability is \[ \mathbb{P}(S>\tfrac12+\tfrac14\mid S>\tfrac12) =\frac{\mathbb{P}(S>\tfrac34)}{\mathbb{P}(S>\tfrac12)}. \] Using the exponential survival formula, the numerator is \(e^{-2(3/4)}=e^{-3/2}\), and the denominator is \(e^{-2(1/2)}=e^{-1}\). Their ratio is \(e^{-3/2}/e^{-1}=e^{-1/2}\).
Check: Memorylessness gives \(e^{-\mu x}=e^{-2(1/4)}=e^{-1/2}\), the same result. The elapsed service time does not appear in the final probability.
The Queue-Length Markov Property
Proof. Fix a time \(t\) and consider the information in \(\mathcal{F}_t\). If \(N(t)=0\), the server is idle. The future arrivals after \(t\) have the same law as a fresh Poisson arrival process and are independent of the history, by independent increments. There is no service in progress whose age must be included in the state.
If \(N(t)>0\), there is one customer in service. Conditional on the observed service age and on service not yet having completed, the lemma shows that the residual service time is exponential with rate \(\mu\). It is independent of future arrivals because service requirements and arrivals are independent. Customers waiting at time \(t\) have not yet begun service; their service requirements are independent fresh exponential variables. The FCFS rule fixes their service order, while their identities do not affect the count.
Consequently, conditional on the history at time \(t\), the future count is generated from \(N(t)\) using the same laws for future arrivals, the residual service if the system is busy, and the service requirements of customers who begin service later. These laws do not depend on \(t\) or on any other feature of the history. Thus, for every \(s\geq0\) and \(C\subseteq S\), the conditional probability \(\mathbb{P}(N(t+s)\in C\mid\mathcal{F}_t)\) is determined solely by \(N(t)\) and \(s\). This is the Markov property, and the fact that the rule does not depend on \(t\) makes it time-homogeneous. \(\square\)
This result explains the choice of state. When \(N(t)=0\), the server is idle; when \(N(t)>0\), it is busy, and exponential memorylessness removes the need to record how long the current service has lasted. A count that excluded the customer in service would not have this convenient interpretation: it could be zero both when the server is idle and when one customer is being served.
Worked Example: Reading the State Under FCFS
At a particular time, suppose one customer is being served and three customers are waiting. The waiting customers arrived in the order \(C_1,C_2,C_3\), and a new customer \(C_4\) arrives.
The state before the arrival is \(N(t)=1+3=4\): one customer in service plus three waiting. The arrival joins the end of the line, so immediately afterward there are one customer in service and four waiting. The new state is \(N(t+)=1+4=5\). If the customer in service completes and no other event occurs at that instant, the state becomes \(4\), and \(C_1\) begins service under FCFS.
Check: The state counts every customer in the system, not just those waiting. Before the arrival, the count \(4\) agrees with one in service plus three waiting; after the arrival, \(5\) agrees with one in service plus four waiting.
Independent Inputs and What the State Does Not Say
The Poisson assumption specifies the arrival process, not the queue length itself. In particular, the number of arrivals in disjoint time intervals is independent, and the law of the arrivals in an interval depends on its length rather than its location. The exponential assumption specifies individual service requirements. These requirements are independent across customers and independent of arrivals. Together with the single-server FCFS rule, these assumptions determine how the count changes over time. They do not say that \(N(t)\) has the same distribution at different times; the Markov property is a statement about conditional future dependence, not stationarity.
Worked Example: No Arrival and No Completion During an Interval
Suppose the queue is in state \(N(t)=1\), with one customer in service and no one waiting. Let the arrival rate and service rate both be \(1\), and consider an interval of length \(h=\ln 2\). Find the probability that there is neither an arrival nor a service completion during this interval.
The probability of no arrival is \(e^{-1\cdot\ln 2}=\tfrac12\). Since the current service has an exponential residual time of rate \(1\), the probability of no completion during the interval is also \(e^{-1\cdot\ln 2}=\tfrac12\). The two events are independent, so the probability of both is \[ \tfrac12\cdot\tfrac12=\tfrac14. \]
Check: Directly multiplying the two survival probabilities gives \(e^{-(1+1)\ln 2}=e^{-\ln 4}=\tfrac14\). This is the probability of no arrival and no completion; it is not, by itself, the probability that the queue length is \(1\) at the end, since other event sequences could also leave the count at \(1\).
Common Mistakes and a Boundary of the Model
Common mistake: using an unconditional service probability for a customer already in service. If service has lasted \(a\) units, the probability of another \(x\) units is not \(\mathbb{P}(S>a+x)\) by itself. That expression also includes the probability that service survived the first \(a\) units. The conditional probability must divide by \(\mathbb{P}(S>a)\).
For example, with rate \(\mu=1\), elapsed time \(a=1\), and additional time \(x=1\), the incorrect calculation gives \(\mathbb{P}(S>2)=e^{-2}\). The correct conditional calculation is \[ \mathbb{P}(S>2\mid S>1)=\frac{e^{-2}}{e^{-1}}=e^{-1}. \] The latter is the probability that the residual service exceeds one unit, given that the customer is still being served.
Exponential service is important to the Markov state description. To see why, consider instead deterministic service times of length \(1\), still with one FCFS server and Poisson arrivals. In state \(N(t)=1\), the remaining service time depends on the elapsed service age: at age \(\tfrac34\), service ends after \(\tfrac14\) time unit, while at age \(\tfrac14\), it ends after \(\tfrac34\) time unit. For a next interval of length \(\tfrac12\), the service-completion behavior differs in these two histories even though the queue-length state is the same. The count alone therefore does not determine the conditional future law; recording service age (or some equivalent information) would be necessary for a Markov description.
Likewise, a service discipline is part of the model, not a consequence of the queue-length definition. FCFS specifies the order customers begin service. It is especially relevant when asking about individual waiting times. For the evolution of the total count, what matters is that the server works on one customer whenever the system is nonempty and that service requirements follow the assumed independent exponential law.
Check Your Understanding
Use the assumptions and definitions above to answer the following questions.
- A system has two customers waiting and one in service. What is \(N(t)\), and what happens to the count when a new customer arrives?
- For an exponential service time of rate \(\mu\), derive the probability that residual service exceeds \(x\), given that service has already lasted \(a\).
- Which independence assumptions are used to combine the probability of no arrival with the probability of no service completion?
- Explain why the server’s busy or idle status does not need to be recorded separately once \(N(t)\) is known.
- Give a reason that queue length alone may fail to be Markov when service times are deterministic rather than exponential.