In
queueing theory
Queueing theory is the mathematical study of waiting lines, or queues. A queueing model is constructed so that queue lengths and waiting time can be predicted. Queueing theory is generally considered a branch of operations research because the ...
, a discipline within the mathematical theory of probability, Ross's conjecture gives a lower bound for the average waiting-time experienced by a customer when arrivals to the queue do not follow the simplest model for random arrivals. It was proposed by
Sheldon M. Ross Sheldon M. Ross is the Daniel J. Epstein Chair and Professor at the USC Viterbi School of Engineering. He is the author of several books in the field of probability.
Biography
Ross received his B. S. degree in mathematics from Brooklyn College i ...
in 1978 and proved in 1981 by Tomasz Rolski.
Equality can be obtained in the bound; and the bound does not hold for finite buffer queues.
Bound
Ross's conjecture is a bound for the mean delay in a queue where arrivals are governed by a
doubly stochastic Poisson process[.]
or by a non-stationary
Poisson process
In probability, statistics and related fields, a Poisson point process is a type of random mathematical object that consists of points randomly located on a mathematical space with the essential feature that the points occur independently of one ...
.
[.][.] The conjecture states that the average amount of time that a customer spends waiting in a queue is greater than or equal to
::
where ''S'' is the service time and λ is the average arrival rate (in the limit as the length of the time period increases).
References
Probabilistic inequalities
Queueing theory
{{probability-stub