Ross's conjecture

In queueing theory, 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.^[1] Equality can be obtained in the bound; and the bound does not hold for finite buffer queues.^[2]

Bound

Ross's conjecture is a bound for the mean delay in a queue where arrivals are governed by a doubly stochastic Poisson process ^[3] or by a non-stationary Poisson process.^[1][4] The conjecture states that the average amount of time that a customer spends waiting in a queue is greater than or equal to

$\frac{\lambda \operatorname E (S^2)}{2 \{1-\lambda \operatorname E (S) \}}$

where S is the service time and λ is the average arrival rate (in the limit as the length of the time period increases).^[1]

References

1. Rolski, Tomasz (1981), "Queues with non-stationary input stream: Ross's conjecture", Advances in Applied Probability 13 (3): 603–618, doi:10.2307/1426787, JSTOR 1426787, MR 615953.
2. Heyman, D. P. (1982), "On Ross's conjectures about queues with non-stationary Poisson arrivals", Journal of Applied Probability 19 (1): 245–249, doi:10.2307/3213936, JSTOR 3213936, MR 644439.
3. Huang, J. (1991), "A Study on Queuing Theory and Teletraffic Models (Part 1 of 3)", Ph.D Dissertation (1), doi:10.13140/RG.2.1.1259.6329.
4. Ross, Sheldon M. (1978), "Average delay in queues with non-stationary Poisson arrivals", Journal of Applied Probability 15 (3): 602–609, doi:10.2307/3213122, JSTOR 3213122, MR 0483101.