PREMIÈRE ANNONCE Le groupe de travail Arbres-Chemins-Probabilités-Algorithme et le groupement ALÉA organisent deux journées sur le thème **************************************** MARCHES DANS UN QUART DE PLAN Lundi 15 et Mardi 16 novembre Université de Versailles Six exposés exceptionnels du Pr Guy FAYOLLE **************************************** THÈME: Il s'agit d'une réunion qui fonctionnera comme un groupe de travail très interactif et informel. L'objectif est de comprendre les méthodes du livre de Fayolle, Iasnogorodski et Malyshev, lesquelles combinent de jolies mathématiques variées (méthodes de noyau, conjuguaison algébrique, intégrales elliptiques, problèmes de Riemann-Hilbert). Il s'agit de fournir un cadre analytique d'étude des marches dans un quart de plan. PROGRAMME: Lundi 15 Novembre: 14h00-14h30 Ouverture et introduction (P. Flajolet) 14h30-15h20: Fayolle I 16h00-16h50: Fayolle II 17h15-18h00: Fayolle III 19h45: Repas, Place du Marché à Versailles Mardi 16 Novembre 10h00-10h50: Fayolle IV 11h30-12h20: Fayolle V 12h30-14h15 Repas 14h15-15h00: Fayolle VI 15h00-15h30: Conclusion des Journees (M. Bousquet-Mélou) LIEU: Salle 3102 du batiment Fermat, 45, avenue des Etats-Unis a Versailles. http://www.math.uvsq.fr/lama/ ORGANISATEURS: Mireille Bousquet-Mélou, Philippe Flajolet, Nicolas Pouyanne SITE OUÈBE: http://algo.inria.fr/Alea + pointeurs RÉFÉRENCE: Fayolle, Guy(F-INRIA); Iasnogorodski, Roudolf(F-ORLN); Malyshev, Vadim(F-INRIA) "Random walks in the quarter-plane". Springer-Verlag, Berlin, 1999. xvi+156 pp. ISBN 3-540-65047-4 ----------------------------------------------------------------- MATHEMATICAL REVIEWS: As the authors state in the introduction, the goal of this monograph is to promote original mathematical methods for determining the invariant measures of two-dimensional random walks in domains with non-smooth boundaries. The motivation comes from problems in three basic areas: (1) boundary value problems for functions of one complex variable; (2) singular integral equations, Wiener-Hopf equations, Toeplitz operators; and (3) random walks on a half-line and related queueing problems. The main line of research is as follows: For the random walks under consideration, the functional equation for the invariant measure has the form $$Q(x,y)\pi(x,y)+q(x,y)\pi(x)+\tilde q(x,y)\tilde \pi(y)+q_{0}(x,y)\pi_{00}=0.$$ (The terms correspond, respectively, to the interior, the positive $x$-axis, the positive $y$-axis, and the origin of the first quadrant.) The first step is to restrict the functional equation to the algebraic curve $Q=0$. On this curve, the equation reduces to an equation with two unknown functions of one variable each. The next step is to use Galois automorphisms to solve the equation on the algebraic curve. Then, $\pi$ and $\tilde \pi$ are lifted as meromorphic functions onto the complex plane $\bold C$, as the universal covering of the Riemann surface corresponding to the algebraic curve. Lifted onto the universal covering, $\pi$ and $\tilde \pi$ each satisfy a system of non-local equations of the form $$ \cases\pi(t + \omega_{1})=\pi(t),\quad \forall t \in\bold C, \cr \pi(t+\omega_{3})=a(t)\pi(t)+b(t),\quad \forall t \in\bold C, \endcases $$ where $\omega_{1}$ [resp. $\omega_{3}$] is a complex [resp. real] constant. The solution can be presented in terms of infinite series equivalent to Abelian integrals. The backward transformation (projection) from the universal covering onto the initial coordinates can be given in terms of uniformization functions, which in this case, are elliptic functions. The organization of the book is as follows: Chapter 1 contains background material on Markov chains, random walks in the quarter plane, and the derivation of the functional equations for the invariant measure. The first part of Chapter 2 contains background material on the necessary analytical tools: manifolds, Riemann surfaces, elements of Galois theory, universal covers, and abelian differentials and divisors. The second part of Chapter 2 begins the process outlined above: The fundamental equation is restricted to the algebraic curve. The initial domains of analyticity of the unknown functions are studied. The group of the random walk is introduced, and simple properties of the Galois automorphisms are given. Chapter 3 is devoted to the analytic continuation of the unknown functions in the genus 1 case. The case where the group of the random walk is finite is studied in Chapter 4. In this case, an elegant algebraic theory is developed for solving the fundamental equations (both homogeneous and non-homogeneous). Necessary and sufficient conditions are given for the solution to be rational or algebraic, and the solution is obtained in the general case. These results are applied to some simple queueing systems, for which the group is finite. The case of an arbitrary group is studied in Chapter 5, by reduction to a Riemann-Hilbert boundary value problem in the complex plane. Necessary and sufficient conditions for the process to be ergodic are obtained in a purely analytical way, by calculating the index of the boundary value problem (which corresponds roughly to the number of independent admissible solutions). The unknown functions are given by integral forms, which can be explicitly computed, via the Weierstrass $\wp$ function. In Chapter 6, the degenerate case is considered where the genus of the algebraic curve is 0. This case is practically important since it applies to certain priority queues and joined queues. The solutions in this case are even simpler. In Chapter 7, a number of related ideas and problems are explored briefly. These include explicit solutions, asymptotics and large deviations, generalized problems and analytic continuations, and problems outside the scope of probability. [FRom the Review by Kyle Siegrist]