×

zbMATH — the first resource for mathematics

Walks in the quarter plane: Kreweras’ algebraic model. (English) Zbl 1064.05010
Summary: We consider planar lattice walks that start from (0,0), remain in the first quadrant \(i,j\geq 0\), and are made of three types of steps: North-East, West and South. These walks are known to have remarkable enumerative and probabilistic properties:
\(\bullet\) they are counted by nice numbers [G. Kreweras, Cahiers du B.U.R.O 6, 5–105 (1965)],
\(\bullet\) the generating function of these numbers is algebraic [I.M. Gessel, J. Stat. Plann. Inference 14, 49–58 (1986; Zbl 0602.05006)],
\(\bullet\) the stationary distribution of the corresponding Markov chain in the quadrant has an algebraic probability generating function [L. Flatto and S. Hahn, SIAM J. Appl. Math. 44, 1041–1053 (1984; Zbl 0554.90041)].
These results are not well understood, and have been established via complicated proofs. Here we give a uniform derivation of all of them, which is more elementary than those previously published. We then go further by computing the full law of the Markov chain. This helps to delimit the border of algebraicity: the associated probability generating function is no longer algebraic, unless a diagonal symmetry holds.
Our proofs are based on the solution of certain functional equations, which are very simple to establish. Finding purely combinatorial proofs remains an open problem.

MSC:
05A15 Exact enumeration problems, generating functions
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Banderier, C., Bousquet-Mélou, M., Denise, A., Flajolet, P., Gardy, D. and Gouyou-Beauchamps, D. (2002). Generating functions for generating trees. Discrete Math. 246 29–55. · Zbl 0997.05007 · doi:10.1016/S0012-365X(01)00250-3
[2] Banderier, C. and Flajolet, P. (2002). Basic analytic combinatorics of directed lattice paths. Theoret. Comput. Sci. 281 37–80. · Zbl 0996.68126 · doi:10.1016/S0304-3975(02)00007-5
[3] Berstel, J. (2003). Personal communication.
[4] Bousquet-Mélou, M. (2001). Walks on the slit plane: Other approaches. Adv. in Appl. Math. 27 243–288. · Zbl 0992.05012 · doi:10.1006/aama.2001.0734
[5] Bousquet-Mélou, M. (2002). Counting walks in the quarter plane. In Mathematics and Computer Science 2 49–67. Birkhäuser, Basel. · Zbl 1026.05004
[6] Bousquet-Mélou, M. (2003). Four classes of pattern-avoiding permutations under one roof: Generating trees with two labels. Electron. J. Combin. 9 . Research Paper 19. · Zbl 1031.05006
[7] Bousquet-Mélou, M. and Petkovšek, M. (2000). Linear recurrences with constant coefficients: The multivariate case. Discrete Math. 225 51–75. · Zbl 0963.05005 · doi:10.1016/S0012-365X(00)00147-3
[8] Bousquet-Mélou, M. and Petkovšek, M. (2003). Walks confined in a quadrant are not always D-finite. Theoret. Comput. Sci. 307 257–276. · Zbl 1070.68112 · doi:10.1016/S0304-3975(03)00219-6
[9] Bousquet-Mélou, M. and Schaeffer, G. (2002). Walks on the slit plane. Probab. Theory Related Fields 124 305–344. · Zbl 1008.05006 · doi:10.1007/s004400200205
[10] Chung, K. L. (1967). Markov Chains with Stationary Transition Probabilities , 2nd ed. Springer, New York. · Zbl 0146.38401
[11] Fayolle, G. and Iasnogorodski, R. (1979). Solutions of functional equations arising in the analysis of two-server queueing models. In Performance of Computer Systems (M. Arató, B. Butrimenko and E. Gelenbe, eds.) 289–303. North-Holland, Amsterdam. · Zbl 0419.60090
[12] Fayolle, G. and Iasnogorodski, R. (1979). Two coupled processors: The reduction to a Riemann–Hilbert problem. Z. Wahrsch. Verw. Gebiete 47 325–351. · Zbl 0395.68032 · doi:10.1007/BF00535168
[13] Fayolle, G., Iasnogorodski, R. and Malyshev, V. (1999). Random Walks in the Quarter-Plane : Algebraic Methods , Boundary Value Problems and Applications . Springer, Berlin. · Zbl 0932.60002
[14] Fayolle, G., Malyshev, V. A. and Menshikov, M. V. (1995). Topics in the Constructive Theory of Countable Markov Chains . Cambridge Univ. Press. · Zbl 0823.60053 · doi:10.1017/CBO9780511984020
[15] Flajolet, P. (1987). Analytic models and ambiguity of context-free languages. Theoret. Comput. Sci. 49 283–309. · Zbl 0612.68069 · doi:10.1016/0304-3975(87)90011-9
[16] Flajolet, P. and Odlyzko, A. (1990). Singularity analysis of generating functions. SIAM J. Discrete Math. 3 216–240. · Zbl 0712.05004 · doi:10.1137/0403019
[17] Flatto, L. and Hahn, S. (1984). Two parallel queues created by arrivals with two demands. I. SIAM J. Appl. Math. 44 1041–1053. · Zbl 0554.90041 · doi:10.1137/0144074
[18] Gessel, I. M. (1980). A factorization for formal Laurent series and lattice path enumeration. J. Combin. Theory Ser. A 28 321–337. · doi:10.1016/0097-3165(80)90074-6
[19] Gessel, I. M. (1986). A probabilistic method for lattice path enumeration. J. Statist. Plann. Inference 14 49–58. · Zbl 0602.05006 · doi:10.1016/0378-3758(86)90009-1
[20] Guy, R. K., Krattenthaler, C. and Sagan, B. E. (1992). Lattice paths, reflections, and dimension-changing bijections. Ars Combin. 34 3–15. · Zbl 0770.05003
[21] Hopcroft, J. E. and Ullman, J. D. (1969). Formal Languages and Their Relation to Automata . Addison–Wesley, Reading, MA. · Zbl 0196.01701
[22] Knuth, D. E. (1975). The Art of Computer Programming 1 , 2nd ed. Addison–Wesley, Reading, MA. · Zbl 0335.68018
[23] Kreweras, G. (1965). Sur une classe de problèmes liés au treillis des partitions d’entiers. Cahiers du B.U.R.O. 6 5–105.
[24] Lipshitz, L. (1988). The diagonal of a D-finite power series is D-finite. J. Algebra 113 373–378. · Zbl 0657.13024 · doi:10.1016/0021-8693(88)90166-4
[25] Lipshitz, L. (1989). D-finite power series. J. Algebra 122 353–373. · Zbl 0695.12018 · doi:10.1016/0021-8693(89)90222-6
[26] Malyšev, V. A. (1972). An analytic method in the theory of two-dimensional positive random walks. Siberian Math. J. 13 917–929. · Zbl 0287.60072 · doi:10.1007/BF00971868
[27] Malyšev, V. A. (1972). Classification of two-dimensional positive random walks and almost linear semi-martingales. Soviet. Math. Dokl. 13 136–139. · Zbl 0246.60055
[28] Niederhausen, H. (1980). Sheffer polynomials in path enumeration. In Proceedings of the West Coast Conference on Combinatorics , Graph Theory and Computing (P. Z. Chinn and D. McCarthy, eds.) 281–294. Utilitas, Winnipeg, Canada. · Zbl 0444.05005
[29] Niederhausen, H. (1983). The ballot problem with three candidates. European J. Combin. 4 161–167. · Zbl 0528.05003 · doi:10.1016/S0195-6698(83)80046-8
[30] Rudin, W. (1974). Real and Complex Analysis , 2nd ed. McGraw–Hill, New York. · Zbl 0278.26001
[31] Stanley, R. P. (1980). Differentiably finite power series. European J. Combin. 1 175–188. · Zbl 0445.05012 · doi:10.1016/S0195-6698(80)80051-5
[32] Stanley, R. P. (1999). Enumerative Combinatorics 2 . Cambridge Univ. Press. · Zbl 0928.05001
[33] Wright, P. E. (1992). Two parallel processors with coupled inputs. Adv. in Appl. Probab. 24 986–1007. · Zbl 0760.60093 · doi:10.2307/1427722
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.