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