Elements of Random Walk and Diffusion Processes E-Book

Oliver C. Ibe

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Serie: Wiley Series in Operations Research and Management Science
• Sprache: Englisch

Seitenzahl: 361

Veröffentlichungsjahr: 2013

Beschreibung

Presents an important and unique introduction to random walk theory Random walk is a stochastic process that has proven to be a useful model in understanding discrete-state discrete-time processes across a wide spectrum of scientific disciplines. Elements of Random Walk and Diffusion Processes provides an interdisciplinary approach by including numerous practical examples and exercises with real-world applications in operations research, economics, engineering, and physics. Featuring an introduction to powerful and general techniques that are used in the application of physical and dynamic processes, the book presents the connections between diffusion equations and random motion. Standard methods and applications of Brownian motion are addressed in addition to Levy motion, which has become popular in random searches in a variety of fields. The book also covers fractional calculus and introduces percolation theory and its relationship to diffusion processes. With a strong emphasis on the relationship between random walk theory and diffusion processes, Elements of Random Walk and Diffusion Processes features: * Basic concepts in probability, an overview of stochastic and fractional processes, and elements of graph theory * Numerous practical applications of random walk across various disciplines, including how to model stock prices and gambling, describe the statistical properties of genetic drift, and simplify the random movement of molecules in liquids and gases * Examples of the real-world applicability of random walk such as node movement and node failure in wireless networking, the size of the Web in computer science, and polymers in physics * Plentiful examples and exercises throughout that illustrate the solution of many practical problems Elements of Random Walk and Diffusion Processes is an ideal reference for researchers and professionals involved in operations research, economics, engineering, mathematics, and physics. The book is also an excellent textbook for upper-undergraduate and graduate level courses in probability and stochastic processes, stochastic models, random motion and Brownian theory, random walk theory, and diffusion process techniques.

Leseprobe

CONTENTS

PREFACE

ACKNOWLEDGMENTS

CHAPTER 1: REVIEW OF PROBABILITY THEORY

1.1 INTRODUCTION

1.2 RANDOM VARIABLES

1.3 TRANSFORM METHODS

1.4 COVARIANCE AND CORRELATION COEFFICIENT

1.5 SUMS OF INDEPENDENT RANDOM VARIABLES

1.6 SOME PROBABILITY DISTRIBUTIONS

1.7 LIMIT THEOREMS

PROBLEMS

CHAPTER 2: OVERVIEW OF STOCHASTIC PROCESSES

2.1 INTRODUCTION

2.2 CLASSIFICATION OF STOCHASTIC PROCESSES

2.3 MEAN AND AUTOCORRELATION FUNCTION

2.4 STATIONARY PROCESSES

2.5 POWER SPECTRAL DENSITY

2.6 COUNTING PROCESSES

2.7 INDEPENDENT INCREMENT PROCESSES

2.8 STATIONARY INCREMENT PROCESS

2.9 POISSON PROCESSES

2.10 MARKOV PROCESSES

2.11 GAUSSIAN PROCESSES

2.12 MARTINGALES

PROBLEMS

CHAPTER 3: ONE-DIMENSIONAL RANDOM WALK

3.1 INTRODUCTION

3.2 OCCUPANCY PROBABILITY

3.3 RANDOM WALK AS A MARKOV CHAIN

3.4 SYMMETRIC RANDOM WALK AS A MARTINGALE

3.5 RANDOM WALK WITH BARRIERS

3.6 MEAN-SQUARE DISPLACEMENT

3.7 GAMBLER’S RUIN

3.8 RANDOM WALK WITH STAY

3.9 FIRST RETURN TO THE ORIGIN

3.10 FIRST PASSAGE TIMES FOR SYMMETRIC RANDOM WALK

3.11 THE BALLOT PROBLEM AND THE REFLECTION PRINCIPLE

3.12 RETURNS TO THE ORIGIN AND THE ARC-SINE LAW

3.13 MAXIMUM OF A RANDOM WALK

3.14 TWO SYMMETRIC RANDOM WALKERS

3.15 RANDOM WALK ON A GRAPH

3.16 RANDOM WALKS AND ELECTRIC NETWORKS

3.17 CORRELATED RANDOM WALK

3.18 CONTINUOUS-TIME RANDOM WALK

3.19 REINFORCED RANDOM WALK

3.20 MISCELLANEOUS RANDOM WALK MODELS

3.21 SUMMARY

PROBLEMS

CHAPTER 4: TWO-DIMENSIONAL RANDOM WALK

4.1 INTRODUCTION

4.2 THE PEARSON RANDOM WALK

4.3 THE SYMMETRIC 2D RANDOM WALK

4.4 THE ALTERNATING RANDOM WALK

4.5 SELF-AVOIDING RANDOM WALK

4.6 NONREVERSING RANDOM WALK

4.7 EXTENSIONS OF THE NRRW

4.8 SUMMARY

CHAPTER 5: BROWNIAN MOTION

5.1 INTRODUCTION

5.2 BROWNIAN MOTION WITH DRIFT

5.3 BROWNIAN MOTION AS A MARKOV PROCESS

5.4 BROWNIAN MOTION AS A MARTINGALE

5.5 FIRST PASSAGE TIME OF A BROWNIAN MOTION

5.6 MAXIMUM OF A BROWNIAN MOTION

5.7 FIRST PASSAGE TIME IN AN INTERVAL

5.8 THE BROWNIAN BRIDGE

5.9 GEOMETRIC BROWNIAN MOTION

5.10 THE LANGEVIN EQUATION

5.11 SUMMARY

PROBLEMS

CHAPTER 6: INTRODUCTION TO STOCHASTIC CALCULUS

6.1 INTRODUCTION

6.2 THE ITO INTEGRAL

6.3 THE STOCHASTIC DIFFERENTIAL

6.4 THE ITO’S FORMULA

6.5 STOCHASTIC DIFFERENTIAL EQUATIONS

6.6 SOLUTION OF THE GEOMETRIC BROWNIAN MOTION

6.7 THE ORNSTEIN–UHLENBECK PROCESS

6.8 MEAN-REVERTING ORNSTEIN–UHLENBECK PROCESS

6.9 SUMMARY

CHAPTER 7: DIFFUSION PROCESSES

7.1 INTRODUCTION

7.2 MATHEMATICAL PRELIMINARIES

7.3 DIFFUSION ON ONE-DIMENSIONAL RANDOM WALK

7.4 EXAMPLES OF DIFFUSION PROCESSES

7.5 CORRELATED RANDOM WALK AND THE TELEGRAPH EQUATION

7.6 DIFFUSION AT FINITE SPEED

7.7 DIFFUSION ON SYMMETRIC TWO-DIMENSIONAL LATTICE RANDOM WALK

7.8 DIFFUSION APPROXIMATION OF THE PEARSON RANDOM WALK

7.9 SUMMARY

CHAPTER 8: LEVY WALK

8.1 INTRODUCTION

8.2 GENERALIZED CENTRAL LIMIT THEOREM

8.3 STABLE DISTRIBUTION

8.4 SELF-SIMILARITY

8.5 FRACTALS

8.6 LEVY DISTRIBUTION

8.7 LEVY PROCESS

8.8 INFINITE DIVISIBILITY

8.9 LEVY FLIGHT

8.10 TRUNCATED LEVY FLIGHT

8.11 LEVY WALK

8.12 SUMMARY

CHAPTER 9: FRACTIONAL CALCULUS AND ITS APPLICATIONS

9.1 INTRODUCTION

9.2 GAMMA FUNCTION

9.3 MITTAG–LEFFLER FUNCTIONS

9.4 LAPLACE TRANSFORM

9.5 FRACTIONAL DERIVATIVES

9.6 FRACTIONAL INTEGRALS

9.7 DEFINITIONS OF FRACTIONAL INTEGRO-DIFFERENTIALS

9.8 FRACTIONAL DIFFERENTIAL EQUATIONS

9.9 APPLICATIONS OF FRACTIONAL CALCULUS

9.10 SUMMARY

CHAPTER 10: PERCOLATION THEORY

10.1 INTRODUCTION

10.2 GRAPH THEORY REVISITED

10.3 PERCOLATION ON A LATTICE

10.4 CONTINUUM PERCOLATION

10.5 BOOTSTRAP (OR k-CORE) PERCOLATION

10.6 DIFFUSION PERCOLATION

10.7 FIRST-PASSAGE PERCOLATION

10.8 EXPLOSIVE PERCOLATION

10.9 PERCOLATION IN COMPLEX NETWORKS

10.10 SUMMARY

REFERENCES

INDEX

Copyright © 2013 by John Wiley & Sons, Inc. All rights reserved

Published by John Wiley & Sons, Inc., Hoboken, New JerseyPublished simultaneously in Canada

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone], or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, [phone], fax [phone], or online at http://www.wiley.com/go/permission.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at [phone], outside the United States at [phone] or fax [phone].

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data:

Ibe, Oliver C. (Oliver Chukwudi), 1947–Elements of random walk and diffusion processes / Oliver C. Ibe, University of Massachusetts Lowell, MA.pages cmIncludes bibliographical references and index.

ISBN 978-1-118-61809-7 (hardback)1. Random walks (Mathematics) 2. Diffusion processes. I. Title.QA274.73.I24 2013519.2′82–dc23

2013009389

Printed in the United States of America

ISBN: 9781118618097

10 9 8 7 6 5 4 3 2 1

PREFACE

This book is about random walks and the related subject of diffusion processes. The simplest definition of a random walk is that it is a stochastic process that consists of a sequence of discrete steps of fixed length. A more rigorous mathematical definition of a random walk is that it is a stochastic process that is formed by successive summation of independent and identically distributed random variables. In other words, it is a mathematical formalization of a trajectory that consists of taking successive random steps.

Random walk is related to numerous physical processes, including the Brownian motion, diffusion processes, and Levy flights. Consequently, it is used to explain observed behaviors of processes in several fields, including ecology, economics, psychology, computer science, physics, chemistry, and biology. The path traced by a molecule as it travels in a liquid or a gas, the search path of a foraging animal, the price of a fluctuating stock, and the financial status of a gambler can all be modeled as random walks. For example, the trajectory of insects on a horizontal planar surface may be accurately modeled as a random walk. In polymer physics, random walk is the simplest model to study polymers. Random walk accurately explains the relation between the time needed to make a decision and the probability that a certain decision will be made, which is a concept that is used in psychology. It is used in wireless networking to model node movements and node failures. It has been used in computer science to estimate the size of the World Wide Web. Also, in image processing, the random walker segmentation algorithm is used to determine the labels to associate with each pixel. Thus, random walk is a stochastic process that has proven to be a useful model in understanding several processes across a wide spectrum of scientific disciplines.

There are different types of random walks. Some random walks are on graphs while others are on the line, in the plane, or in higher dimensions. Random walks also vary with regard to the time parameter. In discrete-time random walks, the walker usually takes fixed-length steps in discrete time. In continuous-time random walks, the walker takes steps at random times, and the step length is usually a random variable.

The purpose of this book is to bring into one volume the different types of random walks and related topics, including Brownian motion, diffusion processes, and Levy flights. While many books have been written on random walks, our approach in this book is different. The book includes standard methods and applications of Brownian motion, which is considered a limit of random walk, and a discussion on Levy flights and Levy walk, which have become popular in random searches in ecology, finance, and other fields. It also includes a chapter on fractional calculus that is necessary for understanding anomalous (or fractional) diffusion, fractional Brownian motion, and fractional random walk. Finally, it introduces the reader to percolation theory and its relationship to diffusion processes. It is a self-contained book that will appeal to graduate students across science, engineering, and mathematics who need to understand the applications of random walk and diffusion process techniques, as well as to established researchers. It presents the connections between diffusion equations and random walks and introduces stochastic calculus, which is a prerequisite for understanding some of the modern concepts in Brownian motion and diffusion processes.

The chapters are organized as follows. Chapter 1 presents an introduction to probability while Chapter 2 gives an overview of stochastic processes. Chapter 3 discusses one-dimensional random walk while Chapter 4 discusses two-dimensional random walk. Chapter 5 discusses Brownian motion, Chapter 6 presents an introduction to stochastic calculus, and Chapter 7 discusses diffusion processes. Chapter 8 discusses Levy flights and Levy walk, Chapter 9 discusses fractional calculus and its applications, and Chapter 10 discusses percolation theory.

The book is written with the understanding that much of research on social networks, economics, finance, ecology, biostatistics, polymer physics, and population genetics has become interdisciplinary with random walk and diffusion processes as the common thread. Thus, it is truly a book designed for interdisciplinary use. It can be used for a one-semester course on stochastic processes and their applications.

OLIVER C. IBE

ACKNOWLEDGMENTS

My journey into the field of stochastic systems modeling started with my encounter at the Massachusetts Institute of Technology with two giants in the field, namely, the late Professor Alvin Drake, who was my academic adviser and under whom I was a teaching assistant in a course titled “Probabilistic Systems Analysis,” and Professor Robert Gallager, who was my adviser for both my master’s and doctoral theses. This book is a product of the wonderful instruction I received from these two great professors, and I sincerely appreciate all that they did to get me excited in this field.

This is the second project that I have completed with my editor, Ms. Susanne Steitz-Filler of Wiley. I am sincerely grateful to her for encouraging me and for being patient with me throughout the time it took to get the project completed. I would also like to thank Ms. Sari Friedman, an Editorial Assistant at Wiley, for ensuring that the production schedule is met. This is also my second project with her. I am grateful to the anonymous reviewers for their comments that helped to improve the quality of the book.

Finally, I would like to thank my wife, Christina, and our children Chidinma, Ogechi, Amanze, and Ugonna, for the joy they have brought to my life. I could not have completed this project without their encouragement.

CHAPTER 1

REVIEW OF PROBABILITY THEORY

1.1 INTRODUCTION

1.2 RANDOM VARIABLES

Consider a random experiment with sample spaceΩ. Letwbe a sample point inΩ. We are interested in assigning a real number to eachw∈Ω. A random variable,X(w), is a single-valued real function that assigns a real number, called the value ofX(w), to each sample pointw∈Ω. That is, it is a mapping of the sample space onto the real line.

Generally, a random variable is represented by a single letter X instead of the function X(w). Therefore, in the remainder of the book we use X to denote a random variable. The sample space Ω is called the domain of the random variable X. Also, the collection of all numbers that are values of X is called the range of the random variable X.

Let X be a random variable and x a fixed real value. Let the event Ax define the subset of Ω that consists of all real sample points to which the random variable X assigns the number x. That is,

Since Ax is an event, it will have a probability, which we define as follows:

We can define other types of events in terms of a random variable. For fixed numbers x, a, and b, we can define the following: