Rates and Occupancy in the M/M/Infinity Queue

The M/M/Infinity Model

In a finite-server queue, an arriving customer may have to wait because all servers are busy. The M/M/infinity queue removes that constraint: whenever a customer arrives, a server is available for that customer, regardless of how many other customers are present. The resulting occupancy process has a simple, but state-dependent, service-completion rate.

Fix an arrival rate \(\lambda\ge 0\) and a service rate \(\mu>0\). Arrivals form a Poisson process of rate \(\lambda\), and each customer's service time is exponentially distributed with rate \(\mu\). Service times are mutually independent and independent of the arrival process. There are infinitely many servers, each serving one customer at a time. Assume the queue begins with a finite number of customers. All these random quantities are defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\).

The first M denotes Poisson arrivals, the second M denotes exponential service times, and infinity denotes unlimited servers. In particular, \(\mu\) is the completion rate for one customer, not the completion rate for the entire system. When there are \(n\) customers, \(n\) separate services are in progress.

Why the Completion Rate Is \(n\mu\)

Suppose the system currently contains \(n\) customers. Each of their remaining service times is exponential with rate \(\mu\), conditional on the history so far. This conditional statement follows from the memoryless property: for an exponential service time \(V\), \(\mathbb{P}(V>s+t\mid V>s)=e^{-\mu t}\) for \(s,t\ge0\). Independence of the service times means the \(n\) remaining times are independent. The next completion is the minimum of these \(n\) times.

Proof. For \(n\ge1\), let \(V_1,\ldots,V_n\) be the remaining service times. For \(u\ge0\), independence and the exponential survival probability give \(\mathbb{P}(\min_i V_i>u)=\prod_{i=1}^n\mathbb{P}(V_i>u)=\prod_{i=1}^n e^{-\mu u}=e^{-n\mu u}\). This is the survival function of an exponential random variable with rate \(n\mu\). If \(n=0\), there is no customer in service, so no service completion can occur until an arrival takes place; the completion rate in state zero is therefore zero. \(\square\)

Arrivals are independent of service completions and have rate \(\lambda\). Consequently, when the occupancy is \(n\), the possible next events are an arrival, at rate \(\lambda\), and a completion, at rate \(n\mu\). If their combined rate is positive, the time to the next event is exponential with rate \(\lambda+n\mu\); the probabilities that the next event is an arrival or a completion are respectively \(\lambda/(\lambda+n\mu)\) and \(n\mu/(\lambda+n\mu)\). When \(n=0\) and \(\lambda=0\), there is no next event.

These rates specify the generator \(Q=(q_{ij})\) of the occupancy process. For a continuous-time chain, \(q_{ij}\), for \(i\ne j\), is the rate of a transition from state \(i\) to state \(j\), and the diagonal entry is the negative sum of the rates out of state \(i\).

All other off-diagonal entries are zero, and \(q_{0,-1}\) is not a state or a transition. Equivalently, \(q_{0,1}=\lambda\) and \(q_{0,0}=-\lambda\). Every row sums to zero: for \(n\ge1\), \(\lambda+n\mu-(\lambda+n\mu)=0\), and for \(n=0\), \(\lambda-\lambda=0\). This generator describes rates, not stationary probabilities; no stationary distribution is needed to obtain it.

Worked Rate Calculations

Why an Arrival Never Waits

The absence of waiting is a direct consequence of the model's service rule. At any finite time, there are only finitely many customers in the system: the initial population is finite, and a Poisson process has finitely many arrivals in every bounded time interval with probability one. If an arrival occurs when \(n\) customers are present, those customers occupy \(n\) servers, while infinitely many servers are available. The new customer can therefore be assigned a distinct server immediately. The service time for that customer begins at the arrival time.

Proof. Consider an arrival at a time when the occupancy is \(n\), where \(n\) is finite. The model assigns each of the \(n\) customers in service to a server, with no server assigned to more than one customer. Because the server supply is unlimited, an additional server is available for the arriving customer. Assigning that server starts the customer's service immediately and increases the occupancy from \(n\) to \(n+1\). The argument applies to every finite \(n\), and the occupancy is finite at every finite time with probability one. Hence no arrival has to wait. \(\square\)

This statement concerns waiting for service, not the time until a future completion elsewhere in the system. An arrival begins its own service immediately, but its service duration remains random and exponential with rate \(\mu\). Nor does immediate service imply that the occupancy is constant: arrivals and completions continue to change it.

A Common Rate Mistake

A frequent error is to use \(\mu\) as the total completion rate even when several customers are in service. For example, if \(n=4\) and \(\mu=\tfrac12\), the incorrect calculation gives a total rate of \(\tfrac12\). It treats four simultaneous independent services as though only one customer were being served. The correct calculation is \(n\mu=4\cdot\tfrac12=2\). The individual rate remains \(\tfrac12\); the system's total completion rate depends on the number of active services.

A second distinction is useful when comparing models: with \(c\) finite servers and \(n\) customers present, the total completion rate is \(\min(n,c)\mu\), because only \(\min(n,c)\) customers can be in service. In the M/M/infinity model, \(\min(n,\infty)=n\) for finite \(n\), giving \(n\mu\). The formula is a count of active independent service clocks, not a change in any one customer's service rate.

The rate description is valuable whenever the occupancy process is modeled as a continuous-time Markov chain. It identifies the only possible jumps, their rates, and the dependence of the service rate on occupancy. These facts are enough to construct the generator and to calculate next-event probabilities. They do not, by themselves, assert a stationary distribution or describe the process's transient occupancy probabilities.