This paper derives recursive algorithms for efficiently computing event probabilities related to order statistics and applies the results in a queue inferencing setting. Consider a net of N independent, identically distributed random variables in [0, 1]. When the experimental values of the random variables are arranged in ascending order from smallest to largest, one has the order statistics of the set of random variables. Both a forward and a backward recursive O(N3) algorithm are developed for computing the probability that the order statistics vector lies in a given N-rectangle. The new algorithms have applicability in inferring the statistical behavior of Poisson arrival queues, given only the start and stop times of service of all N customers served in a period of continuous congestion. The queue inference results extend the theory of the ‘Queue Inference Engine’ (QIE), originally developed by Larson in 1990. The methodology is extended to a third O(N3) algorithm, employing both forward and backward recursion, that computes the conditional average probability (averaged over all N customers in a congestion period) that the in-queue wait is less than t minutes, given the departure time data and assuming first come, first served service. To our knowledge, this result is the first O(N3) exact algorithm for computing points on the in-queue waiting time distribution function, conditioned on the start and stop time data. The paper concludes with an extension to the computation of certain correlations of in-queue waiting times. Illustrative computational results are included throughout.
