Walks on the slit plane

Abstract

In the first part of this paper, we enumerate exactly walks on the square lattice that start from the origin, but otherwise avoid the non positive horizontal half-axis. We call them "walks on the slit plane". We count them by their length, and by the coordinates of their endpoint. The corresponding three variable generating function is algebraic of degree 8. Moreover, for any point (i,j), the length generating function for walks of this type ending at (i,j) is also algebraic, of degree 2 or 4, and involves the famous Catalan numbers. Our method is based on the solution of a functional equation, established via a simple combinatorial argument. It actually works for more general models, in which walks take their steps in a finite subset of Z^2 satisfying two simple conditions. The corresponding generating functions are always algebraic. In the second part of the paper, we derive from our enumerative results a number of probabilistic corollaries. For instance, we can compute exactly the probability that an ordinary random walk starting from (i,j) hits for the first time the horizontal half-axis at position (k,0), for any triple (i,j,k). This generalizes a question raised by R. Kenyon, which was the starting point of this paper. Taking uniformly at random all n-step walks on the slit plane, we also compute the probability that they visit a given point (k,0), and the average number of visits to this point. In other words, we quantify the transience of the walks. Finally, we derive an explicit limit law for the coordinates of their endpoint.

30 pages, 9 figures. See also http://www.loria.fr/~schaeffe/Pub/Slitplane/

References in corpus (1)

• Walks on the slit plane: other approaches

Cited by in corpus (14)

• Walks with small steps in the quarter plane
• Excited Random Walk
• Walks confined in a quadrant are not always D-finite
• The Ring of Malcev-Neumann Series and the Residue Theorem
• On a general many-dimensional excited random walk
• Winding of simple walks on the square lattice
• Counting lattice walks by winding angle
• Quantum Cellular Automaton Model for the Generalized Dirac Equation
• A note on the Green's function for the transient random walk without killing on the half lattice, orthant and strip
• Walks in the quarter plane: Kreweras' algebraic model
• Central Limit Theorem for the Excited Random Walk in dimension $d\ge 2$
• Proof of a Conjecture on the Slit Plane Problem
• Counting Lattice Paths By Gessel Pairs
• Partially directed paths in a wedge