| Título: | Efficient Computation of Probabilities of Events Described by Order Statistics and Applications to Queue Inference |
| Autores: |
Jones, Lee K. Larson, Richard C., 1943- |
| Fecha: |
2004-05-28 2004-05-28 1994-03 |
| Publicador: | MIT |
| Fuente: |
 |
| Tipo: | Working Paper |
| Tema: | order statistics, queues, inference, computational probability. |
| Descripción: | 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 set of N i.i.d. 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 [8]. The methodology is extended to a third O(N 3 ) algorithm, employing both forward and backward recursion, that computes the conditional probability that a random customer of the N served waited in queue less than r minutes, given the observed customer departure times 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. |
| Idioma: | Inglés |
1 Problem Investigation in High-Hazard Industries: Creating and Negotiational Learning por Hatakenaka, Sachi,Rudolph, Jenny,Carroll, John S. | 6 Trade Linkages and Output-Multiplier Effects: A Structural VAR por Forbes, Kristin J.,Abeysinghe, Tilak |
2 Global sourcing in the automotive supply chain:The case of Fiat Auto por Volpato, Giuseppe,Camuffo, Arnaldo | 7 Description Of Procedures In Automotive Engine Plants por Artzner, Denis,Whitney, Dr. Daniel |
3 Reading Courtesy Amounts on Handwritten Paper Checks por Palacios, Rafael,Wang, Patrick S.P.,Gupta, Amar | 8 Mobility Issues in the Developing World por Gakenheimer, Ralph |
4 On Trees and Logs por Pavlova, Anna,Cass, David | 9 Saturn, The GM/UAW Partnership por Rubinstein, Saul,Kochan, Thomas |
5 Academic Earmarks and the Returns to Lobbying por De Figueiredo, John M.,Silverman, Brian S. | 10 Toward a Stakeholder Theory of the Firm: The Case of the Saturn Partnership por Kochan, Thomas,Rubinstein, Saul |