The Infinite Server Queue

Last Updated: Jan 12, 2024

Often when studying continous time stochastic processes with discrete state space it is easy to compute the stationary properties of the chain, but harder to compute transient properties. Stationary properties describe the behavior of the system as it “settles down” over time and reaches a probabilistic equilibrium, or long-run “average” state. Transient properties are those that describe the evolution of the system in a finite amount of time, starting from a particular state.

An exception to this rule of thumb is the infinite server queue, also known as M/M/∞. It is easy to compute that the stationary distribution of the infinite server queue is Poisson with a parameter that depends on the arrival rate and per-server service rate of the system, named λ and μ respectively. Unusually, it is also easy to compute the transient properties of this process.

The argument is as follows. Suppose the system starts off in the empty state at time 0. We’ll use X(t) to denote the number-in-system at time t, so our initial assumption is that X(0)=0. We’ll compute the distribution of X(t). In the interval [0,t], the number of total arrivals are distributed Poisson(λt). Conditional on j arrivals in [0,t], the j arrival times are each independently distributed uniformly on [0,t]. Service for each arrival starts immediately (there are infinitely many servers, after all), and lasts for Exponential(μ) time. Denote by q the probability that the sum of independent Uniform(0,t) and Exponential(μ) random variables exceeds t. Conditional on j arrivals, there are then Binomial(j; q) customers remaining in the system at time t. Some basic algebraic massaging reveals that the resulting distribution of X(t) is then Poisson(λtq).

A similar argument works in generality if the initial configuration of the system is arbitrary (X(0)=i). All that needs to change is some accounting for the i exponential service times that the system needs to process starting at time 0. The resulting distribution is not as clean, but it can still be expressed in closed form without infinite sums.

\[P(X(t)=j\mid X(0)=i) = e^{-\lambda t q} \sum_{k=0}^{\min\{i,j\}} \binom{i}{k} e^{-\mu t k} (1-e^{-\mu t})^k \frac{(\lambda t q)^{j-k}}{(j-k)!}.\]

This nice argument works also for general service time distributions (M/G/∞), although the behavior when the system is not initially empty is slightly more intricate.