Skip to Main content Skip to Navigation
Journal articles

Walks in the slit plane

Mireille Bousquet-Mélou 1 Gilles Schaeffer 2
2 ADAGE - Applying discrete algorithms to genomics
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
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 half-line ${\cal H}=\{(k,0), k\le 0\}$. We call them {\em walks on the slit plane\/}. We count them by their length, and by the coordinates of their endpoint. The corresponding three variable \gf \ is algebraic of degree $8$. Moreover, for any point $(i,j)$, the length \gf \ 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 $\zs ^2$ satisfying two simple conditions. The corresponding \gfs \ 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 half-line $\cal H$ 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.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/inria-00100936
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 2:53:00 PM
Last modification on : Friday, February 26, 2021 - 3:28:02 PM

Identifiers

  • HAL Id : inria-00100936, version 1

Citation

Mireille Bousquet-Mélou, Gilles Schaeffer. Walks in the slit plane. Probability Theory and Related Fields, Springer Verlag, 2002, 124 (3), pp.305-344. ⟨inria-00100936⟩

Share

Metrics

Record views

232