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 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 In probability theory, a Cox process, also known as a doubly stochastic Poisson process is a point process which is a generalization of a Poisson process where the intensity that varies across the underlying mathematical space (often space or time) ...

. 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 ::

\frac

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