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.

Define
\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$$.