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.

• Preface xiiiAcknowledgments xv1 Review of Probability Theory 11.1 Introduction 11.2 Random Variables 11.2.1 Distribution Functions 21.2.2 Discrete Random Variables 31.2.3 Continuous Random Variables 31.2.4 Expectations 41.2.5 Moments of Random Variables and the Variance 41.3 Transform Methods 51.3.1 The Characteristic Function 51.3.2 Moment-Generating Property of the Characteristic Function 61.3.3 The s-Transform 61.3.4 Moment-Generating Property of the s-Transform 71.3.5 The z-Transform 71.3.6 Moment-Generating Property of the z-Transform 81.4 Covariance and Correlation Coefficient 91.5 Sums of Independent Random Variables 101.6 Some Probability Distributions 111.6.1 The Bernoulli Distribution 111.6.2 The Binomial Distribution 121.6.3 The Geometric Distribution 121.6.4 The Poisson Distribution 131.6.5 The Exponential Distribution 131.6.6 Normal Distribution 141.7 Limit Theorems 161.7.1 Markov Inequality 161.7.2 Chebyshev Inequality 171.7.3 Laws of Large Numbers 171.7.4 The Central Limit Theorem 18Problems 192 Overview of Stochastic Processes 212.1 Introduction 212.2 Classification of Stochastic Processes 222.3 Mean and Autocorrelation Function 222.4 Stationary Processes 232.4.1 Strict-Sense Stationary Processes 232.4.2 Wide-Sense Stationary Processes 242.5 Power Spectral Density 242.6 Counting Processes 252.7 Independent Increment Processes 252.8 Stationary Increment Process 252.9 Poisson Processes 262.9.1 Compound Poisson Process 282.10 Markov Processes 292.10.1 Discrete-Time Markov Chains 302.10.2 State Transition Probability Matrix 312.10.3 The k-Step State Transition Probability 312.10.4 State Transition Diagrams 322.10.5 Classification of States 332.10.6 Limiting-State Probabilities 342.10.7 Doubly Stochastic Matrix 352.10.8 Continuous-Time Markov Chains 352.10.9 Birth and Death Processes 362.11 Gaussian Processes 382.12 Martingales 382.12.1 Stopping Times 40Problems 413 One-Dimensional Random Walk 443.1 Introduction 443.2 Occupancy Probability 463.3 Random Walk as a Markov Chain 493.4 Symmetric Random Walk as a Martingale 493.5 Random Walk with Barriers 503.6 Mean-Square Displacement 503.7 Gambler’s Ruin 523.7.1 Ruin Probability 523.7.2 Alternative Derivation of Ruin Probability 543.7.3 Duration of a Game 553.8 Random Walk with Stay 563.9 First Return to the Origin 573.10 First Passage Times for Symmetric Random Walk 593.10.1 First Passage Time via the Generating Function 593.10.2 First Passage Time via the Reflection Principle 613.10.3 Hitting Time and the Reflection Principle 643.11 The Ballot Problem and the Reflection Principle 653.11.1 The Conditional Probability Method 663.12 Returns to the Origin and the Arc-Sine Law 673.13 Maximum of a Random Walk 723.14 Two Symmetric Random Walkers 733.15 Random Walk on a Graph 733.15.1 Proximity Measures 753.15.2 Directed Graphs 753.15.3 Random Walk on an Undirected Graph 763.15.4 Random Walk on a Weighted Graph 803.16 Random Walks and Electric Networks 803.16.1 Harmonic Functions 823.16.2 Effective Resistance and Escape Probability 823.17 Correlated Random Walk 853.18 Continuous-Time Random Walk 903.18.1 The Master Equation 923.19 Reinforced Random Walk 943.19.1 Polya’s Urn Model 943.19.2 ERRW and Polya’s Urn 963.19.3 ERRW Revisited 973.20 Miscellaneous Random Walk Models 983.20.1 Geometric Random Walk 983.20.2 Gaussian Random Walk 993.20.3 Random Walk with Memory 993.21 Summary 100Problems 1004 Two-Dimensional Random Walk 1034.1 Introduction 1034.2 The Pearson Random Walk 1054.2.1 Mean-Square Displacement 1054.2.2 Probability Distribution 1074.3 The Symmetric 2D Random Walk 1104.3.1 Stirling’s Approximation of Symmetric Walk 1124.3.2 Probability of Eventual Return for Symmetric Walk 1134.3.3 Mean-Square Displacement 1144.3.4 Two Independent Symmetric 2D Random Walkers 1144.4 The Alternating Random Walk 1154.4.1 Stirling’s Approximation of Alternating Walk 1174.4.2 Probability of Eventual Return for Alternating Walk 1174.5 Self-Avoiding Random Walk 1174.6 Nonreversing Random Walk 1214.7 Extensions of the NRRW 1264.7.1 The Noncontinuing Random Walk 1264.7.2 The Nonreversing and Noncontinuing Random Walk 1274.8 Summary 1285 Brownian Motion 1295.1 Introduction 1295.2 Brownian Motion with Drift 1325.3 Brownian Motion as a Markov Process 1325.4 Brownian Motion as a Martingale 1335.5 First Passage Time of a Brownian Motion 1335.6 Maximum of a Brownian Motion 1355.7 First Passage Time in an Interval 1355.8 The Brownian Bridge 1365.9 Geometric Brownian Motion 1375.10 The Langevin Equation 1375.11 Summary 141Problems 1416 Introduction to Stochastic Calculus 1436.1 Introduction 1436.2 The Ito Integral 1456.3 The Stochastic Differential 1466.4 The Ito’s Formula 1476.5 Stochastic Differential Equations 1476.6 Solution of the Geometric Brownian Motion 1486.7 The Ornstein–Uhlenbeck Process 1516.7.1 Solution of the Ornstein–Uhlenbeck SDE 1526.7.2 First Alternative Solution Method 1536.7.3 Second Alternative Solution Method 1546.8 Mean-Reverting Ornstein–Uhlenbeck Process 1556.9 Summary 1577 Diffusion Processes 1587.1 Introduction 1587.2 Mathematical Preliminaries 1597.3 Diffusion on One-Dimensional Random Walk 1607.3.1 Alternative Derivation 1637.4 Examples of Diffusion Processes 1647.4.1 Brownian Motion 1647.4.2 Brownian Motion with Drift 1677.5 Correlated Random Walk and the Telegraph Equation 1677.6 Diffusion at Finite Speed 1707.7 Diffusion on Symmetric Two-Dimensional Lattice Random Walk 1717.8 Diffusion Approximation of the Pearson Random Walk 1737.9 Summary 1748 Levy Walk 1758.1 Introduction 1758.2 Generalized Central Limit Theorem 1758.3 Stable Distribution 1778.4 Self-Similarity 1828.5 Fractals 1838.6 Levy Distribution 1858.7 Levy Process 1868.8 Infinite Divisibility 1868.8.1 The Infinite Divisibility of the Poisson Process 1878.8.2 Infinite Divisibility of the Compound Poisson Process 1878.8.3 Infinite Divisibility of the Brownian Motion with Drift 1888.9 Levy Flight 1888.9.1 First Passage Time of Levy Flights 1908.9.2 Leapover Properties of Levy Flights 1908.10 Truncated Levy Flight 1918.11 Levy Walk 1918.11.1 Levy Walk as a Coupled CTRW 1928.11.2 Truncated Levy Walk 1958.12 Summary 1959 Fractional Calculus and Its Applications 1969.1 Introduction 1969.2 Gamma Function 1979.3 Mittag–Leffler Functions 1989.4 Laplace Transform 2009.5 Fractional Derivatives 2029.6 Fractional Integrals 2039.7 Definitions of Fractional Integro-Differentials 2039.7.1 Riemann–Liouville Fractional Derivative 2049.7.2 Caputo Fractional Derivative 2059.7.3 Grunwald–Letnikov Fractional Derivative 2069.8 Fractional Differential Equations 2079.8.1 Relaxation Differential Equation of Integer Order 2089.8.2 Oscillation Differential Equation of Integer Order 2089.8.3 Relaxation and Oscillation Fractional Differential Equations 2099.9 Applications of Fractional Calculus 2109.9.1 Fractional Brownian Motion 2109.9.2 Multifractional Brownian Motion 2139.9.3 Fractional Random Walk 2139.9.4 Fractional (or Anomalous) Diffusion 2159.9.5 Fractional Gaussian Noise 2219.9.6 Fractional Poisson Process 2229.10 Summary 22410 Percolation Theory 22510.1 Introduction 22510.2 Graph Theory Revisited 22610.2.1 Complete Graphs 22610.2.2 Random Graphs 22610.3 Percolation on a Lattice 22810.3.1 Cluster Formation and Phase Transition 22910.3.2 Percolation Probability and Critical Exponents 23310.4 Continuum Percolation 23510.4.1 The Boolean Model 23510.4.2 The Random Connection Model 23610.5 Bootstrap (or k-Core) Percolation 23710.6 Diffusion Percolation 23710.6.1 Bootstrap Percolation versus Diffusion Percolation 23910.7 First-Passage Percolation 23910.8 Explosive Percolation 24010.9 Percolation in Complex Networks 24210.9.1 Average Path Length 24310.9.2 Clustering Coefficient 24310.9.3 Degree Distribution 24410.9.4 Percolation and Network Resilience 24410.10 Summary 245References 247Index 253

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.

• Preface xiiiAcknowledgments xv1 Review of Probability Theory 11.1 Introduction 11.2 Random Variables 11.2.1 Distribution Functions 21.2.2 Discrete Random Variables 31.2.3 Continuous Random Variables 31.2.4 Expectations 41.2.5 Moments of Random Variables and the Variance 41.3 Transform Methods 51.3.1 The Characteristic Function 51.3.2 Moment-Generating Property of the Characteristic Function 61.3.3 The s-Transform 61.3.4 Moment-Generating Property of the s-Transform 71.3.5 The z-Transform 71.3.6 Moment-Generating Property of the z-Transform 81.4 Covariance and Correlation Coefficient 91.5 Sums of Independent Random Variables 101.6 Some Probability Distributions 111.6.1 The Bernoulli Distribution 111.6.2 The Binomial Distribution 121.6.3 The Geometric Distribution 121.6.4 The Poisson Distribution 131.6.5 The Exponential Distribution 131.6.6 Normal Distribution 141.7 Limit Theorems 161.7.1 Markov Inequality 161.7.2 Chebyshev Inequality 171.7.3 Laws of Large Numbers 171.7.4 The Central Limit Theorem 18Problems 192 Overview of Stochastic Processes 212.1 Introduction 212.2 Classification of Stochastic Processes 222.3 Mean and Autocorrelation Function 222.4 Stationary Processes 232.4.1 Strict-Sense Stationary Processes 232.4.2 Wide-Sense Stationary Processes 242.5 Power Spectral Density 242.6 Counting Processes 252.7 Independent Increment Processes 252.8 Stationary Increment Process 252.9 Poisson Processes 262.9.1 Compound Poisson Process 282.10 Markov Processes 292.10.1 Discrete-Time Markov Chains 302.10.2 State Transition Probability Matrix 312.10.3 The k-Step State Transition Probability 312.10.4 State Transition Diagrams 322.10.5 Classification of States 332.10.6 Limiting-State Probabilities 342.10.7 Doubly Stochastic Matrix 352.10.8 Continuous-Time Markov Chains 352.10.9 Birth and Death Processes 362.11 Gaussian Processes 382.12 Martingales 382.12.1 Stopping Times 40Problems 413 One-Dimensional Random Walk 443.1 Introduction 443.2 Occupancy Probability 463.3 Random Walk as a Markov Chain 493.4 Symmetric Random Walk as a Martingale 493.5 Random Walk with Barriers 503.6 Mean-Square Displacement 503.7 Gambler’s Ruin 523.7.1 Ruin Probability 523.7.2 Alternative Derivation of Ruin Probability 543.7.3 Duration of a Game 553.8 Random Walk with Stay 563.9 First Return to the Origin 573.10 First Passage Times for Symmetric Random Walk 593.10.1 First Passage Time via the Generating Function 593.10.2 First Passage Time via the Reflection Principle 613.10.3 Hitting Time and the Reflection Principle 643.11 The Ballot Problem and the Reflection Principle 653.11.1 The Conditional Probability Method 663.12 Returns to the Origin and the Arc-Sine Law 673.13 Maximum of a Random Walk 723.14 Two Symmetric Random Walkers 733.15 Random Walk on a Graph 733.15.1 Proximity Measures 753.15.2 Directed Graphs 753.15.3 Random Walk on an Undirected Graph 763.15.4 Random Walk on a Weighted Graph 803.16 Random Walks and Electric Networks 803.16.1 Harmonic Functions 823.16.2 Effective Resistance and Escape Probability 823.17 Correlated Random Walk 853.18 Continuous-Time Random Walk 903.18.1 The Master Equation 923.19 Reinforced Random Walk 943.19.1 Polya’s Urn Model 943.19.2 ERRW and Polya’s Urn 963.19.3 ERRW Revisited 973.20 Miscellaneous Random Walk Models 983.20.1 Geometric Random Walk 983.20.2 Gaussian Random Walk 993.20.3 Random Walk with Memory 993.21 Summary 100Problems 1004 Two-Dimensional Random Walk 1034.1 Introduction 1034.2 The Pearson Random Walk 1054.2.1 Mean-Square Displacement 1054.2.2 Probability Distribution 1074.3 The Symmetric 2D Random Walk 1104.3.1 Stirling’s Approximation of Symmetric Walk 1124.3.2 Probability of Eventual Return for Symmetric Walk 1134.3.3 Mean-Square Displacement 1144.3.4 Two Independent Symmetric 2D Random Walkers 1144.4 The Alternating Random Walk 1154.4.1 Stirling’s Approximation of Alternating Walk 1174.4.2 Probability of Eventual Return for Alternating Walk 1174.5 Self-Avoiding Random Walk 1174.6 Nonreversing Random Walk 1214.7 Extensions of the NRRW 1264.7.1 The Noncontinuing Random Walk 1264.7.2 The Nonreversing and Noncontinuing Random Walk 1274.8 Summary 1285 Brownian Motion 1295.1 Introduction 1295.2 Brownian Motion with Drift 1325.3 Brownian Motion as a Markov Process 1325.4 Brownian Motion as a Martingale 1335.5 First Passage Time of a Brownian Motion 1335.6 Maximum of a Brownian Motion 1355.7 First Passage Time in an Interval 1355.8 The Brownian Bridge 1365.9 Geometric Brownian Motion 1375.10 The Langevin Equation 1375.11 Summary 141Problems 1416 Introduction to Stochastic Calculus 1436.1 Introduction 1436.2 The Ito Integral 1456.3 The Stochastic Differential 1466.4 The Ito’s Formula 1476.5 Stochastic Differential Equations 1476.6 Solution of the Geometric Brownian Motion 1486.7 The Ornstein–Uhlenbeck Process 1516.7.1 Solution of the Ornstein–Uhlenbeck SDE 1526.7.2 First Alternative Solution Method 1536.7.3 Second Alternative Solution Method 1546.8 Mean-Reverting Ornstein–Uhlenbeck Process 1556.9 Summary 1577 Diffusion Processes 1587.1 Introduction 1587.2 Mathematical Preliminaries 1597.3 Diffusion on One-Dimensional Random Walk 1607.3.1 Alternative Derivation 1637.4 Examples of Diffusion Processes 1647.4.1 Brownian Motion 1647.4.2 Brownian Motion with Drift 1677.5 Correlated Random Walk and the Telegraph Equation 1677.6 Diffusion at Finite Speed 1707.7 Diffusion on Symmetric Two-Dimensional Lattice Random Walk 1717.8 Diffusion Approximation of the Pearson Random Walk 1737.9 Summary 1748 Levy Walk 1758.1 Introduction 1758.2 Generalized Central Limit Theorem 1758.3 Stable Distribution 1778.4 Self-Similarity 1828.5 Fractals 1838.6 Levy Distribution 1858.7 Levy Process 1868.8 Infinite Divisibility 1868.8.1 The Infinite Divisibility of the Poisson Process 1878.8.2 Infinite Divisibility of the Compound Poisson Process 1878.8.3 Infinite Divisibility of the Brownian Motion with Drift 1888.9 Levy Flight 1888.9.1 First Passage Time of Levy Flights 1908.9.2 Leapover Properties of Levy Flights 1908.10 Truncated Levy Flight 1918.11 Levy Walk 1918.11.1 Levy Walk as a Coupled CTRW 1928.11.2 Truncated Levy Walk 1958.12 Summary 1959 Fractional Calculus and Its Applications 1969.1 Introduction 1969.2 Gamma Function 1979.3 Mittag–Leffler Functions 1989.4 Laplace Transform 2009.5 Fractional Derivatives 2029.6 Fractional Integrals 2039.7 Definitions of Fractional Integro-Differentials 2039.7.1 Riemann–Liouville Fractional Derivative 2049.7.2 Caputo Fractional Derivative 2059.7.3 Grunwald–Letnikov Fractional Derivative 2069.8 Fractional Differential Equations 2079.8.1 Relaxation Differential Equation of Integer Order 2089.8.2 Oscillation Differential Equation of Integer Order 2089.8.3 Relaxation and Oscillation Fractional Differential Equations 2099.9 Applications of Fractional Calculus 2109.9.1 Fractional Brownian Motion 2109.9.2 Multifractional Brownian Motion 2139.9.3 Fractional Random Walk 2139.9.4 Fractional (or Anomalous) Diffusion 2159.9.5 Fractional Gaussian Noise 2219.9.6 Fractional Poisson Process 2229.10 Summary 22410 Percolation Theory 22510.1 Introduction 22510.2 Graph Theory Revisited 22610.2.1 Complete Graphs 22610.2.2 Random Graphs 22610.3 Percolation on a Lattice 22810.3.1 Cluster Formation and Phase Transition 22910.3.2 Percolation Probability and Critical Exponents 23310.4 Continuum Percolation 23510.4.1 The Boolean Model 23510.4.2 The Random Connection Model 23610.5 Bootstrap (or k-Core) Percolation 23710.6 Diffusion Percolation 23710.6.1 Bootstrap Percolation versus Diffusion Percolation 23910.7 First-Passage Percolation 23910.8 Explosive Percolation 24010.9 Percolation in Complex Networks 24210.9.1 Average Path Length 24310.9.2 Clustering Coefficient 24310.9.3 Degree Distribution 24410.9.4 Percolation and Network Resilience 24410.10 Summary 245References 247Index 253