×

3D positive lattice walks and spherical triangles. (English) Zbl 1433.05025

Summary: In this paper we explore the asymptotic enumeration of three-dimensional excursions confined to the positive octant. As shown in [D. Denisov and V. Wachtel, Ann. Probab. 43, No. 3, 992–1044 (2015; Zbl 1332.60066)], both the exponential growth and the critical exponent admit universal formulas, respectively in terms of the inventory of the step set and of the principal Dirichlet eigenvalue of a certain spherical triangle, itself being characterized by the steps of the model. We focus on the critical exponent, and our main objective is to relate combinatorial properties of the step set (structure of the so-called group of the walk, existence of a Hadamard decomposition, existence of differential equations satisfied by the generating functions) to geometric or analytic properties of the associated spherical triangle (remarkable angles, tiling properties, existence of an exceptional closed-form formula for the principal eigenvalue). As in general the eigenvalues of the Dirichlet problem on a spherical triangle are not known in closed form, we also develop a finite-elements method to compute approximate values, typically with ten digits of precision.

MSC:

05A16 Asymptotic enumeration
60G50 Sums of independent random variables; random walks
60F05 Central limit and other weak theorems

Citations:

Zbl 1332.60066
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alves, C.; Antunes, P., The method of fundamental solution applied to boundary value problems on the surface of a sphere, Comput. Math. Appl., 75, 2365-2373 (2018) · Zbl 1409.65107
[2] Bacher, A.; Kauers, M.; Yatchak, R., Continued classification of 3D lattice models in the positive octant, (Proceedings of FPSAC’16, DMTCS (2016)), 95-106 · Zbl 1440.05017
[3] Balakrishna, B., Heat equation on the cone and the spectrum of the spherical Laplacian (2013), pp. 1-16, preprint
[4] Balakrishna, B., On multi-particle Brownian survivals and the spherical Laplacian (2013), preprint, available at:
[5] Banderier, C.; Flajolet, P., Basic analytic combinatorics of directed lattice paths, Theor. Comput. Sci., 281, 37-80 (2002) · Zbl 0996.68126
[6] Bañuelos, R.; Smits, R., Brownian motion in cones, Probab. Theory Relat. Fields, 108, 299-319 (1997) · Zbl 0884.60037
[7] Bérard, P., Remarques sur la conjecture de Weyl, Compos. Math., 48, 35-53 (1983) · Zbl 0538.58037
[8] Bérard, P.; Besson, G., Spectres et groupes cristallographiques. II. Domaines sphériques, Ann. Inst. Fourier, 30, 237-248 (1980) · Zbl 0426.35073
[9] Berger, M., Geometry. II, Universitext (1987), Springer-Verlag: Springer-Verlag Berlin, Translated from the French by M. Cole and S. Levy · Zbl 0606.51001
[10] Bertoin, J.; Doney, R., On conditioning a random walk to stay nonnegative, Ann. Probab., 22, 2152-2167 (1994) · Zbl 0834.60079
[11] Bogosel, B., The method of fundamental solutions applied to boundary eigenvalue problems, J. Comput. Appl. Math., 306, 265-285 (2016) · Zbl 1338.49068
[12] Bornemann, F.; Laurie, D.; Wagon, S.; Waldvogel, J., The SIAM 100-Digit Challenge (2004), SIAM: SIAM Philadelphia PA · Zbl 1060.65002
[13] Bostan, A.; Kauers, M., Automatic classification of restricted lattice walks, (Proceedings of FPSAC’09, DMTCS (2009)), 201-215 · Zbl 1391.05026
[14] Bostan, A.; Kauers, M., The complete generating function for Gessel walks is algebraic, Proc. Am. Math. Soc., 138, 3063-3078 (2010), With an appendix by Mark van Hoeij · Zbl 1206.05013
[15] Bostan, A.; Raschel, K.; Salvy, B., Non-D-finite excursions in the quarter plane, J. Comb. Theory, Ser. A, 121, 45-63 (2014) · Zbl 1279.05003
[16] Bostan, A.; Bousquet-Mélou, M.; Kauers, M.; Melczer, S., On 3-dimensional lattice walks confined to the positive octant, Ann. Comb., 20, 661-704 (2016) · Zbl 1354.05006
[17] Bostan, A.; Bousquet-Mélou, M.; Melczer, S., On walks with large steps in an orthant (2018), pp. 1-60, preprint
[18] A. Bostan, K. Raschel, B. Salvy, unpublished notes, 2012.
[19] Bourbaki, N., Éléments de mathématique. Fasc. XXXIV. Groupes et algèbres de Lie, Actualités Scientifiques et Industrielles, vol. 1337 (1968), Hermann · Zbl 0186.33001
[20] Bousquet-Mélou, M., Square lattice walks avoiding a quadrant, J. Comb. Theory, Ser. A, 144, 37-79 (2016) · Zbl 1343.05019
[21] Bousquet-Mélou, M.; Mishna, M., Walks with small steps in the quarter plane, (Algorithmic Probability and Combinatorics. Algorithmic Probability and Combinatorics, Contemp. Math., vol. 520 (2010), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 1-39 · Zbl 1209.05008
[22] Bousquet-Mélou, M.; Schaeffer, G., Walks on the slit plane, Probab. Theory Relat. Fields, 124, 305-344 (2002) · Zbl 1008.05006
[23] Chavel, I., Eigenvalues in Riemannian Geometry, Pure and Applied Mathematics, vol. 115 (1984), Academic Press, Inc.: Academic Press, Inc. Orlando, FL · Zbl 0551.53001
[24] J. Dahne, B. Salvy, Enclosing the first eigenvalue of the Laplacian on a spherical triangle, 2019, in preparation.
[25] Dauge, M., Elliptic Boundary Value Problems on Corner Domains. Smoothness and Asymptotics of Solutions, Lecture Notes in Mathematics, vol. 1341 (1988), Springer-Verlag: Springer-Verlag Berlin · Zbl 0668.35001
[26] M. Dauge, Private communication, 2017.
[27] Davydychev, A.; Delbourgo, R., A geometrical angle on Feynman integrals, J. Math. Phys., 39, 4299-4334 (1998) · Zbl 0986.81082
[28] DeBlassie, R., Exit times from cones in \(\mathbb{R}^n\) of Brownian motion, Probab. Theory Relat. Fields, 74, 1-29 (1987) · Zbl 0586.60077
[29] Denisov, D.; Wachtel, V., Random walks in cones, Ann. Probab., 43, 992-1044 (2015) · Zbl 1332.60066
[30] Dreyfus, T.; Hardouin, C.; Roques, J.; Singer, M., On the nature of the generating series of walks in the quarter plane, Invent. Math., 213, 139-203 (2018) · Zbl 1392.05007
[31] Du, D.; Hou, Q.-H.; Wang, R.-H., Infinite orders and non-D-finite property of 3-dimensional lattice walks, Electron. J. Comb., 23, 3, Article 3.38 pp. (2016) · Zbl 1344.05013
[32] Duraj, J., Random walks in cones: the case of nonzero drift, Stoch. Process. Appl., 124, 1503-1518 (2014) · Zbl 1319.60088
[33] Duraj, J.; Wachtel, V., Invariance principles for random walks in cones (2015), pp. 1-17, preprint
[34] Dziuk, G.; Elliott, C., Finite element methods for surface PDEs, Acta Numer., 22, 289-396 (2013) · Zbl 1296.65156
[35] Fayolle, G.; Iasnogorodski, R.; Malyshev, V., Random Walks in the Quarter-Plane. Algebraic Methods, Boundary Value Problems and Applications, Applications of Mathematics (New York), vol. 40 (1999), Springer-Verlag: Springer-Verlag Berlin · Zbl 0932.60002
[36] Fichera, G., Comportamento asintotico del campo elettrico e della densità elettrica in prossimità dei punti singolari della superficie conduttore, Rend. Semin. Mat. (Torino), 32, 111-143 (1973/1974) · Zbl 0318.35007
[37] Fichera, G.; Sneider, M., Distribution de la charge électrique dans le voisinage des sommets et des arêtes d’un cube, C. R. Acad. Sci. Paris Sér. A, 278, 1303-1306 (1974) · Zbl 0282.35038
[38] Fix, G., Eigenvalue approximation by the finite element method, Adv. Math., 10, 300-316 (1973) · Zbl 0257.65086
[39] Garbit, R.; Raschel, K., On the exit time from a cone for Brownian motion with drift, Electron. J. Probab., 19, 63, 1-27 (2014) · Zbl 1317.60104
[40] Garbit, R.; Raschel, K., On the exit time from a cone for random walks with drift, Rev. Mat. Iberoam., 32, 511-532 (2016) · Zbl 1346.60060
[41] (Guttmann, T., Polygons, Polyominoes and Polycubes. Polygons, Polyominoes and Polycubes, Lecture Notes in Physics, vol. 775 (2009), Springer: Springer Dordrecht) · Zbl 1162.82005
[42] T. Guttmann, Private communication, 2017.
[43] Helffer, B.; Hoffmann-Ostenhof, T.; Terracini, S., On spectral minimal partitions: the case of the sphere, (Laptev, A., Around the Research of Vladimir Maz’ya III. Around the Research of Vladimir Maz’ya III, International Mathematical Series, vol. 13 (2010), Springer: Springer New York, NY) · Zbl 1230.35072
[44] Hillairet, L.; Judge, C., Generic spectral simplicity of polygons, Proc. Am. Math. Soc., 137, 2139-2145 (2009) · Zbl 1169.58007
[45] Kanschat, G., Finite Element Methods for Variational Eigenvalue Problems, Contemp. Math., vol. 700 (2017), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI · Zbl 1385.65056
[46] Kato, T., Perturbation Theory for Linear Operators (1976), Springer-Verlag: Springer-Verlag Berlin-New York · Zbl 0342.47009
[47] M. Kauers, Private communication, 2017.
[48] Kauers, M.; Wang, R.-H., Lattice walks in the octant with infinite associated groups, (Proceedings of EUROCOMB 2017. Proceedings of EUROCOMB 2017, Electronic Notes in Discrete Mathematics, vol. 61 (2017)), 703-709 · Zbl 1378.05008
[49] Kauers, M.; Yatchak, R., Walks in the quarter plane with multiple steps, (Proceedings of FPSAC’15, DMTCS (2015)), 25-36 · Zbl 1335.05012
[50] Kurkova, I.; Raschel, K., 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
[51] Lejay, A.; Maire, S., Computing the principal eigenvalue of the Laplace operator by a stochastic method, Math. Comput. Simul., 73, 351-363 (2007) · Zbl 1110.65105
[52] Mustapha, S., Non-D-finite walks in a three-quadrant cone, Ann. Comb., 23, 143-158 (2019) · Zbl 1414.05030
[53] Raschel, K.; Trotignon, A., On walks avoiding a quadrant, Electron. J. Comb., 26, Article 3.31 pp. (2019) · Zbl 1418.05011
[54] Ratzkin, J.; Treibergs, A., A Payne-Weinberger eigenvalue estimate for wedge domains on spheres, Proc. Am. Math. Soc., 137, 2299-2309 (2009) · Zbl 1169.53029
[55] Ratzkin, J.; Treibergs, A., A capture problem in Brownian motion and eigenvalues of spherical domains, Trans. Am. Math. Soc., 361, 391-405 (2009) · Zbl 1156.60067
[56] Schwarz, H., Ueber diejenigen Fälle, in welchen die Gaussische hypergeometrische Reihe eine algebraische Function ihres vierten Elementes darstellt, J. Reine Angew. Math., 75, 292-335 (1873) · JFM 05.0146.03
[57] Walden, H., Solution of an eigenvalue problem for the Laplace operator on a spherical surface (1974), NASA/Goddard Space Flight Center, Document No. X-582-74-41
[58] Walden, H.; Kellogg, R., Numerical determination of the fundamental eigenvalue for the Laplace operator on a spherical domain, J. Eng. Math., 11, 299-318 (1977) · Zbl 0367.65062
[59] Yatchak, R., Automated positive part extraction for lattice path generating functions in the octant, (Proceedings of EUROCOMB 2017. Proceedings of EUROCOMB 2017, Electronic Notes in Discrete Mathematics, vol. 61 (2017)), 1061-1067 · Zbl 1378.05011
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.