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 W1,…, WN of customers within a busy period of length N are computed efficiently by exploiting an embedded Markov chain. All first moments E(Wk| data from busy period of length N) are computed in O(N³) multiplications; finding the distributions of all Wk 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 as or faster than all known algorithms, and address a broader range of performance measures than the extant literature.