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…mehr
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.Hinweis: Dieser Artikel kann nur an eine deutsche Lieferadresse ausgeliefert werden.
OLIVER C. IBE, ScD, is Associate Professor in the Department of Electrical and Computer Engineering at the University of Massachusetts at Lowell. He has more than thirty years of experience in academia and the telecommunications industry in various technical and management capacities. Dr. Ibe's research interests include stochastic systems modeling, bioinformatics, and communication network performance modeling. He is the author of Converged Network Architectures: Delivering Voice over IP, ATM, and Frame Relay and Fundamentals of Stochastic Networks, both published by Wiley.
Inhaltsangabe
Preface xiii Acknowledgments xv 1 Review of Probability Theory 1 1.1 Introduction 1 1.2 Random Variables 1 1.2.1 Distribution Functions 2 1.2.2 Discrete Random Variables 3 1.2.3 Continuous Random Variables 3 1.2.4 Expectations 4 1.2.5 Moments of Random Variables and the Variance 4 1.3 Transform Methods 5 1.3.1 The Characteristic Function 5 1.3.2 Moment-Generating Property of the Characteristic Function 6 1.3.3 The s-Transform 6 1.3.4 Moment-Generating Property of the s-Transform 7 1.3.5 The z-Transform 7 1.3.6 Moment-Generating Property of the z-Transform 8 1.4 Covariance and Correlation Coefficient 9 1.5 Sums of Independent Random Variables 10 1.6 Some Probability Distributions 11 1.6.1 The Bernoulli Distribution 11 1.6.2 The Binomial Distribution 12 1.6.3 The Geometric Distribution 12 1.6.4 The Poisson Distribution 13 1.6.5 The Exponential Distribution 13 1.6.6 Normal Distribution 14 1.7 Limit Theorems 16 1.7.1 Markov Inequality 16 1.7.2 Chebyshev Inequality 17 1.7.3 Laws of Large Numbers 17 1.7.4 The Central Limit Theorem 18 Problems 19 2 Overview of Stochastic Processes 21 2.1 Introduction 21 2.2 Classification of Stochastic Processes 22 2.3 Mean and Autocorrelation Function 22 2.4 Stationary Processes 23 2.4.1 Strict-Sense Stationary Processes 23 2.4.2 Wide-Sense Stationary Processes 24 2.5 Power Spectral Density 24 2.6 Counting Processes 25 2.7 Independent Increment Processes 25 2.8 Stationary Increment Process 25 2.9 Poisson Processes 26 2.9.1 Compound Poisson Process 28 2.10 Markov Processes 29 2.10.1 Discrete-Time Markov Chains 30 2.10.2 State Transition Probability Matrix 31 2.10.3 The k-Step State Transition Probability 31 2.10.4 State Transition Diagrams 32 2.10.5 Classification of States 33 2.10.6 Limiting-State Probabilities 34 2.10.7 Doubly Stochastic Matrix 35 2.10.8 Continuous-Time Markov Chains 35 2.10.9 Birth and Death Processes 36 2.11 Gaussian Processes 38 2.12 Martingales 38 2.12.1 Stopping Times 40 Problems 41 3 One-Dimensional Random Walk 44 3.1 Introduction 44 3.2 Occupancy Probability 46 3.3 Random Walk as a Markov Chain 49 3.4 Symmetric Random Walk as a Martingale 49 3.5 Random Walk with Barriers 50 3.6 Mean-Square Displacement 50 3.7 Gambler's Ruin 52 3.7.1 Ruin Probability 52 3.7.2 Alternative Derivation of Ruin Probability 54 3.7.3 Duration of a Game 55 3.8 Random Walk with Stay 56 3.9 First Return to the Origin 57 3.10 First Passage Times for Symmetric Random Walk 59 3.10.1 First Passage Time via the Generating Function 59 3.10.2 First Passage Time via the Reflection Principle 61 3.10.3 Hitting Time and the Reflection Principle 64 3.11 The Ballot Problem and the Reflection Principle 65 3.11.1 The Conditional Probability Method 66 3.12 Returns to the Origin and the Arc-Sine Law 67 3.13 Maximum of a Random Walk 72 3.14 Two Symmetric Random Walkers 73 3.15 Random Walk on a Graph 73 3.15.1 Proximity Measures 75 3.15.2 Directed Graphs 75 3.15.3 Random Walk on an Undirected Graph 76 3.15.4 Random Walk on a Weighted Graph 80 3.16 Random Walks and Electric Networks 80 3.16.1 Harmonic Functions 82 3.16.2 Effective Resistance and Escape Probability 82 3.17 Correlated Random Walk 85 3.18 Continuous-Time Random Walk 90 3.18.1 The Master Equation 92 3.19 Reinforced Random Walk 94 3.19.1 Polya's Urn Model 94 3.19.2 ERRW and Polya's Urn 96 3.19.3 ERRW Revisited 97 3.20 Miscellaneous Random Walk Models 98 3.20.1 Geometric Random Walk 98 3.20.2 Gaussian Random Walk 99 3.20.3 Random Walk with Memory 99 3.21 Summary 100 Problems 100 4 Two-Dimensional Random Walk 103 4.1 Introduction 103 4.2 The Pearson Random Walk 105 4.2.1 Mean-Square Displacement 105 4.2.2 Probability Distribution 107 4.3 The Symmetric 2D Random Walk 110 4.3.1 Stirling's Approximation of Symmetric Walk 112 4.3.2 Probability of Eventual Return for Symmetric Walk 113 4.3.3 Mean-Square Displacement 114 4.3.4 Two Independent Symmetric 2D Random Walkers 114 4.4 The Alternating Random Walk 115 4.4.1 Stirling's Approximation of Alternating Walk 117 4.4.2 Probability of Eventual Return for Alternating Walk 117 4.5 Self-Avoiding Random Walk 117 4.6 Nonreversing Random Walk 121 4.7 Extensions of the NRRW 126 4.7.1 The Noncontinuing Random Walk 126 4.7.2 The Nonreversing and Noncontinuing Random Walk 127 4.8 Summary 128 5 Brownian Motion 129 5.1 Introduction 129 5.2 Brownian Motion with Drift 132 5.3 Brownian Motion as a Markov Process 132 5.4 Brownian Motion as a Martingale 133 5.5 First Passage Time of a Brownian Motion 133 5.6 Maximum of a Brownian Motion 135 5.7 First Passage Time in an Interval 135 5.8 The Brownian Bridge 136 5.9 Geometric Brownian Motion 137 5.10 The Langevin Equation 137 5.11 Summary 141 Problems 141 6 Introduction to Stochastic Calculus 143 6.1 Introduction 143 6.2 The Ito Integral 145 6.3 The Stochastic Differential 146 6.4 The Ito's Formula 147 6.5 Stochastic Differential Equations 147 6.6 Solution of the Geometric Brownian Motion 148 6.7 The Ornstein-Uhlenbeck Process 151 6.7.1 Solution of the Ornstein-Uhlenbeck SDE 152 6.7.2 First Alternative Solution Method 153 6.7.3 Second Alternative Solution Method 154 6.8 Mean-Reverting Ornstein-Uhlenbeck Process 155 6.9 Summary 157 7 Diffusion Processes 158 7.1 Introduction 158 7.2 Mathematical Preliminaries 159 7.3 Diffusion on One-Dimensional Random Walk 160 7.3.1 Alternative Derivation 163 7.4 Examples of Diffusion Processes 164 7.4.1 Brownian Motion 164 7.4.2 Brownian Motion with Drift 167 7.5 Correlated Random Walk and the Telegraph Equation 167 7.6 Diffusion at Finite Speed 170 7.7 Diffusion on Symmetric Two-Dimensional Lattice Random Walk 171 7.8 Diffusion Approximation of the Pearson Random Walk 173 7.9 Summary 174 8 Levy Walk 175 8.1 Introduction 175 8.2 Generalized Central Limit Theorem 175 8.3 Stable Distribution 177 8.4 Self-Similarity 182 8.5 Fractals 183 8.6 Levy Distribution 185 8.7 Levy Process 186 8.8 Infinite Divisibility 186 8.8.1 The Infinite Divisibility of the Poisson Process 187 8.8.2 Infinite Divisibility of the Compound Poisson Process 187 8.8.3 Infinite Divisibility of the Brownian Motion with Drift 188 8.9 Levy Flight 188 8.9.1 First Passage Time of Levy Flights 190 8.9.2 Leapover Properties of Levy Flights 190 8.10 Truncated Levy Flight 191 8.11 Levy Walk 191 8.11.1 Levy Walk as a Coupled CTRW 192 8.11.2 Truncated Levy Walk 195 8.12 Summary 195 9 Fractional Calculus and Its Applications 196 9.1 Introduction 196 9.2 Gamma Function 197 9.3 Mittag-Leffler Functions 198 9.4 Laplace Transform 200 9.5 Fractional Derivatives 202 9.6 Fractional Integrals 203 9.7 Definitions of Fractional Integro-Differentials 203 9.7.1 Riemann-Liouville Fractional Derivative 204 9.7.2 Caputo Fractional Derivative 205 9.7.3 Grunwald-Letnikov Fractional Derivative 206 9.8 Fractional Differential Equations 207 9.8.1 Relaxation Differential Equation of Integer Order 208 9.8.2 Oscillation Differential Equation of Integer Order 208 9.8.3 Relaxation and Oscillation Fractional Differential Equations 209 9.9 Applications of Fractional Calculus 210 9.9.1 Fractional Brownian Motion 210 9.9.2 Multifractional Brownian Motion 213 9.9.3 Fractional Random Walk 213 9.9.4 Fractional (or Anomalous) Diffusion 215 9.9.5 Fractional Gaussian Noise 221 9.9.6 Fractional Poisson Process 222 9.10 Summary 224 10 Percolation Theory 225 10.1 Introduction 225 10.2 Graph Theory Revisited 226 10.2.1 Complete Graphs 226 10.2.2 Random Graphs 226 10.3 Percolation on a Lattice 228 10.3.1 Cluster Formation and Phase Transition 229 10.3.2 Percolation Probability and Critical Exponents 233 10.4 Continuum Percolation 235 10.4.1 The Boolean Model 235 10.4.2 The Random Connection Model 236 10.5 Bootstrap (or k-Core) Percolation 237 10.6 Diffusion Percolation 237 10.6.1 Bootstrap Percolation versus Diffusion Percolation 239 10.7 First-Passage Percolation 239 10.8 Explosive Percolation 240 10.9 Percolation in Complex Networks 242 10.9.1 Average Path Length 243 10.9.2 Clustering Coefficient 243 10.9.3 Degree Distribution 244 10.9.4 Percolation and Network Resilience 244 10.10 Summary 245 References 247 Index 253
Preface xiii Acknowledgments xv 1 Review of Probability Theory 1 1.1 Introduction 1 1.2 Random Variables 1 1.2.1 Distribution Functions 2 1.2.2 Discrete Random Variables 3 1.2.3 Continuous Random Variables 3 1.2.4 Expectations 4 1.2.5 Moments of Random Variables and the Variance 4 1.3 Transform Methods 5 1.3.1 The Characteristic Function 5 1.3.2 Moment-Generating Property of the Characteristic Function 6 1.3.3 The s-Transform 6 1.3.4 Moment-Generating Property of the s-Transform 7 1.3.5 The z-Transform 7 1.3.6 Moment-Generating Property of the z-Transform 8 1.4 Covariance and Correlation Coefficient 9 1.5 Sums of Independent Random Variables 10 1.6 Some Probability Distributions 11 1.6.1 The Bernoulli Distribution 11 1.6.2 The Binomial Distribution 12 1.6.3 The Geometric Distribution 12 1.6.4 The Poisson Distribution 13 1.6.5 The Exponential Distribution 13 1.6.6 Normal Distribution 14 1.7 Limit Theorems 16 1.7.1 Markov Inequality 16 1.7.2 Chebyshev Inequality 17 1.7.3 Laws of Large Numbers 17 1.7.4 The Central Limit Theorem 18 Problems 19 2 Overview of Stochastic Processes 21 2.1 Introduction 21 2.2 Classification of Stochastic Processes 22 2.3 Mean and Autocorrelation Function 22 2.4 Stationary Processes 23 2.4.1 Strict-Sense Stationary Processes 23 2.4.2 Wide-Sense Stationary Processes 24 2.5 Power Spectral Density 24 2.6 Counting Processes 25 2.7 Independent Increment Processes 25 2.8 Stationary Increment Process 25 2.9 Poisson Processes 26 2.9.1 Compound Poisson Process 28 2.10 Markov Processes 29 2.10.1 Discrete-Time Markov Chains 30 2.10.2 State Transition Probability Matrix 31 2.10.3 The k-Step State Transition Probability 31 2.10.4 State Transition Diagrams 32 2.10.5 Classification of States 33 2.10.6 Limiting-State Probabilities 34 2.10.7 Doubly Stochastic Matrix 35 2.10.8 Continuous-Time Markov Chains 35 2.10.9 Birth and Death Processes 36 2.11 Gaussian Processes 38 2.12 Martingales 38 2.12.1 Stopping Times 40 Problems 41 3 One-Dimensional Random Walk 44 3.1 Introduction 44 3.2 Occupancy Probability 46 3.3 Random Walk as a Markov Chain 49 3.4 Symmetric Random Walk as a Martingale 49 3.5 Random Walk with Barriers 50 3.6 Mean-Square Displacement 50 3.7 Gambler's Ruin 52 3.7.1 Ruin Probability 52 3.7.2 Alternative Derivation of Ruin Probability 54 3.7.3 Duration of a Game 55 3.8 Random Walk with Stay 56 3.9 First Return to the Origin 57 3.10 First Passage Times for Symmetric Random Walk 59 3.10.1 First Passage Time via the Generating Function 59 3.10.2 First Passage Time via the Reflection Principle 61 3.10.3 Hitting Time and the Reflection Principle 64 3.11 The Ballot Problem and the Reflection Principle 65 3.11.1 The Conditional Probability Method 66 3.12 Returns to the Origin and the Arc-Sine Law 67 3.13 Maximum of a Random Walk 72 3.14 Two Symmetric Random Walkers 73 3.15 Random Walk on a Graph 73 3.15.1 Proximity Measures 75 3.15.2 Directed Graphs 75 3.15.3 Random Walk on an Undirected Graph 76 3.15.4 Random Walk on a Weighted Graph 80 3.16 Random Walks and Electric Networks 80 3.16.1 Harmonic Functions 82 3.16.2 Effective Resistance and Escape Probability 82 3.17 Correlated Random Walk 85 3.18 Continuous-Time Random Walk 90 3.18.1 The Master Equation 92 3.19 Reinforced Random Walk 94 3.19.1 Polya's Urn Model 94 3.19.2 ERRW and Polya's Urn 96 3.19.3 ERRW Revisited 97 3.20 Miscellaneous Random Walk Models 98 3.20.1 Geometric Random Walk 98 3.20.2 Gaussian Random Walk 99 3.20.3 Random Walk with Memory 99 3.21 Summary 100 Problems 100 4 Two-Dimensional Random Walk 103 4.1 Introduction 103 4.2 The Pearson Random Walk 105 4.2.1 Mean-Square Displacement 105 4.2.2 Probability Distribution 107 4.3 The Symmetric 2D Random Walk 110 4.3.1 Stirling's Approximation of Symmetric Walk 112 4.3.2 Probability of Eventual Return for Symmetric Walk 113 4.3.3 Mean-Square Displacement 114 4.3.4 Two Independent Symmetric 2D Random Walkers 114 4.4 The Alternating Random Walk 115 4.4.1 Stirling's Approximation of Alternating Walk 117 4.4.2 Probability of Eventual Return for Alternating Walk 117 4.5 Self-Avoiding Random Walk 117 4.6 Nonreversing Random Walk 121 4.7 Extensions of the NRRW 126 4.7.1 The Noncontinuing Random Walk 126 4.7.2 The Nonreversing and Noncontinuing Random Walk 127 4.8 Summary 128 5 Brownian Motion 129 5.1 Introduction 129 5.2 Brownian Motion with Drift 132 5.3 Brownian Motion as a Markov Process 132 5.4 Brownian Motion as a Martingale 133 5.5 First Passage Time of a Brownian Motion 133 5.6 Maximum of a Brownian Motion 135 5.7 First Passage Time in an Interval 135 5.8 The Brownian Bridge 136 5.9 Geometric Brownian Motion 137 5.10 The Langevin Equation 137 5.11 Summary 141 Problems 141 6 Introduction to Stochastic Calculus 143 6.1 Introduction 143 6.2 The Ito Integral 145 6.3 The Stochastic Differential 146 6.4 The Ito's Formula 147 6.5 Stochastic Differential Equations 147 6.6 Solution of the Geometric Brownian Motion 148 6.7 The Ornstein-Uhlenbeck Process 151 6.7.1 Solution of the Ornstein-Uhlenbeck SDE 152 6.7.2 First Alternative Solution Method 153 6.7.3 Second Alternative Solution Method 154 6.8 Mean-Reverting Ornstein-Uhlenbeck Process 155 6.9 Summary 157 7 Diffusion Processes 158 7.1 Introduction 158 7.2 Mathematical Preliminaries 159 7.3 Diffusion on One-Dimensional Random Walk 160 7.3.1 Alternative Derivation 163 7.4 Examples of Diffusion Processes 164 7.4.1 Brownian Motion 164 7.4.2 Brownian Motion with Drift 167 7.5 Correlated Random Walk and the Telegraph Equation 167 7.6 Diffusion at Finite Speed 170 7.7 Diffusion on Symmetric Two-Dimensional Lattice Random Walk 171 7.8 Diffusion Approximation of the Pearson Random Walk 173 7.9 Summary 174 8 Levy Walk 175 8.1 Introduction 175 8.2 Generalized Central Limit Theorem 175 8.3 Stable Distribution 177 8.4 Self-Similarity 182 8.5 Fractals 183 8.6 Levy Distribution 185 8.7 Levy Process 186 8.8 Infinite Divisibility 186 8.8.1 The Infinite Divisibility of the Poisson Process 187 8.8.2 Infinite Divisibility of the Compound Poisson Process 187 8.8.3 Infinite Divisibility of the Brownian Motion with Drift 188 8.9 Levy Flight 188 8.9.1 First Passage Time of Levy Flights 190 8.9.2 Leapover Properties of Levy Flights 190 8.10 Truncated Levy Flight 191 8.11 Levy Walk 191 8.11.1 Levy Walk as a Coupled CTRW 192 8.11.2 Truncated Levy Walk 195 8.12 Summary 195 9 Fractional Calculus and Its Applications 196 9.1 Introduction 196 9.2 Gamma Function 197 9.3 Mittag-Leffler Functions 198 9.4 Laplace Transform 200 9.5 Fractional Derivatives 202 9.6 Fractional Integrals 203 9.7 Definitions of Fractional Integro-Differentials 203 9.7.1 Riemann-Liouville Fractional Derivative 204 9.7.2 Caputo Fractional Derivative 205 9.7.3 Grunwald-Letnikov Fractional Derivative 206 9.8 Fractional Differential Equations 207 9.8.1 Relaxation Differential Equation of Integer Order 208 9.8.2 Oscillation Differential Equation of Integer Order 208 9.8.3 Relaxation and Oscillation Fractional Differential Equations 209 9.9 Applications of Fractional Calculus 210 9.9.1 Fractional Brownian Motion 210 9.9.2 Multifractional Brownian Motion 213 9.9.3 Fractional Random Walk 213 9.9.4 Fractional (or Anomalous) Diffusion 215 9.9.5 Fractional Gaussian Noise 221 9.9.6 Fractional Poisson Process 222 9.10 Summary 224 10 Percolation Theory 225 10.1 Introduction 225 10.2 Graph Theory Revisited 226 10.2.1 Complete Graphs 226 10.2.2 Random Graphs 226 10.3 Percolation on a Lattice 228 10.3.1 Cluster Formation and Phase Transition 229 10.3.2 Percolation Probability and Critical Exponents 233 10.4 Continuum Percolation 235 10.4.1 The Boolean Model 235 10.4.2 The Random Connection Model 236 10.5 Bootstrap (or k-Core) Percolation 237 10.6 Diffusion Percolation 237 10.6.1 Bootstrap Percolation versus Diffusion Percolation 239 10.7 First-Passage Percolation 239 10.8 Explosive Percolation 240 10.9 Percolation in Complex Networks 242 10.9.1 Average Path Length 243 10.9.2 Clustering Coefficient 243 10.9.3 Degree Distribution 244 10.9.4 Percolation and Network Resilience 244 10.10 Summary 245 References 247 Index 253
Es gelten unsere Allgemeinen Geschäftsbedingungen: www.buecher.de/agb
Impressum
www.buecher.de ist ein Internetauftritt der buecher.de internetstores GmbH
Geschäftsführung: Monica Sawhney | Roland Kölbl | Günter Hilger
Sitz der Gesellschaft: Batheyer Straße 115 - 117, 58099 Hagen
Postanschrift: Bürgermeister-Wegele-Str. 12, 86167 Augsburg
Amtsgericht Hagen HRB 13257
Steuernummer: 321/5800/1497
USt-IdNr: DE450055826
