zbMATH — the first resource for mathematics

Approximation of excessive backlog probabilities of two tandem queues. (English) Zbl 1401.60081
Summary: Let \(X\) be the constrained random walk on \(\mathbb Z_+^2\) having increments \((1,0)\), \((-1,1)\), and \((0,-1)\) with respective probabilities \(\lambda\), \(\mu_1\), and \(\mu_2\) representing the lengths of two tandem queues. We assume that \(X\) is stable and \(\mu_1\neq\mu_2\). Let \(\tau_n\) be the first time when the sum of the components of \(X\) equals \(n\). Let \(Y\) be the constrained random walk on \(\mathbb Z\times\mathbb Z_+\) having increments \((-1,0)\), \((1,1)\), and \((0,-1)\) with probabilities \(\lambda\), \(\mu_1\), and \(\mu_2\). Let \(\tau\) be the first time that the components of \(Y\) are equal to each other. We prove that \(P_{n-x_n(1),x_n(2)}(\tau<\infty)\) approximates \(p_n(x_n)\) with relative error exponentially decaying in \(n\) for \(x_n=\lfloor nx\rfloor\), \(x \in\mathbb R_+^2\), \(0<x(1)+x(2)<1\), \(x(1)>0\). An affine transformation moving the origin to the point (\(n,0\)) and letting \(n\rightarrow\infty\) connect the \(X\) and \(Y\) processes. We use a linear combination of basis functions constructed from single and conjugate points on a characteristic surface associated with \(X\) to derive a simple expression for \(\mathbb P_y(\tau<\infty)\) in terms of the utilization rates of the nodes. The proof that the relative error decays exponentially in \(n\) uses a sequence of subsolutions of a related Hamilton-Jacobi-Bellman equation on a manifold consisting of three copies of \(\mathbb R_+^2\) glued to each other along the constraining boundaries. We indicate how the ideas of the paper can be generalized to more general processes and other exit boundaries.

60G50 Sums of independent random variables; random walks
60K25 Queueing theory (aspects of probability theory)
60G40 Stopping times; optimal stopping problems; gambling theory
60F10 Large deviations
60J45 Probabilistic potential theory
Full Text: DOI arXiv
[1] Asmussen, S., Applied Probability and Queues, (2003), Springer: Springer, New York · Zbl 1029.60001
[2] Asmussen, S.; Glynn, P. W., Stochastic Simulation: Algorithms and Analysis, (2007), Springer: Springer, New York · Zbl 1126.65001
[3] Atar, R.; Dupuis, P., Large deviations and queueing networks: methods for rate function identification, Stoch. Process. Appl., 84, 255-296, (1999) · Zbl 0996.60036
[4] Blanchet, J., Optimal sampling of overflow paths in Jackson networks, Math. Operat. Res., 38, 698-719, (2013) · Zbl 1291.65010
[5] Blanchet, J. H.; Leder, K.; Glynn, P. W., Monte Carlo and Quasi-Monte Carlo Methods 2008, Efficient simulation of light-tailed sums: an old-folk song sung to a faster new tune, 227-258, (2008), Springer: Springer, Berlin · Zbl 1191.65002
[6] Borovkov, A. A.; Mogul’Skiĭ, A. A., Large deviations for Markov chains in the positive quadrant, Russian Math. Surveys, 56, 803-916, (2001) · Zbl 1068.60034
[7] Chen, H.; Yao, D. D., Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization, (2001), Springer: Springer, New York · Zbl 0992.60003
[8] Comets, F.; Delarue, F.; Schott, R., Distributed algorithms in an ergodic Markovian environment, Random Structures Algorithms, 30, 131-167, (2007) · Zbl 1178.68663
[9] Dai, J. G.; Miyazawa, M., Reflecting Brownian motion in two dimensions: exact asymptotics for the stationary distribution, Stoch. Systems, 1, 146-208, (2011) · Zbl 1291.60168
[10] De Boer, P.-T., Analysis of state-independent importance-sampling measures for the two-node tandem queue, ACM Trans. Model. Comput. Simul., 16, 225-250, (2006) · Zbl 1390.90270
[11] Dean, T.; Dupuis, P., Splitting for rare event simulation: a large deviation approach to design and analysis, Stoch. Process. Appl., 119, 562-587, (2009) · Zbl 1157.60019
[12] Dupuis, P.; Ellis, R. S., A Weak Convergence Approach to the Theory of Large Deviations, (1997), John Wiley: John Wiley, New York · Zbl 0904.60001
[13] Dupuis, P.; Ellis, R. S., The large deviation principle for a general class of queueing systems. I, Trans. Amer. Math. Soc., 347, 2689-2751, (1995) · Zbl 0869.60022
[14] Dupuis, P.; Wang, H., Importance sampling, large deviations, and differential games, Stoch. Stoch. Reports, 76, 481-508, (2004) · Zbl 1076.65003
[15] Dupuis, P.; Wang, H., Subsolutions of an Isaacs equation and efficient schemes for importance sampling, Math. Operat. Res., 32, 723-757, (2007) · Zbl 1341.62042
[16] Dupuis, P.; Wang, H., Importance sampling for Jackson networks, Queueing Systems, 62, 113-157, (2009) · Zbl 1166.60329
[17] Dupuis, P.; Leder, K.; Wang, H., Importance sampling for sums of random variables with regularly varying tails, ACM Trans. Model. Comput. Simul., 17, (2007) · Zbl 1390.65002
[18] Dupuis, P.; Sezer, A. D.; Wang, H., Dynamic importance sampling for queueing networks, Ann. Appl. Prob., 17, 1306-1346, (2007) · Zbl 1144.60022
[19] Durrett, R., Probability: Theory and Examples, (1996), Duxbury: Duxbury, Belmont, CA
[20] Flajolet, P., Mathematical Foundations of Computer Science, 1986, The evolution of two stacks in bounded space and random walks in a triangle, 325-340, (1986), Springer: Springer, Berlin
[21] Foley, R. D.; Mcdonald, D. R., Constructing a harmonic function for an irreducible nonnegative matrix with convergence parameter R > 1, Bull. London Math. Soc., 44, 533-544, (2012) · Zbl 1260.60154
[22] Freidlin, M. I.; Wentzell, A. D., Random Perturbations of Dynamical Systems, (2012), Springer: Springer, Heidelberg · Zbl 1267.60004
[23] Glasserman, P.; Kou, S.-G., Analysis of an importance sampling estimator for tandem queues, ACM Trans. Model. Comput. Simul., 5, 22-42, (1995) · Zbl 0841.62083
[24] Griffiths, P. A., Introduction to Algebraic Curves, (1989), American Mathematical Society: American Mathematical Society, Providence, RI
[25] Guillotin-Plantard, N.; Schott, R., Dynamic Random Walks: Theory and Applications, (2006), Elsevier: Elsevier, Amsterdam · Zbl 1103.60012
[26] Henderson, S. G.; Nelson, B. L., Handbooks in Operations Research and Management Science: Vol. 13, Simulation, (2006), North-Holland: North-Holland, Amsterdam · Zbl 1170.90300
[27] Ignatiouk-Robert, I., Large deviations of Jackson networks, Ann. Appl. Prob., 10, 962-1001, (2000) · Zbl 1073.60510
[28] Ignatiouk-Robert, I.; Loree, C., Martin boundary of a killed random walk on a quadrant, Ann. Prob., 38, 1106-1142, (2010) · Zbl 1205.60057
[29] Ignatyuk, I. A.; Malyshev, V. A.; Scherbakov, V. V., Boundary effects in large deviation problems, Russian. Math. Surveys, 49, 41-99, (1994)
[30] Juneja, S.; Nicola, V., Efficient simulation of buffer overflow probabilities in Jackson networks with feedback, ACM Trans. Model. Comput. Simul., 15, 281-315, (2005) · Zbl 1390.90224
[31] Knuth, D. E., The Art of Computer Programming, (1969), Addison-Wesley: Addison-Wesley, Reading, MA · Zbl 0191.18001
[32] Kobayashi, M.; Miyazawa, M., Matrix-Analytic Methods in Stochastic Models, Revisiting the tail asymptotics of the double QBD process: refinement and complete solutions for the coordinate and diagonal directions, 145-185, (2013), Springer: Springer, New York · Zbl 1280.60044
[33] Kurkova, I. A.; Malyshev, V. A., Martin boundary and elliptic curves, Markov Process. Relat. Fields, 4, 203-272, (1998) · Zbl 0929.60055
[34] Kushner, H. J.; Dupuis, P., Numerical Methods for Stochastic Control Problems in Continuous Time, (2001), Springer: Springer, New York · Zbl 0968.93005
[35] Louchard, G.; Schott, R., Probabilistic analysis of some distributed algorithms, Random Structures Algorithms, 2, 151-186, (1991) · Zbl 0732.68055
[36] Louchard, G.; Schott, R.; Tolley, M.; Zimmermann, P., Random walks, heat equation and distributed algorithms, J. Comput. Appl. Math., 53, 243-274, (1994) · Zbl 0820.68052
[37] Maier, R. S., Colliding stacks: a large deviations analysis, Random Structures Algorithms, 2, 379-420, (1991) · Zbl 0737.60097
[38] Maier, R. S., 1992 Lectures in Complex Systems, Large fluctuations in stochastically perturbed nonlinear systems: applications in computing, 501-517, (1993), Addison-Wesley: Addison-Wesley, Reading, MA · Zbl 0869.60105
[39] Mcdonald, D. R., Asymptotics of first passage times for random walk in an orthant, Ann. Appl. Prob., 9, 110-145, (1999) · Zbl 0937.60091
[40] Miretskiy, D.; Scheinhardt, W.; Mandjes, M., State-dependent importance sampling for a Jackson tandem network, ACM Trans. Model. Comput. Simul., 20, (2010) · Zbl 1384.90028
[41] Miyazawa, M., Tail decay rates in double QBD processes and related reflected random walks, Math. Operat. Res., 34, 547-575, (2009) · Zbl 1213.60151
[42] Miyazawa, M., Light tail asymptotics in multidimensional reflecting processes for queueing networks, TOP, 19, 233-299, (2011) · Zbl 1280.60051
[43] Ney, P.; Nummelin, E., Markov additive processes. I. Eigenvalue properties and limit theorems, Ann. Prob., 15, 561-592, (1987) · Zbl 0625.60027
[44] Nicola, V. F.; Zaburnenko, T. S., Efficient importance sampling heuristics for the simulation of population overflow in Jackson networks, ACM Trans. Model. Comput. Simul., 17, (2007) · Zbl 1390.90249
[45] Parekh, S.; Walrand, J., A quick simulation method for excessive backlogs in networks of queues, IEEE Trans. Automatic Control, 34, 54-66, (1989) · Zbl 0661.60110
[46] Revuz, D., Markov Chains, (1984), North-Holland: North-Holland, Amsterdam · Zbl 0539.60073
[47] Ridder, A., Importance sampling algorithms for first passage time probabilities in the infinite server queue, Europ. J. Operat. Res., 199, 176-186, (2009) · Zbl 1176.90131
[48] Robert, P., Stochastic Networks and Queues, (2003), Springer: Springer, Berlin
[49] Rubino, G.; Tuffin, B., Rare Event Simulation using Monte Carlo Methods, (2009), John Wiley: John Wiley, New York · Zbl 1159.65003
[50] Setayeshgar, L.; Wang, H., Efficient importance sampling schemes for a feed-forward network, ACM Trans. Model. Comput. Simul., 23, (2013) · Zbl 1358.60079
[51] Sezer, A. D., Dynamic Importance Sampling for Queueing Networks, (2006)
[52] Sezer, A. D., (2007)
[53] Sezer, A. D., Importance sampling for a Markov modulated queuing network, Stoch. Process. Appl., 119, 491-517, (2009) · Zbl 1157.60345
[54] Sezer, A. D., Asymptotically optimal importance sampling for Jackson networks with a tree topology, Queueing Systems, 64, 103-117, (2010) · Zbl 1182.90027
[55] Sezer, A. D., (2015)
[56] Sezer, A. D.; Özbudak, F., Approximation of bounds on mixed-level orthogonal arrays, Adv. Appl. Prob., 43, 399-421, (2011) · Zbl 1225.05050
[57] Yao, A. C., An analysis of a memory allocation scheme for implementing stacks, SIAM J. Comput., 10, 398-403, (1981) · Zbl 0457.68023
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.