Dynamic Random Walks: Theory and Applications
()
About this ebook
· New probabilistic model, new results in probability theory
· Original applications in computer science
· Applications in mathematical physics
· Applications in finance
Nadine Guillotin-Plantard
Nadine GUILLOTIN-PLANTARD has been Maître de Conférences (i.e. Associate Professor) at the University Claude Bernard, Lyon, France since 1998. Here research interests include the study of time and/or space dependent random walks and their applications in computer science, biology and finance. She serves as referee for many journals in mathematics and authored or co-authored more than 20 published journal papers.
Related to Dynamic Random Walks
Related ebooks
Stochastic Analysis of Mixed Fractional Gaussian Processes Rating: 0 out of 5 stars0 ratingsSubmodular Functions and Optimization Rating: 0 out of 5 stars0 ratingsReal Analysis: A Historical Approach Rating: 0 out of 5 stars0 ratingsStochastic Control by Functional Analysis Methods Rating: 0 out of 5 stars0 ratingsEssential Computational Modeling in Chemistry Rating: 0 out of 5 stars0 ratingsFermat Days 85: Mathematics for Optimization Rating: 0 out of 5 stars0 ratingsErgodic Theory and Topological Dynamics Rating: 0 out of 5 stars0 ratingsMathematical Methods of Statistics (PMS-9), Volume 9 Rating: 3 out of 5 stars3/5Infinite Abelian Groups Rating: 0 out of 5 stars0 ratingsAgent-Based Computational Sociology Rating: 0 out of 5 stars0 ratingsDynamic Programming and Stochastic Control Rating: 3 out of 5 stars3/5Mathematical Experiments on the Computer Rating: 0 out of 5 stars0 ratingsRandom Matrices and the Statistical Theory of Energy Levels Rating: 0 out of 5 stars0 ratingsMachine Learning Proceedings 1991: Proceedings of the Eighth International Workshop (ML91) Rating: 0 out of 5 stars0 ratingsExact Statistical Inference for Categorical Data Rating: 0 out of 5 stars0 ratingsPseudorandomness and Cryptographic Applications Rating: 0 out of 5 stars0 ratingsTransformations: Mathematical Approaches to Culture Change Rating: 0 out of 5 stars0 ratingsMathematical Methods of Reliability Theory Rating: 0 out of 5 stars0 ratingsFoundations of Genetic Algorithms 1991 (FOGA 1) Rating: 0 out of 5 stars0 ratingsA Mathematical Kaleidoscope: Applications in Industry, Business and Science Rating: 0 out of 5 stars0 ratingsArtificial Neural Systems: Principle and Practice Rating: 0 out of 5 stars0 ratingsFoundations of Stochastic Analysis Rating: 0 out of 5 stars0 ratingsQuantum Theory of Collective Phenomena Rating: 0 out of 5 stars0 ratingsGraphs, Dynamic Programming and Finite Games Rating: 0 out of 5 stars0 ratingsCausality and Modern Science: Third Revised Edition Rating: 4 out of 5 stars4/5Automated Theorem Proving: A Logical Basis Rating: 0 out of 5 stars0 ratingsMachine Learning for Future Fiber-Optic Communication Systems Rating: 0 out of 5 stars0 ratingsSymmetry: An Introduction to Group Theory and Its Applications Rating: 2 out of 5 stars2/5
Mathematics For You
Introducing Game Theory: A Graphic Guide Rating: 4 out of 5 stars4/5Basic Math & Pre-Algebra For Dummies Rating: 4 out of 5 stars4/5Calculus For Dummies Rating: 4 out of 5 stars4/5Algebra - The Very Basics Rating: 5 out of 5 stars5/5Geometry For Dummies Rating: 5 out of 5 stars5/5Basic Math Notes Rating: 5 out of 5 stars5/5Quantum Physics for Beginners Rating: 4 out of 5 stars4/5Game Theory: A Simple Introduction Rating: 4 out of 5 stars4/5My Best Mathematical and Logic Puzzles Rating: 5 out of 5 stars5/5Algebra I Workbook For Dummies Rating: 3 out of 5 stars3/5The Everything Guide to Algebra: A Step-by-Step Guide to the Basics of Algebra - in Plain English! Rating: 4 out of 5 stars4/5Mental Math Secrets - How To Be a Human Calculator Rating: 5 out of 5 stars5/5The Everything Everyday Math Book: From Tipping to Taxes, All the Real-World, Everyday Math Skills You Need Rating: 5 out of 5 stars5/5See Ya Later Calculator: Simple Math Tricks You Can Do in Your Head Rating: 4 out of 5 stars4/5Calculus Made Easy Rating: 4 out of 5 stars4/5The Elements of Euclid for the Use of Schools and Colleges (Illustrated) Rating: 0 out of 5 stars0 ratingsThe Golden Ratio: The Divine Beauty of Mathematics Rating: 5 out of 5 stars5/5Is God a Mathematician? Rating: 4 out of 5 stars4/5ACT Math & Science Prep: Includes 500+ Practice Questions Rating: 3 out of 5 stars3/5The Thirteen Books of the Elements, Vol. 1 Rating: 0 out of 5 stars0 ratingsRelativity: The special and the general theory Rating: 5 out of 5 stars5/5A Mind for Numbers | Summary Rating: 4 out of 5 stars4/5GED® Math Test Tutor, 2nd Edition Rating: 0 out of 5 stars0 ratingsAlgebra I For Dummies Rating: 4 out of 5 stars4/5
Reviews for Dynamic Random Walks
0 ratings0 reviews
Book preview
Dynamic Random Walks - Nadine Guillotin-Plantard
Nelly.
Preface
The theory of random walks has a long history which goes back (at least) to the start of the last century. Feller’s books [49, 50] contain preliminary material on the topic. Spitzer’s book [177] is a friendly introduction to the domain. Self-avoiding random walks have been intensively investigated in connection with problems in physics and percolation theory. In the 70’s the study of random walks on non-commutative algebraic structures (Lie groups, homogeneous spaces, hypergroups, …) has become an important area of research [79, 81]. Meanwhile random walk tools have found many applications in computer science including algorithm analysis [132] as well as in other fields. More recently [68, 69, 70] dynamic random walks have been introduced and investigated. The main purpose of this book is to report on the progress realized in the emerging domain of dynamic random walks. We provide a smooth introduction to this area and present some applications in computer science and option pricing in financial markets. Most of the material is scattered throughout available literature, however, we have nowhere found all of this material collected in accessible form. The theory of dynamic random walks as exposed in this book has been developed by N. Guillotin-Plantard [68, 69, 70]. The applications in computer science presented in this book are mostly based on joint works between N. Guillotin-Plantard and R. Schott. More applications of random walks in computer science are described in [132]. The model of dynamic financial market based on (binomial) dynamic random walks presented in this book may be considered to be a small step towards option pricing when decisions are time dependent random variables.
Part I is devoted to theoretical aspects of dynamic random walks: Chapter 1 contains some preliminaries and basic definitions. Limit theorems (law of large numbers, central limit theorem, local limit theorem, law of the iterated logarithm, large deviation principle as well as results aboutrecurrence and transience which are consequences of three first mentioned limit theorems) are given in Chapter 2 and 3. Some aspects of dynamic random walks in a random scenery are exposed in Chapter 4 (the reader may consult the bibliography for complements). Chapter 5 is devoted to ergodic theorems, here we use a slightly different dynamic random-walk model. Dynamic random walks on Heisenberg groups are investigated in Chapter 6. Chapter 7 is devoted to dynamic quantum Bernoulli random walks.
Part II contains several applications of the results stated in Part I: Chapter 8 revisits some distributed algorithms whose analysis has been started in the 70’s by D.E. Knuth then continued by A. Yao, P. Flajolet, G. Louchard, R. Maier, and the second author of the present book. A similar study is done in Chapter 9 for dynamic data structures whose combinatorial analysis goes also back to D.E. Knuth and was also continued by some of the above mentioned researchers in collaboration with J. Francon, C. Kenyon-Mathieu, C. Puel and J. Vuillemin. Chapter 10 presents results obtained by N. Guillotin-Plantard and A. Le Ny on random walks on dynamically oriented lattices. Chapter 11 reports on work in progress on the use of the binomial dynamic random-walk model in financial mathematics. Few appendices will help refreshing memories (if necessary!) and provide adapted places for some intricate technical results.
Finally we would mention that M. Lin, B. Rubshtein and A.L. Wittmann [116] have developed a more abstract theory of random walks with dynamic random transitions on locally compact groups.
This book is intended for mathematicians, computer scientists and all researchers interested by recent developments in probability theory and their applications. Each chapter contains didactical material as well as advanced technical sections.
The authors are particularly grateful to B. Pinson for his help on per-forming simulations and solving a differential equation, to D. Petritis for his scientific advises, to F. Comets, F. Delarue, C. Dombry, A. Le Ny and H. Schurz for allowing us to use material which is joint work with the present authors and to our colleagues from IECN, LORIA and Institut C. Jordan for stimulating discussions.
Part I
THEORETICAL ASPECTS
Chapter 1
PRELIMINARIES ON DYNAMIC RANDOM WALKS
1 INTRODUCTION
Consider a particle which moves randomly along the x-axis, coming to rest only at the points x = …, −2, −1, 0, 1, 2, … with integral coordinates. Suppose the particle’s motion is such that once at a point i, it jumps at the next step to either the point i + 1 or the point i − 1 with probabilities p and q = 1 − p, respectively. Let S(n) be the particle’s position after n steps. Then the sequence S(0) → S(1) → S(2) → … is a Markov chain with transition probabilities
S(n) is a one-dimensional random walk which is often used in many areas including physics, computer science, information theory, mathematical finance, games theory, … For example physicists use such a random-walk model as a crude approximation to one-dimensional diffusion or Brownian motion: A physical particle is exposed to a great number of molecular collisions which impart to it a random motion. The case p > q , the random walk is called symmetric.
The classical ruin problem uses a similar model: Consider the gambler who wins or loses a dollar with probability p and q, respectively. Let his capital be z and let him play against an adversary with initial capital a − z, so that the combined capital is a. The game continues until the gambler’s capital either is reduced to zero or has increased to a, that is, until one of the two players is ruined. One is interested in the probability distribution of the duration of the game.
The banker algorithm (whose analysis is presented in the second part of this book, see also [120, 121, 124, 132]) provides another interesting application of similar random-walk models: Consider (for simplicity) two customers C1 and C2 sharing a given resource m (money). There are fixed upper bounds m1 and m2 on how much of the resource each of the customers is allowed to use at any time. The banker decides to affect to the customer Ci, i = 1,2 the required resource units only if the remaining units are sufficient in order to fulfill the requirements of Cj, j = 1, 2; j ≠ i. The natural formulation of this algorithm is in terms of random walks in a rectangle with a broken corner, i.e.,
where the last constraint generates the broken corner. The random walk Ym(.) has four reflecting barriers (R) and one absorbing barrier (A) as shown in Figure 1.1. The distribution of steps (steps of unit length) ΔY is given by:
p1 + q1 + p2 + q2 = 1) with the boundary conditions of Figure 1.1. The hitting place and the hitting time of the absorbing boundary are the parameters of interest in computer science.
Figure 1.1 Banker algorithm
We believe that the reader is aware of similar examples where such random-walk models fit in.
The above introduced random-walk model would be more realistic if pi (and therefore qi), i = 1,2, would be time and space dependent.
Random walks with probabilities varying from place to place have been intensively studied (see [49, 50] for example).
The main purpose of this hook is to introduce and investigate a dynamic random-walk model which is closer to real-world applications.
2 DEFINITIONS
Let S = (E, A, μ, T) be a dynamical system where (E, A, μ) is a probability space and T is a transformation defined on E. Let d ≥ 1 and f1, …, fd be functions defined on E . Let (Xi)id. Let x ∈ E and (ei)1≤j≤d d. For every i ≥ 1, the law of the random vector Xi is given by
We write
d-random walk generated by the family (Xi)i≥1. The random sequence (Sn)nd-random walk.
It is worth remarking that if the functions fj are constant then we have the classical random walks but if these functions are not all constant, (Sn)nis a non-homogeneous Markov chain. The dynamic random walks were introduced and studied by the first author in [68], [69], [70]. They are of some relevance in the statistical mechanics of quasiperiodic systems in the presence of external spatial disorder (see [51], [83] and [104]).
Let C1(S) denote the class of functions f ∈ L¹ (E, μ) satisfying the following condition (H1): there exists a set E0 ⊆ E with probability 1 such that for every x ∈ E0,
Let C2(S) denote the class of functions f ∈ L¹(E, μ) satisfying the following condition (H2):
Let C3(S) denote the class of functions f ∈ L¹(E, μ) satisfying the following condition (H3):
We assume that for 1 ≤ i ≤ dand denote by A = (aij)1≤i,j≤d the matrix with coefficients
The matrix A so A is nonnegative definite.
3 A RIEMANNIAN DYNAMIC RANDOM WALK
Let f1, …, fd and (Xi,n)1≤i≤n d with distribution
(1.1)
We write
this n-dynamic random walk. This random walk is more difficult to study than the previous one due to the presence of n in the transition probabilities which creates much more temporal inhomogeneity.
PROPOSITION 1: Let f be a one-periodic function which can be expanded into a Fourier series f(x) = Σhche²πihx.
When there exists β > 1 such that |cn| + |c−n| = O(n−β), then
The proof of the proposition is straightforward. When the functions f1, …, fd can be expanded into a Fourier series
and there exists βj > 1 such that
Remark: Thanks to the above uniform inequality all limit theorems which we are going to prove in the next chapters for the dynamic random walk defined in 2. can be adapted for the dynamic random walk given by (1.1).