M/G/∞ Queue and Campbell’s Theorem

The M/G/$\infty$ has Poisson arrivals and general service times; here, the number of jobs in service is Poisson distributed. Campbell’s theorem extends the proof idea by giving the moment generating function of sums taken over the points of a Poisson process.

The M/G/∞ Queue

Jobs arrive according to a Poisson process with rate $\lambda$ . Their service times are independent and identically distributed copies of a random variable $S$ . Every job begins service immediately upon arrival and is served at unit speed.

Theorem

Suppose that an M/G/∞ queue is empty at time $0$ . Then the number of jobs in the system at time $t$ , denoted by $Q(t)$ , is Poisson distributed with mean

$\displaystyle \lambda\int_0^t\mathbb P(S\geq s)\,ds.$

Proof

Plot each arrival time on the horizontal axis and the corresponding service time as a vertical height. A job that arrives at time $u$ remains in the system at time $t$ precisely when its service time exceeds $t-u$ .

The M/G/∞ queue.

In the figure, the shaded region represents the jobs that are still in the system at time $t$ . By the Poisson marking property, the number of points in this region is Poisson distributed. Its mean is

$\displaystyle \lambda\int_0^t\mathbb P(S\geq t-u)\,du=\lambda\int_0^t\mathbb P(S\geq s)\,ds.$

This proves the result.

□

Campbell’s Theorem

Campbell’s theorem generalizes the preceding Poisson-set argument.

Let $N_t$ be a Poisson process with rate $\lambda$ , let $\tau_1,\tau_2,\ldots$ be its jump times, and let $X_1,X_2,\ldots$ be independent and identically distributed random variables, independent of the Poisson process. Define

$\displaystyle Z_t=\sum_{k=1}^{N_t}g_{\tau_k}(X_k).$

Campbell’s Theorem

The moment generating function of $Z_t$ is

$\displaystyle \mathbb E\!\left[e^{\theta Z_t}\right]=\exp\left\{\lambda\int_0^t\left(\mathbb E\!\left[e^{\theta g_s(X)}\right]-1\right)\,ds\right\}.$

Proof

Conditional on $N_t=n$ , the jump times $\tau_1,\ldots,\tau_n$ are distributed as the order statistics of $n$ independent Uniform $[0,t]$ random variables.

Therefore,

$\displaystyle \mathbb E\!\left[e^{\theta Z_t}\right]=\mathbb E\!\left[\mathbb E\!\left[e^{\theta\sum_{k=1}^{N_t}g_{\tau_k}(X_k)}\mid N_t\right]\right].$

Conditional on $N_t=n$ , the product is symmetric in the jump times, so we may average over independent uniform random variables. This gives

$\displaystyle \mathbb E\!\left[e^{\theta Z_t}\mid N_t=n\right]=\left(\frac{1}{t}\int_0^t\mathbb E\!\left[e^{\theta g_s(X)}\right]\,ds\right)^n.$

Hence,

$\displaystyle \mathbb E\!\left[e^{\theta Z_t}\right]=\mathbb E\!\left[a^{N_t}\right],\qquad a=\frac{1}{t}\int_0^t\mathbb E\!\left[e^{\theta g_s(X)}\right]\,ds.$

Using the probability generating function of a Poisson random variable,

$\displaystyle \mathbb E[a^{N_t}]=\exp\{\lambda t(a-1)\},$

we obtain

$\displaystyle \mathbb E\!\left[e^{\theta Z_t}\right]=\exp\left\{\lambda\int_0^t\left(\mathbb E\!\left[e^{\theta g_s(X)}\right]-1\right)\,ds\right\}.$

This proves the result.

□