Probability Theory and Stochastic Processes

Contents
Introduction
PART ONE: Probability theory
PART TWO: Standard stochastic processes
PART THREE: Advanced topics
Practical issues
Acknowledgements
I: PROBABILITY THEORY
Chapter 1 Warming Up
1.1 Sample Space, Events and Probability
1.1.1 Events
The Language of Probabilists
The σ-field of Events
1.1.2 Probability of Events
Basic Formulas
Negligible Sets
1.2 Independence and Conditioning
1.2.1 Independent Events
1.2.2 Bayes’ Calculus
1.2.3 Conditional Independence
1.3 Discrete Random Variables
1.3.1 Probability Distributions and Expectation
Expectation for Discrete Random Variables
Basic Properties of Expectation
Mean and Variance
Independent Variables
The Product Formula for Expectations
1.3.2 Famous Discrete Probability Distributions
The Binomial Distribution
The Geometric Distribution
The Poisson Distribution
The Multinomial Distribution
Random Graphs
1.3.3 Conditional Expectation
1.4 The Branching Process
1.4.1 Generating Functions
Moments from the Generating Function
Counting with Generating Functions
Random Sums
1.4.2 Probability of Extinction
1.5 Borel’s Strong Law of Large Numbers
1.5.1 The Borel–Cantelli Lemma
1.5.2 Markov’s Inequality
1.5.3 Proof of Borel’s Strong Law
Complementary reading
1.6 Exercises
Chapter 2 Integration
2.1 Measurability and Measure
2.1.1 Measurable Functions
Stability Properties of Measurable Functions
Dynkin’s Systems
2.1.2 Measure
Negligible Sets
Equality of Measures
Existence of Measures
2.2 The Lebesgue Integral
2.2.1 Construction of the Integral
The Stieltjes–Lebesgue Integral
2.2.2 Elementary Properties of the Integral
More Elementary Properties
2.2.3 Beppo Levi, Fatou and Lebesgue
Differentiation under the integral sign
2.3 The Other Big Theorems
2.3.1 The Image Measure Theorem
2.3.2 The Fubini–Tonelli Theorem
Integration by Parts Formula
2.3.3 The Riesz–Fischer Theorem
Holder’s Inequality
Minkowski’s Inequality
The Riesz–Fischer Theorem
2.3.4 The Radon–Nikod´ym Theorem
The Product of a Measure by a Function
Lebesgue’s decomposition
The Radon–Nikod´ym Derivative
Complementary reading
2.4 Exercises
Chapter 3 Probability and Expectation
3.1 From Integral to Expectation
3.1.1 Translation
Mean and Variance
Markov’s Inequality
Jensen’s Inequality
3.1.2 Probability Distributions
Famous Continuous Random Variables
Change of Variables
Covariance Matrices
Correlation Coefficient
3.1.3 Independence and the Product Formula
Order Statistics
Sampling from a Distribution
3.1.4 Characteristic Functions
Ladder Random Variables
Random Sums and Wald’s Identity
3.1.5 Laplace Transforms
3.2 Gaussian vectors
3.2.1 Two Equivalent Definitions
3.2.2 Independence and Non-correlation
3.2.3 The pdf of a Non-degenerate Gaussian Vector
3.3 Conditional Expectation
3.3.1 The Intermediate Theory
Bayesian Tests of Hypotheses
3.3.2 The General Theory
Connection with the Intermediate Theory
Properties of the Conditional Expectation
3.3.3 The Doubly Stochastic Framework
3.3.4 The L2-theory of Conditional Expectation
Complementary reading
3.4 Exercises
Chapter 4 Convergences
4.1 Almost-sure Convergence
4.1.1 A Sufficient Condition and a Criterion
A Criterion
4.1.2 Beppo Levi, Fatou and Lebesgue
4.1.3 The Strong Law of Large Numbers
Large Deviations
4.2 Two Other Types of Convergence
4.2.1 Convergence in Probability
4.2.2 Convergence in Lp
4.2.3 Uniform Integrability
4.3 Zero-one Laws
4.3.1 Kolmogorov’s Zero-one Law
4.3.2 The Hewitt–Savage Zero-one Law
4.4 Convergence in Distribution and in Variation
4.4.1 The Role of Characteristic Functions
Paul Levy’s Characterization
Bochner’s Theorem
4.4.2 The Central Limit Theorem
Statistical Applications
4.4.3 Convergence in Variation
The Variation Distance
The Coupling Inequality
A More General Definition
A Bayesian Interpretation
Convergence in Variation
4.4.4 Proof of Paul Levy’s Criterion
Radon Linear Forms
Vague Convergence
Helly’s Theorem
Fourier Transforms of Finite Measures
The Proof of Paul Levy’s criterion
4.5 The Hierarchy of Convergences
4.5.1 Almost-sure vs in Probability
4.5.2 The Rank of Convergence in Distribution
A Stability Property of Gaussian Vectors
Complementary reading
4.6 Exercises
II: STANDARD STOCHASTIC PROCESSES
Chapter 5 Generalities on Random Processes
5.1 The Distribution of a Random Process
5.1.1 Kolmogorov’s Theorem on Distributions
Random Processes as Collections of Random Variables
Finite-dimensional Distributions
Independence
Transfer to Canonical Spaces
Stationarity
5.1.2 Second-order Stochastic Processes
Wide-sense Stationarity
5.1.3 Gaussian Processes
Gaussian Subspaces
5.2 Random Processes as Random Functions
5.2.1 Versions and Modifications
5.2.2 Kolmogorov’s Continuity Condition
5.3 Measurability Issues
5.3.1 Measurable Processes and their Integrals
5.3.2 Histories and Stopping Times
Progressive Measurability
Stopping Times
Complementary reading
5.4 Exercises
Chapter 6 Markov Chains, Discrete Time
6.1 The Markov Property
6.1.1 The Markov Property on the Integers
First-step Analysis
6.1.2 The Markov Property on a Graph
Local characteristics
Gibbs Distributions
The Hammersley–Clifford Theorem
6.2 The Transition Matrix
6.2.1 Topological Notions
Communication Classes
Period
6.2.2 Stationary Distributions and Reversibility
Reversibility
6.2.3 The Strong Markov Property
Regenerative Cycles
6.3 Recurrence and Transience
6.3.1 Classification of States
The Potential Matrix Criterion of Recurrence
6.3.2 The Stationary Distribution Criterion
Birth-and-death Markov Chains
6.3.3 Foster’s Theorem
6.4 Long-run Behavior
6.4.1 The Markov Chain Ergodic Theorem
6.4.2 Convergence in Variation to Steady State
6.4.3 Null Recurrent Case: Orey’s Theorem
6.4.4 Absorption
Before Absorption
Time to Absorption
Final Destination
6.5 Monte Carlo Markov Chain Simulation
6.5.1 Basic Principle and Algorithms
6.5.2 Exact Sampling
The Propp–Wilson Algorithm
Sandwiching
Complementary reading
6.6 Exercises
Chapter 7 Markov Chains, Continuous Time
7.1 Homogeneous Poisson Processes on the Line
7.1.1 The Counting Process and the Interval Sequence
The Counting Process
Superposition of independent HPPS
Strong Markov Property
The Interval Sequence
7.1.2 Stochastic Calculus of HPPS
A Smoothing Formula for HPPS
Watanabe’s Characterization
The Strong Markov Property via Watanabe’s theorem
7.2 The Transition Semigroup
7.2.1 The Infinitesimal Generator
The Uniform HMC
7.2.2 The Local Characteristics
7.2.3 HMCS from HPPS
Aggregation of States
7.3 Regenerative Structure
7.3.1 The Strong Markov Property
7.3.2 Imbedded Chain
7.3.3 Conditions for Regularity
7.4 Long-run Behavior
7.4.1 Recurrence
Invariant Measures of Recurrent Chains
The Stationary Distribution Criterion of Ergodicity
Reversibility
7.4.2 Convergence to Equilibrium
Empirical Averages
Complementary reading
7.5 Exercises
Chapter 8 Spatial Poisson Processes
8.1 Generalities on Point Processes
8.1.1 Point Processes as Random Measures
Points
Marked Point Processes
8.1.2 Point Process Integrals and the Intensity Measure
Campbell’s Formula
Cluster Point Processes
8.1.3 The Distribution of a Point Process
Finite-dimensional Distributions
The Laplace Functional
The Avoidance Function
8.2 Unmarked Spatial Poisson Processes
8.2.1 Construction
Doubly Stochastic Poisson Processes
8.2.2 Poisson Process Integrals
The Covariance Formula
The Exponential Formula
8.3 Marked Spatial Poisson Processes
8.3.1 As Unmarked Poisson Processes
8.3.2 Operations on Poisson Processes
Thinning and Coloring
Transportation
Poisson Shot Noise
8.3.3 Change of Probability Measure
The Case of Finite Intensity Measures
The Mixed Poisson Case
8.4 The Boolean Model
Isolated Points
Complementary reading
8.5 Exercises
Chapter 9 Queueing Processes
9.1 Discrete-time Markovian Queues
9.1.1 The Basic Example
9.1.2 Multiple Access Communication
The Instability of ALOHA
Backlog Dependent Policies
9.1.3 The Stack Algorithm
9.2 Continuous-time Markovian Queues
9.2.1 Isolated Markovian Queues
Congestion as a Birth-and-Death Process
9.2.2 Markovian Networks
Burke’s Output Theorem
Jackson Networks
Gordon–Newell Networks
9.3 Non-exponential Models
9.3.1 M/GI/∞
9.3.2 M/GI/1/∞/FIFO
9.3.3 GI/M/1/∞/FIFO
Complementary reading
9.4 Exercises
Chapter 10 Renewal and Regenerative Processes
10.1 Renewal Point processes
10.1.1 The Renewal Measure
10.1.2 The Renewal Equation
Solution of the Renewal Equation
10.1.3 Stationary Renewal Processes
10.2 The Renewal Theorem
10.2.1 The Key Renewal Theorem
Direct Riemann Integrability
The Key Renewal Theorem
Renewal Reward Processes
10.2.2 The Coupling Proof of Blackwell’s Theorem
10.2.3 Defective and Excessive Renewal Equations
10.3 Regenerative Processes
10.3.1 Examples
10.3.2 The Limit Distribution
10.4 Semi-Markov Processes
Improper Multivariate Renewal Equations
Complementary reading
10.5 Exercises
Chapter 11 Brownian Motion
11.1 Brownian Motion or Wiener Process
11.1.1 As a Rescaled Random Walk
Behavior at Infinity
11.1.2 Simple Operations on Brownian motion
The Brownian Bridge
11.1.3 Gauss–Markov Processes
11.2 Properties of Brownian Motion
11.2.1 The Strong Markov Property
The Reflection Principle
11.2.2 Continuity
11.2.3 Non-differentiability
11.2.4 Quadratic Variation
11.3 The Wiener–Doob Integral
11.3.1 Construction
Series Expansion of Wiener integrals
A Characterization of the Wiener Integral
11.3.2 Langevin’s Equation
11.3.3 The Cameron–Martin Formula
11.4 Fractal Brownian Motion
Complementary reading
11.5 Exercises
Chapter 12 Wide-sense Stationary Stochastic Processes
12.1 The Power Spectral Measure
12.1.1 Covariance Functions and Characteristic Functions
Two Particular Cases
The General Case
12.1.2 Filtering of wss Stochastic Processes
12.1.3 White Noise
A First Approach
White Noise via the Doob–Wiener Integral
The Approximate Derivative Approach
12.2 Fourier Analysis of the Trajectories
12.2.1 The Cramer–Khintchin Decomposition
The Shannon–Nyquist Sampling Theorem
12.2.2 A Plancherel–Parseval Formula
12.2.3 Linear Operations
Linear Transformations of Gaussian Processes
12.3 Multivariate wss Stochastic Processes
12.3.1 The Power Spectral Matrix
12.3.2 Band-pass Stochastic Processes
Complementary reading
12.4 Exercises
III: ADVANCED TOPICS
Chapter 13 Martingales
13.1 Martingale Inequalities
13.1.1 The Martingale Property
Convex Functions of Martingales
Martingale Transforms and Stopped Martingales
13.1.2 Kolmogorov’s Inequality
13.1.3 Doob’s Inequality
13.1.4 Hoeffding’s Inequality
A General Framework of Application
Exposure Martingales in Erd¨os–R´enyi Graphs
13.2 Martingales and Stopping Times
13.2.1 Doob’s Optional Sampling Theorem
13.2.2 Wald’s Formulas
Wald’s Mean Formula
Wald’s Exponential Formula
13.2.3 The Maximum Principle
13.3 Convergence of Martingales
13.3.1 The Fundamental Convergence Theorem
Kakutani’s Theorem
13.3.2 Backwards (or Reverse) Martingales
Local Absolute Continuity
Harmonic Functions and Markov Chains
13.3.3 The Robbins–Sigmund Theorem
13.3.4 Square-integrable Martingales
Doob’s decomposition
The Martingale Law of Large Numbers
The Robbins–Monro algorithm
13.4 Continuous-time Martingales
13.4.1 From Discrete Time to Continuous Time
Predictable Quadratic Variation Processes
13.4.2 The Banach Space MP
13.4.3 Time Scaling
Complementary reading
13.5 Exercises
Chapter 14 A Glimpse at Ito’s Stochastic Calculus
14.1 The Ito Integral
14.1.1 Construction
14.1.2 Properties of the Ito Integral Process
14.1.3 Ito’s Integrals Defined as Limits in Probability
14.2 Ito’s Differential Formula
14.2.1 Elementary Form
Functions of Brownian Motion
Levy’s Characterization of Brownian Motion
14.2.2 Some Extensions
A Finite Number of Discontinuities
The Vectorial Differentiation Rule
14.3 Selected Applications
14.3.1 Square-integrable Brownian Functionals
14.3.2 Girsanov’s Theorem
The Strong Markov Property of Brownian Motion
14.3.3 Stochastic Differential Equations
Strong and Weak Solutions
14.3.4 The Dirichlet Problem
Complementary reading
14.4 Exercises
Chapter 15 Point Processes with a Stochastic Intensity
15.1 Stochastic Intensity
15.1.1 The Martingale Definition
15.1.2 Stochastic Intensity Kernels
The Case of Marked Point Processes
Stochastic Integrals and Martingales
15.1.3 Martingales as Stochastic Integrals
15.1.4 The Regenerative Form of the Stochastic Intensity
15.2 Transformations of the Stochastic Intensity
15.2.1 Changing the History
15.2.2 Absolutely Continuous Change of Probability
The Reference Probability Method
15.2.3 Changing the Time Scale
Cryptology
15.3 Point Processes under a Poisson process
15.3.1 An Extension of Watanabe’s Theorem
15.3.2 Grigelionis’ Embedding Theorem
Variants of the Embedding Theorems
Complementary reading
15.4 Exercises
Chapter 16 Ergodic Processes
16.1 Ergodicity and Mixing
16.1.1 Invariant Events and Ergodicity
16.1.2 Mixing
The Stochastic Process Point of View
16.1.3 The Convex Set of Ergodic Probabilities
16.2 A Detour into Queueing Theory
16.2.1 Lindley’s Sequence
16.2.2 Loynes’ Equation
16.3 Birkhoff’s Theorem
16.3.1 The Ergodic Case
16.3.2 The Non-ergodic Case
16.3.3 The Continuous-time Ergodic Theorem
Complementary reading
16.4 Exercises
Chapter 17 Palm Probability
17.1 Palm Distribution and Palm Probability
17.1.1 Palm Distribution
17.1.2 Stationary Frameworks
Measurable Flows
Compatibility
Stationary Frameworks
17.1.3 Palm Probability and the Campbell–Mecke Formula
Thinning and Conditioning
17.2 Basic Properties and Formulas
17.2.1 Event-time Stationarity
17.2.2 Inversion Formulas
Backward and Forward Recurrence Times
17.2.3 The Exchange Formula
17.2.4 From Palm to Stationary
The G/G/1/∞ Queue in Continuous Time
17.3 Two Interpretations of Palm Probability
17.3.1 The Local Interpretation
17.3.2 The Ergodic Interpretation
17.4 General Principles of Queueing Theory
17.4.1 The PSATA Property
17.4.2 Queue Length at Departures or Arrivals
17.4.3 Little’s Formula
Complementary reading
17.5 Exercises
Appendix A Number Theory and Linear Algebra
A.1 The Greatest Common Divisor
A.2 Eigenvalues and Eigenvectors
A.3 The Perron–Fr¨obenius Theorem
Appendix B Analysis
B.1 Infinite Products
B.2 Abel’s Theorem
B.3 Tykhonov’s Theorem
B.4 Cesaro, Toeplitz and Kronecker’s Lemmas
Cesaro’s Lemma
Toeplitz’s Lemma
Kronecker’s Lemma
B.5 Subadditive Functions
B.6 Gronwall’s Lemma
B.7 The Abstract Definition of Continuity
B.8 Change of Time
Appendix C Hilbert Spaces
C.1 Basic Definitions
C.2 Schwarz’s Inequality
C.3 Isometric Extension
C.4 Orthogonal Projection
C.5 Riesz’s Representation Theorem
C.6 Orthonormal expansions
Bibliography
Index