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

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

gollark: To be honest Perl regexes probably can parse HTML, but they are also probably TC.
gollark: It encourages people to keep doing their silly standard-violating things because they technically *work*, and makes your parsing logic more complex and flaky.
gollark: And they *do* handle it, because at some point down the line someone thought making it compatible was better than encouraging people to NOT DO REALLY STUPID UNPARSEABLE THINGS.
gollark: A few websites will just go "Standards? What are they?" and ignore the standards and then just expect parsers to handle it anyway.
gollark: Technically HTML isn't even parseable with XML parsers because it is for some TRIANGULAR reason a weird SGML subset.

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 0615953.
  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 0644439.
  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.


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.