×

Winding of simple walks on the square lattice. (English) Zbl 1471.60064

Summary: A method is described to count simple diagonal walks on \(\mathbb{Z}^2\) with a fixed starting point and endpoint on one of the axes and a fixed winding angle around the origin. The method involves the decomposition of such walks into smaller pieces, the generating functions of which are encoded in a commuting set of Hilbert space operators. The general enumeration problem is then solved by obtaining an explicit eigenvalue decomposition of these operators involving elliptic functions. By further restricting the intermediate winding angles of the walks to some open interval, the method can be used to count various classes of walks restricted to cones in \(\mathbb{Z}^2\) of opening angles that are integer multiples of \(\pi / 4\).
We present three applications of this main result. First we find an explicit generating function for the walks in such cones that start and end at the origin. In the particular case of a cone of angle \(3 \pi / 4\) these walks are directly related to Gessel’s walks in the quadrant, and we provide a new proof of their enumeration. Next we study the distribution of the winding angle of a simple random walk on \(\mathbb{Z}^2\) around a point in the close vicinity of its starting point, for which we identify discrete analogues of the known hyperbolic secant laws and a probabilistic interpretation of the Jacobi elliptic functions. Finally we relate the spectrum of one of the Hilbert space operators to the enumeration of closed loops in \(\mathbb{Z}^2\) with fixed winding number around the origin.

MSC:

60G50 Sums of independent random variables; random walks
05A15 Exact enumeration problems, generating functions
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abramowitz, M.; Stegun, I. A., Handbook of Mathematical Functions: With Formulas, Graphs, and Mathematical Tables (1964), Courier Corporation · Zbl 0171.38503
[2] Akhiezer, N. I., Elements of the Theory of Elliptic Functions, Transl. of Math. Monographs, vol. 79 (1990), American Mathematical Soc. · Zbl 0694.33001
[3] Arcozzi, N.; Rochberg, R.; Sawyer, E.; Wick, B., The Dirichlet space: a survey, N.Y. J. Math., 17A, 45-86 (2011) · Zbl 1233.30017
[4] Bélisle, C., Windings of random walks, Ann. Probab., 17, 4, 1377-1402 (1989) · Zbl 0693.60020
[5] Bélisle, C.; Faraway, J., Winding angle and maximum winding angle of the two-dimensional random walk, J. Appl. Probab., 28, 4, 717-726 (1991) · Zbl 0748.60057
[6] Bernardi, O., Bijective counting of Kreweras walks and loopless triangulations, J. Comb. Theory, Ser. A, 114, 5, 931-956 (2007) · Zbl 1119.05006
[7] Bernardi, O.; Bousquet-Mélou, M.; Raschel, K., Counting quadrant walks via Tutte’s invariant method · Zbl 1498.05012
[8] Borot, G.; Bouttier, J.; Guitter, E., Loop models on random maps via nested loops: the case of domain symmetry breaking and application to the Potts model, J. Phys. A, Math. Theor., 45, 49, Article 494017 pp. (2012) · Zbl 1257.82016
[9] Borot, G.; Bouttier, J.; Guitter, E., A recursive approach to the \(O(n)\) model on random maps via nested loops, J. Phys. A, Math. Theor., 45, 4, Article 045002 pp. (2012) · Zbl 1235.82026
[10] Borot, G.; Bouttier, J.; Duplantier, B., Nesting statistics in the \(O(n)\) loop model on random planar maps
[11] Borwein, J.; Borwein, P., Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity (1987), Wiley · Zbl 0611.10001
[12] Bostan, A.; Kauers, M., The complete generating function for Gessel walks is algebraic, Proc. Am. Math. Soc., 138, 9, 3063-3078 (2010) · Zbl 1206.05013
[13] Bostan, A.; Kurkova, I.; Raschel, K., A human proof of Gessel’s lattice path conjecture, Trans. Am. Math. Soc., 369, 2, 1365-1393 (2017) · Zbl 1350.05006
[14] Bousquet-Mélou, M., Walks on the slit plane: other approaches, Adv. Appl. Math., 27, 2, 243-288 (2001) · Zbl 0992.05012
[15] Bousquet-Mélou, M., An elementary solution of Gessel’s walks in the quadrant, Adv. Math., 303, 1171-1189 (2016) · Zbl 1351.05017
[16] Bousquet-Mélou, M., Square lattice walks avoiding a quadrant, J. Comb. Theory, Ser. A, 144, 37-79 (2016) · Zbl 1343.05019
[17] 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), 1-39 · Zbl 1209.05008
[18] Bousquet-Mélou, M.; Schaeffer, G., Walks on the slit plane, Probab. Theory Relat. Fields, 124, 3, 305-344 (2002) · Zbl 1008.05006
[19] Bruckman, P. S., On the evaluation of certain infinite series by elliptic functions, Fibonacci Q., 15, 4, 293-310 (1977) · Zbl 0399.10013
[20] Budd, T., The peeling process of infinite Boltzmann planar maps, Electron. J. Comb., 23, 1, Article P1.28 pp. (2016) · Zbl 1331.05192
[21] Budd, T., The peeling process on random planar maps coupled to an \(O(n)\) loop model, (with an appendix by Linxiao Chen)
[22] Budd, T.; Curien, N., Geometry of infinite planar maps with high degrees, Electron. J. Probab., 22 (2017) · Zbl 1360.05151
[23] Camia, F., Brownian loops and conformal fields, (Advances in Disordered Systems, Random Processes and Some Applications (2016), Cambridge University Press)
[24] Camia, F.; Gandolfi, A.; Kleban, M., Conformal correlation functions in the Brownian loop soup, Nucl. Phys. B, 902, 483-507 (2016) · Zbl 1332.82083
[25] Collet, G.; Fusy, É., A simple formula for the series of constellations and quasi-constellations with boundaries, Electron. J. Comb., 21, 2, P2.9 (2014) · Zbl 1300.05074
[26] Drossel, B.; Kardar, M., Winding angle distributions for random walks and flux lines, Phys. Rev. E, 53, 6, 5861-5871 (June 1996)
[27] Flajolet, P.; Odlyzko, A., Singularity analysis of generating functions, SIAM J. Discrete Math., 3, 2, 216-240 (1990) · Zbl 0712.05004
[28] Garban, C.; Trujillo-Ferreras, J. A., The expected area of the filled planar Brownian loop is \(\pi / 5\), Commun. Math. Phys., 264, 3, 797-810 (2006) · Zbl 1107.82023
[29] Hartman, P.; Wintner, A., The spectra of Toeplitz’s matrices, Am. J. Math., 76, 867-882 (1954) · Zbl 0056.11301
[30] Kauers, M.; Koutschan, C.; Zeilberger, D., Proof of Ira Gessel’s lattice path conjecture, Proc. Natl. Acad. Sci., 106, 28, 11502-11505 (2009) · Zbl 1203.05010
[31] Kenyon, R.; Miller, J.; Sheffield, S.; Wilson, D. B., Bipolar orientations on planar maps and SLE_12 · Zbl 1466.60170
[32] Kenyon, R. W.; Wilson, D. B., The Green’s function on the double cover of the grid and application to the uniform spanning tree trunk · Zbl 1460.82005
[33] Lawler, G.; Trujillo Ferreras, J., Random walk loop soup, Trans. Am. Math. Soc., 359, 2, 767-787 (2007) · Zbl 1120.60037
[34] Nesterenko, Y., Modular functions and transcendence, Sb. Math., 187, 9, 65-96 (1996) · Zbl 0898.11031
[35] Reed, M.; Simon, B., Methods of Modern Mathematical Physics I: Functional Analysis (1981), Academic Press: Academic Press San Diego
[36] Rudnick, J.; Hu, Y., The winding angle distribution of an ordinary random walk, J. Phys. A, Math. Gen., 20, 13, 4421 (1987)
[37] Schwartz, H., Über 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
[38] Shi, Z., Windings of Brownian motion and random walks in the plane, Ann. Probab., 26, 1, 112-131 (1998) · Zbl 0938.60073
[39] Walker, P., The analyticity of Jacobian functions with respect to the parameter k, Proc. R. Soc. Lond. A, 459, 2569-2574 (2003) · Zbl 1052.33018
[40] Yor, M., Loi de l’indice du lacet Brownien, et distribution de Hartman-Watson, Z. Wahrscheinlichkeitstheor. Verw. Geb., 53, 1, 71-95 (1980) · Zbl 0436.60057
[41] Zhu, K., Operator Theory in Function Spaces (2007), American Mathematical Soc. · Zbl 1123.47001
[42] Zimmer, J., Essential Results of Functional Analysis, Chicago Lectures in Mathematics (1990), University of Chicago Press · Zbl 0708.46001
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.