Estimating Waiting Times from Transactional Data

Given transactional data consisting of service starting and finishing times in a queuing system with a Poisson arrival process and service in order of arrival, the distributions and moments of waiting times W₁, …, W_N, of customers within a busy period of length N are computed efficiently by exploiting an embedded Markov chain. All first moments E(W_k ∣ data from busy period of length N) are computed in O(N³) multiplications; finding the distributions of all W_k on a set of n prespecified times requires O(nN³) multiplications; finding all rth order moments needs O(rN⁴) multiplications. The algorithms described are all new, as fast or faster than all known algorithms, and address a broader range of performance measures than the extant literature.