×

Robust queueing theory: an initial study using imprecise probabilities. (English) Zbl 1334.60199

Summary: We study the robustness of performance predictions of discrete-time finite-capacity queues by applying the framework of imprecise probabilities. More concretely, we consider the \(\mathrm{Geo}/\mathrm{Geo}/1/L\) model with probabilities of arrival and departure that are no longer fixed, but are allowed to vary within given intervals. We distinguish between two concepts of independence in this framework, namely repetition independence and epistemic irrelevance. In the first approach, we assume the existence of time-homogeneous probabilities for arrival and departure, which leads us to consider a collection of stationary queues. In the second, the stationarity assumption is dropped and we allow the arrival and departure probabilities to vary from time point to time point; they may even depend on the complete history of queue lengths. We calculate bounds on the expected queue length, the probability of a particular queue length and the probability of turning on the server. For the expected queue length, both approaches coincide. For the other performance measures, we observe and discuss various differences between the bounds obtained for these two approaches. One of our observations is that ergodicity may break down due to imprecision: bounds on expected time averages of certain functions on the state space are not necessarily equal to the bounds on the expectation of that function at random instants in a steady-state queue.

MSC:

60K25 Queueing theory (aspects of probability theory)
60G20 Generalized stochastic processes
90B22 Queues and service in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
37A50 Dynamical systems and their relations with probability theory and stochastic processes
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alfa, A.S.: Queueing Theory for Telecommunications: Discrete Time Modelling of a Single Node System, 1st edn. Springer, New York (2010) · Zbl 1211.90001 · doi:10.1007/978-1-4419-7314-6
[2] Altman, E., Avrachenkov, K.E., Núñez-Queija, R.: Perturbation analysis for denumerable Markov chains with application to queueing models. Adv. Appl. Prob. 36, 839-853 (2004) · Zbl 1062.60066 · doi:10.1239/aap/1093962237
[3] Augustin, T., Coolen, F.P., De Cooman, G., Troffaes, M.C. (eds.): Introduction to Imprecise Probabilities. Wiley (2014) · Zbl 1290.62003
[4] Boole, G.: Studies in Logic and Probability. Dover Publications, Mineola (2004, reprint of the work originally published by Watts & Co., London, in 1952) · Zbl 0049.00802
[5] Bucklew, J.A., Ney, P., Sadowsky, J.S.: Monte Carlo simulation and large deviations theory for uniformly recurrent Markov chains. J. Appl. Prob. 27, 44-59 (1990) · Zbl 0702.60028 · doi:10.2307/3214594
[6] Cao, X.R., Chen, H.F.: Perturbation realization, potentials, and sensitivity analysis of Markov processes. IEEE Trans. Autom. Control 42(10), 1382-1393 (1997) · Zbl 0889.93039 · doi:10.1109/9.633827
[7] Chaudhry, M.L.: On numerical computations of some discrete-time queues. In: Computational Probability, Chap. 10, pp. 365-408. Springer (2000) · Zbl 0945.65009
[8] Couso, I., Moral, S., Walley, P.: A survey of concepts of independence for imprecise probabilities. Risk Decis. Policy 5(02), 165-181 (2000) · doi:10.1017/S1357530900000156
[9] De Cooman, G., De Bock, J., Lopatatzidis, S.: A pointwise ergodic theorem for imprecise Markov chains. In: Augustin, T., Doria, S., Miranda, E., Quaeghebeur E. (eds.) ISIPTA ’15—Proceedings of the Ninth International Symposium on Imprecise Probability: Theories and Applications, pp. 107-116. Aracne Editrice (2015) · Zbl 0834.62004
[10] De Cooman, G., Hermans, F., Antonucci, A., Zaffalon, M.: Epistemic irrelevance in credal networks: the case of imprecise Markov trees. In: Augustin, T., Coolen, F.P.A., Moral, S., Troffaes, M.C.M. (eds.) ISIPTA ’09—Proceedings of the Sixth International Symposium on Imprecise Probability: Theories and Applications, pp. 149-158. SIPTA, SIPTA, Durham,(2009). http://www.sipta.org/isipta09/proceedings/053.html · Zbl 1348.68248
[11] De Cooman, G., Hermans, F., Quaeghebeur, E.: Imprecise Markov chains and their limit behaviour. Prob. Eng. Inf. Sci. 23(4), 597-635 (2009). doi:10.1017/S0269964809990039. arXiv:0801.0980 · Zbl 1183.60026 · doi:10.1017/S0269964809990039
[12] De Bock, J., De Cooman, G.: An efficient algorithm for estimating state sequences in imprecise hidden Markov models. J. Artif. Intell. Res. 50, 189-233 (2014) · Zbl 1361.68256
[13] Gross, D., Shortle, J.F., Thompson, J.M., Harris, C.M.: Fundamentals of Queueing Theory. Wiley, New York (2013) · Zbl 1151.60001
[14] Hermans, F., De Cooman, G.: Characterisation of ergodic upper transition operators. Int. J. Approximate Reasoning 53(4), 573-583 (2012). doi:10.1016/j.ijar.2011.12.008 · Zbl 1287.60086 · doi:10.1016/j.ijar.2011.12.008
[15] Kemeny, J.G., Snell, J.L.: Finite Markov Chains. Undergraduate Text in Mathematics. Springer, New York (1976). Reprint of the 1960 Edition · Zbl 0328.60035
[16] Keynes, J.M.: A Treatise on Probability. Macmillan, London (1921)
[17] Levi, I.: The Enterprise of Knowledge. MIT Press, London (1980)
[18] Quaeghebeur, E.: Learning from samples using coherent lower previsions. Ph.D. thesis, Ghent University (2008)
[19] Rubinstein, R.Y.: Optimization of computer simulation models with rare events. Eur. J. Oper. Res. 99(1), 89-112 (1997) · Zbl 0923.90051 · doi:10.1016/S0377-2217(96)00385-2
[20] Schweitzer, P.J.: Perturbation theory and finite Markov chains. J. Appl. Prob. 5, 401-413 (1968) · Zbl 0196.19803 · doi:10.2307/3212261
[21] Seidenfeld, T., Schervish, M.J., Kadane, J.B.: Rethinking the Foundations of Statistics. Cambridge University Press, Cambridge (1999) · Zbl 0966.62002
[22] Shafer, G.: A Mathematical Theory of Evidence. Princeton University Press, Princeton (1976) · Zbl 0359.62002
[23] Shafer, G.: The Art of Causal Conjecture. The MIT Press, Cambridge (1996) · Zbl 0874.60003
[24] Smith, C.A.B.: Consistency in statistical inference and decision. J. Royal Stat. Soc. A 23, 1-37 (1961) · Zbl 0124.09603
[25] Troffaes, M.C.M., De Cooman, G.: Lower Previsions. Wiley, New York (2014)
[26] Škulj, D., Hable, R.: Coefficients of ergodicity for Markov chains with uncertain parameters. Metrika 76(1), 107-133 (2013). doi:10.1007/s00184-011-0378-0 · Zbl 1272.60052 · doi:10.1007/s00184-011-0378-0
[27] Walley, P.: Statistical Reasoning with Imprecise Probabilities. Chapman and Hall, London (1991) · Zbl 0732.62004 · doi:10.1007/978-1-4899-3472-7
[28] Walley, P.: Inferences from multinomial data: learning about a bag of marbles. J. Royal Stat. Soc. B 58, 3-57 (1996). With discussion · Zbl 0834.62004
[29] Walley, P.: Towards a unified theory of imprecise probability. Int. J. Approximate Reasoning 24, 125-148 (2000) · Zbl 1007.28015 · doi:10.1016/S0888-613X(00)00031-1
[30] Weichselberger, K.: The theory of interval-probability as a unifying concept for uncertainty. Int. J. Approximate Reasoning 24, 149-170 (2000) · Zbl 0995.68123 · doi:10.1016/S0888-613X(00)00032-3
[31] White, J.A.: Analysis of Queueing Systems. Elsevier, Amsterdam (2012)
[32] Whittle, P.: Probability Via Expectation, 4th edn. Springer, New York (2000) · Zbl 0980.60004 · doi:10.1007/978-1-4612-0509-8
[33] Williams, P.M.: Notes on conditional previsions. Technical report, School of Mathematical and Physical Science, University of Sussex (1975). Revised journal version: [35] · Zbl 1114.60005
[34] Williams, P.M.: Indeterminate probabilities. In: M. Przelecki, K. Szaniawski, R. Wojcicki (eds.) Proceedings of a 1974 Conference Held in Warsaw. Formal Methods in the Methodology of Empirical Sciences, pp. 229-246. Reidel, Dordrecht (1976) · Zbl 0395.60003
[35] Williams, P.M.: Notes on conditional previsions. Int. J. Approximate Reasoning 44, 366-382 (2007). Revised journal version of [33] · Zbl 1114.60005
[36] Xia, L., Cao, X.R.: Performance optimization of queueing systems with perturbation realization. Eur. J. Oper. Res. 218, 293-304 (2012) · Zbl 1244.90070 · doi:10.1016/j.ejor.2011.07.039
[37] Zadeh, L.A.: Fuzzy sets. Inf. Control 8(3), 338-353 (1965) · Zbl 0139.24606 · doi:10.1016/S0019-9958(65)90241-X
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.