Random Walks in the Quarter-Plane: Algebraic Methods, Boundary Value Problems and Applications

ISBN-13: 9783642642173 / Angielski / Miękka / 2011 / 156 str.

Guy Fayolle; Roudolf Iasnogorodski; Vadim Malyshev

Opis

Historical Comments Two-dimensional random walks in domains with non-smooth boundaries inter- est several groups of the mathematical community. In fact these objects are encountered in pure probabilistic problems, as well as in applications involv- ing queueing theory. This monograph aims at promoting original mathematical methods to determine the invariant measure of such processes. Moreover, as it will emerge later, these methods can also be employed to characterize the transient behavior. It is worth to place our work in its historical context. This book has three sources. l. Boundary value problems for functions of one complex variable; 2. Singular integral equations, Wiener-Hopf equations, Toeplitz operators; 3. Random walks on a half-line and related queueing problems. The first two topics were for a long time in the center of interest of many well known mathematicians: Riemann, Sokhotski, Hilbert, Plemelj, Carleman, Wiener, Hopf. This one-dimensional theory took its final form in the works of Krein, Muskhelishvili, Gakhov, Gokhberg, etc. The third point, and the related probabilistic problems, have been thoroughly investigated by Spitzer, Feller, Baxter, Borovkov, Cohen, etc.

Spis treści

and History.- 1 Probabilistic Background.- 1.1 Markov Chains.- 1.2 Random Walks in a Quarter Plane.- 1.3 Functional Equations for the Invariant Measure.- 2 Foundations of the Analytic Approach.- 2.1 Fundamental Notions and Definitions.- 2.1.1 Covering Manifolds.- 2.1.2 Algebraic Functions.- 2.1.3 Elements of Galois Theory.- 2.1.4 Universal Cover and Uniformization.- 2.1.5 Abelian Differentials and Divisors.- 2.2 Restricting the Equation to an Algebraic Curve.- 2.2.1 First Insight (Algebraic Functions).- 2.2.2 Second Insight (Algebraic Curve).- 2.2.3 Third Insight (Factorization).- 2.2.4 Fourth Insight (Riemann Surfaces).- 2.3 The Algebraic Curve Q(x, y) = 0.- 2.3.1 Branches of the Algebraic Functions on the Unit Circle.- 2.3.2 Branch Points.- 2.4 Galois Automorphisms and the Group of the Random Walk.- 2.4.1 Construction of the Automorphisms ?? and ?? on S.- 2.5 Reduction of the Main Equation to the Riemann Torus.- 3 Analytic Continuation of the Unknown Functions in the Genus 1 Case.- 3.1 Lifting the Fundamental Equation onto the Universal Covering.- 3.1.1 Lifting of the Branch Points.- 3.1.2 Lifting of the Automorphisms on the Universal Covering.- 3.2 Analytic Continuation.- 3.3 More about Uniformization.- 4 The Case of a Finite Group.- 4.1On the Conditions for H to be Finite.- 4.1.1 Explicit Conditions for Groups of Order 4 or 6.- 4.1.2 The General Case.- 4.2 Rational Solutions.- 4.2.1 The Case N(f) ? 1.- 4.2.2 The Case N(f) = 1.- 4.3 Algebraic Solution.- 4.3.1 The Case N(f) = 1.- 4.3.2 The Case N(f) ?.- 4.4 Final Form of the General Solution.- 4.5 The Problem of the Poles and Examples.- 4.5.1 Rational Solutions.- 4.5.1.1 Reversible Random Walks.- 4.5.1.2 Simple Examples of Nonreversible Random Walks.- 4.5.1.3 One Parameter Families.- 4.5.1.4 Two Typical Situations.- 4.5.1.5 Ergodicity Conditions.- 4.5.1.6 Proof of Lemma 4.5.2.- 4.6 An Example of Algebraic Solution by Flatto and Hahn.- 4.7 Two Queues in Tandem.- 5 Solution in the Case of an Arbitrary Group.- 5.1 Informal Reduction to a Riemann-Hilbert-Carleman BVP.- 5.2 Introduction to BVP in the Complex Plane.- 5.2.1 A Bit of History.- 5.2.2 The Sokhotski-Plemelj Formulae.- 5.2.3 The Riemann Boundary Value Problem for a Closed Contour.- 5.2.4 The Riemann BVP for an Open Contour.- 5.2.5 The Riemann-Carleman Problem with a Shift.- 5.3 Further Properties of the Branches Defined by Q(x, y)= 0.- 5.4 Index and Solution of the BVP (5.1.5).- 5.5 Complements.- 5.5.1 Analytic Continuation.- 5.5.2 Computation of w.- 5.5.2.1 An Explicit Form via the Weierstrass ?-Function..- 5.5.2.2 A Differential Equation.- 5.5.2.3 An Integral Equation.- 6 The Genus 0 Case.- 6.1 Properties of the Branches.- 6.2 Case 1: ?01 = ??1,0 = ??1,1 = 0.- 6.3 Case 3: ?11 = ?10 = ?01 = 0.- 6.4 Case 4: ??1,0 = ?0,?1 = ??1,?1= 0.- 6.4.1 Integral Equation.- 6.4.2 Series Representation.- 6.4.3 Uniformization.- 6.4.4 Boundary Value Problem.- 6.5 Case 5: MZ= My= 0.- 7 Miscellanea.- 7.1 About Explicit Solutions.- 7.2 Asymptotics.- 7.2.1 Large Deviations and Stationary Probabilities.- 7.3 Generalized Problems and Analytic Continuation.- 7.4 Outside Probability.- References.