Random Walks in the Quarter-Plane

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.