The Wei–Norman method for the infinite-server queue with phase-type arrivals

In 1964, Wei and Norman [11] showed that a system of linear differential equations with non-constant coefficients can under certain conditions be translated into another possibly simpler system of equations. The Wei–Norman method finds many applications throughout science but has not been used much in applied probability. (Exception are [4, 6] and [7].) We propose as an application the \(PH/G/\infty \) infinite server queue with phase-type arrivals and general service time distribution. Denoting \(X_t\) the process counting the customers in the system and \(J_t\) the current phase of the arrival process at time t, it has been shown in [8] that the matrix of generating functions G(t) given byfulfills a system of nonlinear differential equations, namelyHere, the matrices A and B and the scalar function f are defined as follows. The arrival distribution is assumed to be continuous phase-type (see, e.g., [2]), coinciding with the distribution of the absorption time of a continuous-time Markov chain on the state space \(\{1,2,\ldots ,n,n+1\}\) with generator matrix \({\left[ {\begin{matrix} {T}&{}{t}\\ {0}&{}0 \end{matrix}}\right] }\). The \(n\times n\) matrix \({T}\) has non-positive entries in the diagonal and non-negative entries offside the diagonal. The column vector \({t}\) is such that the row sums of the generator matrix are zero. With \(q=(q_1,\ldots ,q_{n})^{{\mathsf {T}}}\) the vector of the initial probabilities, we then define \(B=t\cdot q^{{\mathsf {T}}}\) and \({A}={T}+B\). Finally, \(f(t)=(z-1)(1-H(t))\), with H the cdf of the service time distribution.

If \({A}\) and \({B}\) commute or f is constant, then \({A}+f(s){B}\) and \({A}+f(t){B}\) commute for any combination of \(s,t\ge 0\) and we readily find a solution of (2) by means of the matrix exponential, namely \({G}(t)=e^{\int _0^t ({A}+f(s){B})\,ds}\). However, if the commutator \( AB:={A}{B}-{B}{A}\) is not zero, then this is no longer true. For example, in the \(E_2/G/\infty \) queue, where the interarrival distribution is Erlang-2, we have (with \(q_1=1\))and it follows that \({A}{B}=\lambda ^2{\left[ {\begin{matrix} 1&{}0\\ 0&{}-1 \end{matrix}}\right] }\not =0\).

Suppose that there are m matrices \({M}_{i}\) (henceforth called ‘basis’) such that \([{M}_{i},{M}_{j}]\) is itself a linear combination of basis elements for every \(i,j=1,2,\ldots ,m\) and \({A}\) and \({B}\) are expressible as linear combinations of the identity matrix I and the \({M}_{i}\). Then, it is shown in [11] that at least locally around \(t=0\) one has the product representationThe functions \(g_i,i=1,\ldots ,m\) fulfill a system of—hopefully easier or more insightful—differential equations.

We will briefly demonstrate the idea with the above E\(_2\)/G/\(\infty \) example. Here, we can choose the basis \({M}_{1}={\left[ {\begin{matrix} 1&{}0 \\ 0&{}-1 \end{matrix}}\right] }\), \({M}_{2}={\left[ {\begin{matrix} 0&{}1 \\ 0&{}0 \end{matrix}}\right] }\) and \({M}_{3}={\left[ {\begin{matrix} 0&{}0\\ -1&{}0 \end{matrix}}\right] }\), with \([{M}_{1},{M}_{2}]=-2{M}_{2}\), \([{M}_{1},{M}_{3}]=2{M}_{3}\) and \([{M}_{2},{M}_{3}]={M}_{1}\). We then express \({A}\) and \({B}\) in (3) in terms of the identity matrix \({I}\) and the basis elements as \({A}=-\lambda {I}+\lambda {M}_{2}-\lambda {M}_{3}\) and \({B}=-\lambda {M}_{3}\). It can be shown that with this choice of the basis we obtain the system (cf. [3, 10])where the dependence on t was omitted. After some rearrangements and setting \(R(t)=g_1(t)'\), we obtain the Riccati equationwhich is still difficult to solve, but once a solution R is found, \(g_1,g_2\) and \(g_3\) follow by integration.

There are still considerable problems and many open questions related to this approach.

The Norman–Wei method is clearly not restricted to this particular application. After all, similar systems of differential equations are quite common in applied probability. The Kolmogorov forward equation for time-inhomogeneous CTMCs is an immediate example. (See also the application for birth-and-death processes in [7] and more general jump processes in [1].) As in the \(PH/G/\infty \) setting, the primary question is how the structure of the problem at hand influences the choice of the basis and thereby the form of the new system of differential equations. In case of the Kolmogorov equation, it would be interesting which generator matrices are related to which Lie algebras ([9] goes into this direction). We note that there is a second algebraic approach complementing the Wei–Norman method, namely the apparently more popular Magnus expansion that searches for representations of G(t) of the form \(e^{\sum _{i=1}^{m} g_i(t){M}_{i}}\) (see, e.g., [5], where also the Wei–Norman approach is mentioned). This approach could also be worthwhile to investigate in connection with queuing problems such as the one presented here.