×

On walks avoiding a quadrant. (English) Zbl 1418.05011

Summary: Two-dimensional (random) walks in cones are very natural both in combinatorics and probability theory: they are interesting for themselves and also because they are strongly related to other discrete structures. While walks restricted to the first quadrant have been studied a lot, the case of planar, non-convex cones – equivalent to the three-quarter plane after a linear transform – has been approached only recently. In this article we develop an analytic approach to the case of walks in three quadrants. The advantage of this method is to provide uniform treatment in the study of models corresponding to different step sets. After splitting the three quadrants in two symmetric convex cones, the method is composed of three main steps: write a system of functional equations satisfied by the counting generating function, which may be simplified into one single equation under symmetry conditions; transform the functional equation into a boundary value problem; and finally solve this problem, using a concept of anti-Tutte’s invariant. The result is a contour-integral expression for the generating function. Such systems of functional equations also appear in queueing theory with the famous Join-the-Shortest-Queue model, which is still an open problem in the non-symmetric case.

MSC:

05A15 Exact enumeration problems, generating functions
60K25 Queueing theory (aspects of probability theory)
60C05 Combinatorial probability

Software:

OEIS

References:

[1] I. Adan, J. Wessels, and W. Zijm. Analysis of the asymmetric shortest queue problem. Queueing Systems Theory Appl., 8(1):1-58, 1991. · Zbl 0719.60107
[2] C. Banderier and M. Wallner. Lattice paths with catastrophes. Discrete Math. Theor. Comput. Sci., 19(1):Paper No. 23, 32, 2017. · Zbl 1400.05022
[3] N. R. Beaton, A. L. Owczarek, and A. Rechnitzer. Exact solution of some quarter plane walks with interacting boundaries.arXiv:1807.08853, 2018. · Zbl 1420.05010
[4] O. Bernardi, M. Bousquet-Mélou, and K. Raschel. Counting quadrant walks via Tutte’s invariant method.arXiv:1708.08215, 2017. · Zbl 1498.05012
[5] A. Bostan, M. Bousquet-Mélou, and S. Melczer. Counting walks with large steps in an orthant.arXiv:1806.00968, 2018. · Zbl 1467.05012
[6] A. Bostan, F. Chyzak, M. van Hoeij, M. Kauers, and L. Pech. Hypergeometric expressions for generating functions of walks with small steps in the quarter plane. European J. Combin., 61:242-275, 2017. the electronic journal of combinatorics 26(3) (2019), #P3.3126 · Zbl 1352.05013
[7] A. Bostan and M. Kauers. The complete generating function for Gessel walks is algebraic. Proc. Amer. Math. Soc., 138(9):3063-3078, 2010. With an appendix by M. van Hoeij. · Zbl 1206.05013
[8] A. Bostan, K. Raschel, and B. Salvy. Non-D-finite excursions in the quarter plane. J. Combin. Theory Ser. A, 121:45-63, 2014. · Zbl 1279.05003
[9] A. Bouaziz, S. Mustapha, and M. Sifi. Discrete harmonic functions on an orthant in d. Electron. Commun. Probab., 20:no. 52, 13, 2015. Z · Zbl 1332.60067
[10] M. Bousquet-Mélou. An elementary solution of Gessel’s walks in the quadrant. Adv. Math., 303:1171-1189, 2016. · Zbl 1351.05017
[11] M. Bousquet-Mélou. Square lattice walks avoiding a quadrant. J. Combin. Theory Ser. A, 144:37-79, 2016. · Zbl 1343.05019
[12] M. Bousquet-Mélou and M. Mishna. Walks with small steps in the quarter plane. In Algorithmic probability and combinatorics, volume 520 of Contemp. Math., pages 1-39. Amer. Math. Soc., Providence, RI, 2010. · Zbl 1209.05008
[13] M. Buchacher and M. Kauers. Inhomogeneous restricted lattice walks. Sém. Lothar. Combin., 82B:Art. 75, 12, 2019. · Zbl 1435.05010
[14] T. Budd. Winding of simple walks on the square lattice.arXiv:1709.04042, 2017. · Zbl 1471.60064
[15] J. Cohen and O. Boxma. Boundary value problems in queueing system analysis, volume 79 of North-Holland Mathematics Studies. North-Holland Publishing Co., Amsterdam, 1983. · Zbl 0515.60092
[16] D. Denisov and V. Wachtel. Random walks in cones. Ann. Probab., 43(3):992-1044, 2015. · Zbl 1332.60066
[17] T. Dreyfus, C. Hardouin, J. Roques, and M. Singer. On the nature of the generating series of walks in the quarter plane. Invent. Math., 213(1):139-203, 2018. · Zbl 1392.05007
[18] J. Duraj. Random walks in cones: the case of nonzero drift. Stochastic Process. Appl., 124(4):1503-1518, 2014. · Zbl 1319.60088
[19] P. Duren. Univalent functions, volume 259 of Grundlehren der Mathematischen Wissenschaften. Springer-Verlag, New York, 1983. · Zbl 0514.30001
[20] G. Fayolle. Méthodes analytiques pour les files d’attente couplées. Doctorat d’État ès Sciences Mathématiques, Université Paris VI, Novembre 1979.
[21] G. Fayolle and R. Iasnogorodski.Two coupled processors: the reduction to a Riemann-Hilbert problem. Z. Wahrsch. Verw. Gebiete, 47(3):325-351, 1979. · Zbl 0395.68032
[22] G. Fayolle, R. Iasnogorodski, and V. Malyshev. Random walks in the quarter plane, volume 40 of Probability Theory and Stochastic Modelling. Springer, Cham, second edition, 2017. Algebraic methods, boundary value problems, applications to queueing systems and analytic combinatorics. · Zbl 1386.60004
[23] G. Fayolle and K. Raschel. Some exact asymptotics in the counting of walks in the quarter plane. In 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA’12), Discrete Math. Theor. Comput. Sci. Proc., AQ, pages 109-124. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2012. the electronic journal of combinatorics 26(3) (2019), #P3.3127 · Zbl 1296.60111
[24] G. Fayolle and K. Raschel. About a possible analytic approach for walks in the quarter plane with arbitrary big jumps. C. R. Math. Acad. Sci. Paris, 353(2):89-94, 2015. · Zbl 1319.60090
[25] R. Foley and D. McDonald. Join the shortest queue: stability and exact asymptotics. Ann. Appl. Probab., 11(3):569-607, 2001. · Zbl 1016.60078
[26] F. D. Gakhov. Boundary value problems. Dover Publications, Inc., New York, 1990. Translated from the Russian, Reprint of the 1966 translation. · Zbl 0830.30026
[27] R. Iasnogorodski. Problèmes frontières dans les files d’attente. Doctorat d’État ès Sciences Mathématiques, Université Paris VI, Novembre 1979.
[28] OEIS Foundation Inc. The on-line encyclopedia of integer sequences, http://oeis.org.
[29] I. Kurkova and K. Raschel. Explicit expression for the generating function counting Gessel’s walks. Adv. in Appl. Math., 47(3):414-433, 2011. · Zbl 1234.05027
[30] I. Kurkova and K. Raschel. On the functions counting walks with small steps in the quarter plane. Publ. Math. Inst. Hautes Études Sci., 116:69-114, 2012. · Zbl 1255.05012
[31] I. Kurkova and Y. Suhov. Malyshev’s theory and JS-queues. Asymptotics of stationary probabilities. Ann. Appl. Probab., 13(4):1313-1354, 2003. · Zbl 1039.60082
[32] J. Lu. Boundary value problems for analytic functions, volume 16 of Series in Pure Mathematics. World Scientific Publishing Co., Inc., River Edge, NJ, 1993. · Zbl 0818.30027
[33] V. Malyshev. An analytic method in the theory of two-dimensional positive random walks. Sibirsk. Mat. Ž., 13:1314-1329, 1421, 1972.
[34] M. Mishna and A. Rechnitzer. Two non-holonomic lattice walks in the quarter plane. Theoret. Comput. Sci., 410(38-40):3616-3630, 2009. · Zbl 1228.05038
[35] M. Mishna and S. Simon. Private communication. 2018.
[36] S. Mustapha. Non-D-finite walks in a three-quadrant cone. Ann. Comb., 23(1):143- 158, 2019. · Zbl 1414.05030
[37] K. Raschel. Counting walks in a quadrant: a unified approach via boundary value problems. J. Eur. Math. Soc. (JEMS), 14(3):749-777, 2012. · Zbl 1238.05014
[38] W. Tutte. Chromatic sums revisited. Aequationes Math., 50(1-2):95-134, 1995. · Zbl 0842.05031
[39] R. Xu, N. R. Beaton, and A. L. Owczarek. Quarter-plane lattice paths with interacting boundaries: Kreweras and friends. Sém. Lothar. Combin., 82B:Art. 26, 12, 2019. AExpression and properties of conformal gluing functions A crucial ingredient in our main results (Theorems 6 and 7) is the function w(y), which we interpret as a conformal mapping from the domain GLonto a complex plane cut along an interval, see Section 2.4. In this appendix, we recall from [37, 4] an explicit expression as well as some analytic properties of this function, first in the finite group case, then for infinite group models. the electronic journal of combinatorics 26(3) (2019), #P3.3128
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.