Construction of the G/M/1 queue length process

The problem

Bremaud provides a construction of the queue length process \(\{Q(t)\}\) of the G/M/1 queue along the following lines. Assume that \(\{A(t)\}\) is the arrival process to that \(A(t)\) is the number of arrivals up to and including time \(t\) (hence \(\{A(t)\}\) is cadlag). Assume further that \(\{N_s(t)\}\) is a Poisson counting process. It is clear that \(\{A(t)\}\) and \(\{N(t)\}\) have, with probability 1, no points in common.

The departure process \(\{D(t)\}\) and \(\{Q(t)\}\) can now be defined as

\[\begin{split}\begin{align} Q(t) &= Q_0 + A(t) - D(t), \\ D(t) &= \int_0^t 1\{Q(s-)>0\} dN_s(s) \end{align}\end{split}\]

The question is whether a solution to this integral equation exists.

A possible construction

The above integral equation can be given a meaning in a path-for-path \(\omega\) for \(\omega\) sense. Lets fix a path, so that \(A(t)\) and \(N_s(t)\) are known for all \(t\). Then the integral \(\int f(s) dN_s(s)\) can be interpreted as Riemann-Stieltjes integral for suitable \(f(s)\).

Next, for ease assume that \(Q_0 = 0\). We prove the existence of a solution by means of an constructive, inductive, approach.

\[\begin{split}\begin{align} Q_0(t) &= A(t), \\ D_0(t) &= \int_0^t 1\{Q_0(s-)>0\} dN_s(s), \\ Q_1(t) &= A(t)- D_0(t), \\ D_1(t) &= \int_0^t 1\{Q_1(s-)>0\} dN_s(s), \\ \end{align}\end{split}\]

and so on, so that, in general,

\[\begin{split}\begin{align} D_i(t) &= \int_0^t 1\{Q_i(s-)>0\} dN_s(s), \\ Q_{i+1}(t) &= A(t)- D_i(t). \end{align}\end{split}\]

Observe that, as \(D_0 \geq 0\), \(Q_1 \leq Q_0\). This, in turn, implies that \(D_1 \leq D_0\), which, in turn, implies \(Q_2 \geq Q_1\). In fact, in general, we see that when \(Q_{i+1} \leq Q_i(t)\) (or \(\geq\)), that \(D_{i+1} \leq D_i\) (or \(\geq\)) so that \(Q_{i+2} \geq Q_{i+1}(t)\) (or \(\leq\)). Straightforward definition chasing then leads to a telescoping set of inequalities:

\[Q_1(t) \leq Q_3(t) \leq \ldots \leq Q_2(t) \leq Q_0(t)\]

for all \(t\).

As \(Q_{2n+1} \leq Q_{2(n+1) + 1} \leq Q_0\) it follows that \(Q_{2n+1}\) converges, pointwise in \(t\), to a limiting function \(Q_-\) as \(n\to \infty\). Likewise, \(Q_{2n}\downarrow Q_+\). Clearly, \(Q_- \leq Q_+\).

It remains to prove that \(Q_-(t) = Q_+(t)\). To this end, let \(T_1 = \inf\{t\geq 0: A(t) > A(t_-)\}\), i.e, the first arrival time, and let \(T_i = \inf\{t> T_{i-1}: A(t) > A(t-) \text{ or } N_s(t) > N_s(t-)\}\), i.e., the sequence of arrivals and service completions. Clearly, for \(Q_0(t) = Q_1(t) = 0\) for \(0\leq t \leq T_1\). From the above recursions, it follows that \(Q_1(s) = Q_2(s)\) for \(s\in [T_1, T_2]\) and so on for increasing \(n\). As for any \(t\) there is an \(n\) such that \(T_{n-1} \leq t < T_n\), \(Q_-(t) = Q_+(t)\) for all \(t\).