---
abstract:
- 'In this note, we consider random walks in the quarter plane with arbitrary big jumps. We announce the extension to that class of models of the analytic approach of @FIM, initially valid for walks with small steps in the quarter plane. New technical challenges arise, most of them being tackled in the framework of generalized boundary value problems on compact Riemann surfaces.'
- 'Dans cette note nous nous intéressons aux marches aléatoires avec sauts arbitrairement grands dans le quart de plan. Nous annonçons le développement pour cette classe de modèles de l'approche analytique proposée dans @FIM, initialement applicable aux marches à petits sauts dans le quart de plan. De nouvelles difficultés théoriques surgissent, qui, pour l'essentiel, sont abordées dans le cadre de la théorie des problèmes aux limites généralisés sur des surfaces de Riemann compactes.'
author:
- 'Guy Fayolle[^1]'
- 'Kilian Raschel[^2]'
title: 'About a possible analytic approach for walks in the quarter plane with arbitrary big jumps[^3]'
---

Introduction
============

In the past decades, many fruitful research activities have been dealing with the analysis of random walks in the quarter plane (RWQP) or quadrant $\mathbb Z_+^2$. Indeed, these objects are at the crossroads of several domains. In our framework, the initial motivations were twofold: on one hand, to analyze the stationary distribution of irreducible RWQP @MAL; on other hand, to study queueing models representing two coupled processors working at different service rates @FI. One can also consult @CB [@FIM] for modern reference books on analytic and probabilistic aspects of RWQP. Recently, applications were found in enumerative combinatorics, see @BMM. Indeed, walks in the quarter plane naturally encode many combinatorial objects (certain trees, maps, permutations, Young tableaux, etc.). They also have many links with population biology and finance. Lastly, in another context, RWQP can be viewed as particular instances of random processes in cones. This latter topic is the subject of many recent works, due to its links with representation theory, quantum random walks, random matrices, non-colliding random walks, etc.

In most of the analytic studies (in particular in @BMM [@FI; @FIM; @MAL]), walks are supposed to have *small steps*. This means that each unit of time, jumps take place to (a subset of) the eight nearest neighbors on the lattice, see Figure \[fig:Walks\]. There are many reasons to make this hypothesis, their fundamental common point being that they simplify the technical computations, and allow to get closed-form solutions. *In this paper, we aim at presenting some challenges, and we announce results concerning the analysis of random walks having possibly *big jumps* in the quarter plane*. This extension of the analytic approach of @FIM has many possible applications, including queueing models, enumeration of lattice paths, discrete harmonic functions, stationary probabilities, etc.

(17,7) (1,1)<span><span>(1,0)<span>5.5</span></span></span> (1,1)<span>(0,1)<span>5.5</span></span> (4,4)<span>(1,1)<span>1</span></span> (4,4)<span>(-1,-1)<span>1</span></span> (4,4)<span>(1,0)<span>1</span></span> (4,4)<span>(-1,0)<span>1</span></span> (4,4)<span>(0,1)<span>1</span></span> (4,4)<span>(0,-1)<span>1</span></span> (4,4)<span>(-1,1)<span>1</span></span> (4,4)<span>(1,-1)<span>1</span></span> (1,2)<span>(0,0)(5.5,0)</span> (1,3)<span>(0,0)(5.5,0)</span> (1,4)<span>(0,0)(5.5,0)</span> (1,5)<span>(0,0)(5.5,0)</span> (1,6)<span>(0,0)(5.5,0)</span> (2,1)<span>(0,0)(0,5.5)</span> (3,1)<span>(0,0)(0,5.5)</span> (4,1)<span>(0,0)(0,5.5)</span> (5,1)<span>(0,0)(0,5.5)</span> (6,1)<span>(0,0)(0,5.5)</span>

(0,-10) (1,1)<span><span>(1,0)<span>5.5</span></span></span> (1,1)<span>(0,1)<span>5.5</span></span> (4,4)<span>(1,1)<span>1</span></span> (4,4)<span>(-1,-1)<span>1</span></span> (4,4)<span>(-1,-1)<span>2</span></span> (4,4)<span>(1,1)<span>2</span></span> (4,4)<span>(-1,0)<span>2</span></span> (4,4)<span>(1,0)<span>2</span></span> (4,4)<span>(0,1)<span>2</span></span> (4,4)<span>(0,-1)<span>2</span></span> (4,4)<span>(-1,1)<span>2</span></span> (4,4)<span>(1,-1)<span>2</span></span> (4,4)<span>(1,-2)<span>1</span></span> (4,4)<span>(1,2)<span>1</span></span> (4,4)<span>(-1,-2)<span>1</span></span> (4,4)<span>(-1,2)<span>1</span></span> (4,4)<span>(-2,1)<span>2</span></span> (4,4)<span>(2,1)<span>2</span></span> (4,4)<span>(-2,-1)<span>2</span></span> (4,4)<span>(2,-1)<span>2</span></span> (4,4)<span>(1,0)<span>1</span></span> (4,4)<span>(-1,0)<span>1</span></span> (4,4)<span>(0,1)<span>1</span></span> (4,4)<span>(0,-1)<span>1</span></span> (4,4)<span>(-1,1)<span>1</span></span> (4,4)<span>(1,-1)<span>1</span></span> (1,2)<span>(0,0)(5.5,0)</span> (1,3)<span>(0,0)(5.5,0)</span> (1,4)<span>(0,0)(5.5,0)</span> (1,5)<span>(0,0)(5.5,0)</span> (1,6)<span>(0,0)(5.5,0)</span> (2,1)<span>(0,0)(0,5.5)</span> (3,1)<span>(0,0)(0,5.5)</span> (4,1)<span>(0,0)(0,5.5)</span> (5,1)<span>(0,0)(0,5.5)</span> (6,1)<span>(0,0)(0,5.5)</span>

To understand the intrinsic difficulties of such models, we should first recall that the now standard approach (for small steps walks) can be summarized by the three following steps.

1.  \[step:functional\_equation\] Find a functional equation for the generating function(s) of interest.

2.  \[step:BVP\] Rewrite the functional equation as a *boundary value problem* (BVP).

3.  \[step:solve\_BVP\] Solve the BVP.

This approach concerns several types of problems pertaining to various mathematical areas, and allows to obtain many quantities: the stationary distribution of ergodic RWQP reflected on the boundary @FIM [@MAL], the Green functions of killed random walks, the enumeration of deterministic walks @BMM, fine characteristics of certain queueing systems @FI, discrete harmonic functions, etc.

Contrary to point (\[step:functional\_equation\]), we shall see that points (\[step:BVP\]) and (\[step:solve\_BVP\]) raise more difficult issues, when assumptions on small jumps are relaxed. Indeed, point (\[step:functional\_equation\]) is rather simple, in the sense that most of the time, finding a functional equation simply reflects properties of the model. Point (\[step:BVP\]), which first appeared in @FI, is the keystone of the whole approach. Point (\[step:solve\_BVP\]) is highly technical, and uses the standard literature (with some peculiarities) devoted to the resolution of BVPs. In many examples, it turns out that the BVPs at stake (\[step:BVP\]) have a unique solution, corresponding to the generating functions of interest.

Presentation of the model, functional equation, and principles of the approach
==============================================================================

(19.55,6.5) (10,3.5) – (13.5,3.5) – (13.5,0) – (10,0) – cycle;

(7.5,6.5) (1,1)<span><span>(1,0)<span>5.5</span></span></span> (1,1)<span>(0,1)<span>5.5</span></span> (4,1)<span><span>(1,0)<span>2.5</span></span></span> (1,4)<span>(0,1)<span>2.5</span></span> (2,3)<span>(0,2)<span>3.5</span></span> (3,2)<span>(2,0)<span>3.5</span></span> (1,2)<span>(0,0)(5.5,0)</span> (1,3)<span>(0,0)(5.5,0)</span> (1,4)<span>(0,0)(5.5,0)</span> (1,5)<span>(0,0)(5.5,0)</span> (1,6)<span>(0,0)(5.5,0)</span> (2,1)<span>(0,0)(0,5.5)</span> (3,1)<span>(0,0)(0,5.5)</span> (4,1)<span>(0,0)(0,5.5)</span> (5,1)<span>(0,0)(0,5.5)</span> (6,1)<span>(0,0)(0,5.5)</span> <span>(2,2)</span> <span>(1,2)</span> <span>(1,3)</span> <span>(2,1)</span> <span>(3,1)</span> <span>(1,1)</span>

The model
---------

In this section we introduce the notation, in the particular example of ergodic RWQP, although the announced results can be rendered much more general.

Consider a two-dimensional random process with the following properties.

1.  \[hypothesis:state\_space\]The state space is the quarter plane $\mathbb Z_+^2=\{0,1,2,\ldots \}^2$.

2.  \[hypothesis:space\_homogeneity\]The state space can be represented as the union of non-intersecting classes $$\label{eq:decomposition}
         \mathbb Z_+^2=S\cup\{\cup_\ell S'_{\ell}\}\cup \{\cup_k S''_{k}\}\cup\{\cup_{k,\ell} \{(k,\ell)\}\}.$$ In order to describe the decomposition we need to introduce four parameters, $(I^-,J^-)$ (resp. $(I^0,J^0)$), which describe the maximal negative amplitude of the transition probabilities in the interior (resp. on the boundary) of the quarter plane. Then, the interior class of the quadrant is $$S=\{(i,j)\in\mathbb Z_+^2: i{\geqslant}I^-,j{\geqslant}J^-\}.$$ In addition, $$S'_\ell=\{(i,\ell)\in\mathbb Z_+^2:i{\geqslant}I^-\},\qquad S''_k=\{(k,j)\in\mathbb Z_+^2:j{\geqslant}J^-\}$$ are the horizontal and vertical domains strictly above the coordinate axes (i.e., $\ell\in\{1,\ldots ,J^--1\}$, $k\in\{1,\ldots ,I^--1\}$), and $$S'_0=\{(i,0)\in\mathbb Z_+^2:i{\geqslant}I^0\},\qquad S''_0=\{(0,j)\in\mathbb Z_+^2:j{\geqslant}J^0\}$$ are parts of the coordinate axes. Lastly, we also need $\{(k,\ell)\}$ to take into account the finite number of remaining isolated points. See Figure \[fig:homogeneity\], where $I^-=J^-=2$ and $I^0=J^0=3$. Thus, in each class, the walk has state homogeneous transition probabilities, denoted by $p_{i,j}$, $p^{S'_\ell}_{i,j}$, $p^{S''_k}_{i,j}$ and $p^{(k,\ell)}_{i,j}$, respectively.

3.  \[hypothesis:boundedness\] We assume that $p_{i,j}=0  \mbox{ if } \{i<-I^- \mbox{ or } j<-J^-\} \mbox{ and if }\{i>I^+ \mbox{ or }j>J^+\}$. In this context, the small steps hypothesis reads $I^-=I^+=J^-=J^+=1$.

Statement of the functional equation
------------------------------------

We denote the generating function of the transition probabilities for the class $S$ by (when nothing is specified, the sum runs on all couples of indices $(i,j)\in\mathbb Z^2$) $$\label{eq:def_R}
     R(x,y) = -1 + \textstyle \sum_{i,j}p_{i,j}x^iy^j ,$$ and the stationary probabilities generating function by$$\label{eq:def_pi}
     \pi(x,y) = \textstyle \sum_{i{\geqslant}I^-,j{\geqslant}J^-}\pi_{i,j}x^iy^j.$$ For the other classes, we take the same notation with the associated class symbol in exponent (for instance, $R^{S'_\ell}(x,y)$ and $\pi^{S'_\ell}(x,y)$ for the class ${S'_\ell}$). Then the functional equation to be solved takes the form (see @FIM [Equation (1.3.4)]) $$\label{eq:main_functional_equation}
     -R(x,y) \pi(x,y)  = \sum_{\{(k,\ell)\}}R^{(k,\ell)}(x,y)\pi^{(k,\ell)}(x,y)   
     +\sum_{\ell=0}^{J^--1}R^{S'_\ell}(x,y)\pi^{S'_\ell}(x,y)+\sum_{k=0}^{I^--1}R^{S''_k}(x,y)\pi^{S''_k}(x,y).$$ It is valid (at least) in the bi-disc $\{x\in \mathbb C: \vert x\vert {\leqslant}1\}\times\{x\in \mathbb C: \vert y\vert {\leqslant}1\}$. The generating function $\pi^{S'_\ell}(x,y)$ (resp. $\pi^{S''_k}(x,y)$) is essentially a function of the single variable $x$ (resp. $y$), since $\pi^{S'_\ell}(x,y)=y^\ell \sum_{i{\geqslant}I^-} \pi_{i,\ell}x^i$ (resp. $\pi^{S''_k}(x,y)=x^k \sum_{j{\geqslant}J^-} \pi_{k,j}y^j$). Further, one has $\pi^{(k,\ell)}(x,y)=\pi_{k,\ell}x^ky^\ell$.

Principles of the method {#subsec:principles}
------------------------

In the right-hand side of , there are $I^-+J^-$ unknown functions, together with a finite number of unknown coefficients $\pi_{k,\ell}$. We shall focus on the $I^-+J^-$ unknown functions, which all are sought a priori to be analytic in the unit disc $\mathcal{D}$ (in fact, they will be only meromorphic in $\mathcal{D}$ when the system is not ergodic). The basic idea to determine these functions is to find $I^-+J^-$ independent equations. In our case these equations will take the form of BVPs set on closed curves (see for an example), each of these problems being obtained from *a pair of branch points in $\mathcal{D}$* of the polynomial $$\label{eq:def_P}
     P(x,y) = x^{I^-}y^{J^-}R(x,y),$$ which is of degree $I=I^-+I^+$ in $x$ and $J=J^-+J^+$ in $y$, recalling that $x$ is a *branch point* if the equation $P(x,y)=0$ in $y$ has a multiple root. In this probabilistic context, the unit disc condition is exactly the domain of definition (a priori) of the generating functions. From a technical point of view, a large part of the analysis will be devoted to locate these branch points, and to select which of them lead to boundary equations on closed curves, in connection with the underlying Riemann surface generated by the algebraic curve $$\label{eq:def_surface}
     \{(x,y)\in(\mathbb C\cup\{\infty\})^2 : P(x,y)=0\}.$$

Analytic approach for walks with small steps: branch points and the reduction to BVP
====================================================================================

Here we are left with only two unknowns in the right-hand side of the functional equation , as well as (to simplify) one unknown scalar coefficient $\pi^{(k,\ell)}(x,y)=\pi_{0,0}$ (in some sense, $\pi_{0,0}$ is not unknown, thanks to the normalization $\sum_{i,j{\geqslant}0}\pi_{i,j}=1$). In the sequel, we shall write $\pi^{S'_\ell}(x,y)=y\pi(x)$ and $\pi^{S''_k}(x,y)=x\widetilde{\pi}(y)$.

=0.6cm

(13,10) (-5,0)<span>(1,0)<span>10</span></span> (0,-5)<span>(0,1)<span>10</span></span> (0,0) (1.5,0.4)<span>$1$</span> (-0.75,0.4)<span>$y_1$</span> (0.8,0.4)<span>$y_2$</span> (1.9,0.4)<span>$y_3$</span> (3.7,0.4)<span>$y_4$</span> <span>(1.5,0)</span>

(-13,0) (-5,0)<span>(1,0)<span>10</span></span> (0,-5)<span>(0,1)<span>10</span></span> (-3.6,0.4) (0.2,0)(2.5,1.75)

It was proved in @FIM that the functions $\pi(x)$ and $\widetilde \pi(y)$ can be found by solving a BVP on a closed curve. In more concrete terms, this means that there exists a curve $C$, symmetrical with respect to the horizontal axis (see Figure \[fig:ex\_curve\]), satisfying the boundary condition (below, we note $\alpha({t})=\overline{t}$ the complex conjugation, which is a particular automorphism of $C$, see Section \[sec:BC\]) $$\label{eq:boundary_condition}
     A(t)\pi (t) - A(\alpha({t}))\pi(\alpha({t})) = g(t),\qquad \forall t\in C.$$ Above, $A(t)$ and $g(t)$ are known functions having simple expressions in terms of the parameters, see @FIM [Equations (5.1.5) and (5.1.6)]. The curve $C$ is obtained via a study of the branch points of the algebraic function of $y$ defined by $P(x,y)=0$. In the small steps case, with obvious notations, we may write $P(x,y)=b_2(y)x^2+b_1(y)x+b_0(y)$; its discriminant equals $$\Delta(y)=b_1(y)^2-4b_2(y)b_0(y).$$ It is easily proved that this discriminant has always $4$ real roots $y_k$ (in general not necessarily distinct), named branch points, as shown on Figure \[fig:ex\_curve\]. Let $L$ be a segment between two consecutive branch points. For $l\in L$, the two solutions to $P(x,l)=0$ are either real or complex conjugate. Choosing $L$ such that the two roots are complex conjugate, the set $$\label{eq:expression_curve}
     \bigcup_{l\in L}\{x\in \mathbb C\cup\{\infty\} : P(x,l)=0\}$$ is symmetrical with respect to the real axis in the $x$-plane, and it builds the two closed components of a *decomposed quartic curve*, which do not intersect and correspond respectively to the cuts $[y_1,y_2]$ and $[y_3,y_4]$ in the $x$-plane. On Figure \[fig:ex\_curve\], $C$ is the component corresponding to $L=[y_1,y_2]$ in .

Formal analytic approach for walks with arbitrary big steps
===========================================================

We present a sequence of results showing to which extent the method of @FIM can be generalized to models of walks with arbitrary big jumps. The line of argument proceeds in stages, one of the key points being, as announced in Section \[subsec:principles\], to prove the existence of $I^-$ (resp. $J^-$) *suitable* couples of branch points $x_k$ (resp. $y_k$) within the closed unit disc $\mathcal{D}$. Then each such pair will be associated with *appropriate branches (or sheets)* of the algebraic curve (after analytic continuation), and finally used to set a BVP for the $I^-$ (resp. $J^-$) unknown functions $\pi^{S''_k}(x,y)$ (resp. $\pi^{S'_\ell}(x,y)$). Needless to mention that selecting these so-called suitable branches involves some deep technicalities related to Riemann surfaces.

Finding and classifying the branch points
-----------------------------------------

Branch points in the $x$-plane are obtained by means of the *discriminant* in $y$ of the polynomial $$P(x,y)=b_I(y)x^I+\cdots+b_0(y)=a_J(x)y^J+\cdots+a_0(x).$$

\[BP\] There are at most $2J(I-1)$ branch points $y_k$ and $2I(J-1)$ branch points $x_k$.

The proof of Lemma \[BP\] relies on the expression of the resultant of $P(x,y)$ and $\frac{\partial P}{\partial x}(x,y)$ (resp. $\frac{\partial P}{\partial y}(x,y)$). These branch points can be split into two categories: the ones outside $\mathcal{D}$, and those inside. We shall prove that, among the interior points, certain ones are not relevant for the problem, in the sense that they will not necessarily lead to boundary conditions on closed curves. This is the subject of the next assertion.

There are exactly $2I^-$ (resp. $2J^-$) interior branch points $x_k$ (resp. $y_k$) leading to boundary conditions on closed curves.

The problem of leading or not to conditions on closed curves of the type strongly depends on the behavior of the branches of the algebraic functions defined by $P(x,Y(x))=P(X(y),y)=0$ in the neighborhood of the branch points. The answer to this difficult question is related to the genus and other specific properties of the underlying Riemann surface .

Branch cuts and boundary value problems {#sec:BC}
---------------------------------------

The $2J^-$ branch points $y_k$ can be grouped by pairs, forming segments $L$ in the $y$-plane. Some segments $L$ are real (as in the small steps case), but others can be complex conjugate (this is a new phenomenon pertaining to the big jumps case). For real segments, the boundary conditions are of type . But, for the non-real segments $L$, condition changes: $\alpha$ is no more the complex conjugation, but a more general automorphism, sometimes called Carleman automorphism, satisfying $\alpha^2(t)=t$.

The solution of the fundamental equation can be obtained from a generalized BVP satisfied by a vector of $J^-$ unknown functions of the variable $x$. This BVP, defined from $J^-$ boundary conditions on closed curves, has in general a unique solution in the ergodic case. Mutatis mutandis, a similar statement holds for the $I^-$ unknown functions of $y$.

In general, it is hopeless to expect a closed-form expression for the unknown functions in . The reader will easily understand this claim, just by seeing the complexity of the computations in the small steps case @FIM. There is, however, a particular and interesting class for which we will be able to obtain explicit expressions, namely the models where $I^-=J^-=1$. Indeed, for these models, the functional equation takes the same form as for the small steps case.

Uniformization and <span>Ł</span>ukasiewicz walks
-------------------------------------------------

When the projections of the jumps in the west and south directions are of size one, while the others are arbitrary and bounded, one speaks sometimes of *<span>Ł</span>ukasiewicz walks*, see @FS [Section I.5.3]. Then the following result holds.

For <span>Ł</span>ukasiewicz walks, the unique unknown function $\pi(x)$ in the variable $x$ is given by $$\int_C\frac{f(t)w'(t)}{w(t)-w(x)}\textnormal{d}t.$$ Here, $f$ is a known algebraic function, and $w$ is directly expressed in terms of the conformal mapping between the interior domain of $C$ and the unit disc $\mathcal{D}$. This mapping in turn can be obtained by means of an ad hoc uniformization of the Riemann surface .

The analysis of $w$ in the small steps case, done in @FIM, allows to introduce elliptic functions, since the Riemann surface in the generic situation has genus one (the torus). But in the case of big jumps, the genus is bigger than one. Although the genus is not simply given in terms of the parameters $I^\pm$ and $J^\pm$, we can express it thanks to the Riemann-Hurwitz's formula, in terms of the order of the branch points.

#### Acknowledgements {#acknowledgements .unnumbered}

The authors would like to thank the referee for his remarks about integrable systems and possible applications to the quantum three-body problem.

<span>00</span> M. Bousquet-Mélou, and M. Mishna. Walks with small steps in the quarter plane. (2010) 1–39.

. <span>*Boundary value problems in queueing system analysis*</span>. <span>North-Holland Publishing Co.</span>, <span>Amsterdam</span> <span>(1983)</span>.

G. Fayolle, and R. Iasnogorodski. Two coupled processors: the reduction to a <span>R</span>iemann-<span>H</span>ilbert problem. (1979) 325–351.

G. Fayolle, R. Iasnogorodski, and V. Malyshev. . Springer-Verlag, Berlin (1999).

P. Flajolet, and R. Sedgewick. Cambridge University Press, Cambridge, 2009.

V. Malyshev. An analytical method in the theory of two-dimensional positive random walks. (1972) 1314–1329.

[^1]: INRIA Paris-Rocquencourt, Domaine de Voluceau, BP 105, 78153 Le Chesnay Cedex, France. Email: [nicholasgarcia@example.net](nicholasgarcia@example.net)

[^2]: CNRS & Fédération Denis Poisson & Laboratoire de Mathématiques et Physique Théorique, Université de Tours, Parc de Grandmont, 37200 Tours, France. Email: [nicholasgarcia@example.net](nicholasgarcia@example.net)

[^3]: Version of

{'source': 'arXiv_out/1406'}