Modern discrete probability : an essential toolkit / Sébastien Roch, University of Wisconsin-Madison.

Format:

Book

Author/Creator:

Roch, Sébastien, author.

Series:

Cambridge series in statistical and probabilistic mathematics ; 55.

Cambridge series in statistical and probabilistic mathematics ; 55

Language:

English

Subjects (All):

Stochastic processes.

Graph theory.

Physical Description:

1 online resource (xvi, 434 pages) : digital, PDF file(s).

Edition:

First edition.

Place of Publication:

Cambridge, United Kingdom ; New York, NY : Cambridge University Press, 2024.

Summary:

Providing a graduate-level introduction to discrete probability and its applications, this book develops a toolkit of essential techniques for analysing stochastic processes on graphs, other random discrete structures, and algorithms. Topics covered include the first and second moment methods, concentration inequalities, coupling and stochastic domination, martingales and potential theory, spectral methods, and branching processes. Each chapter expands on a fundamental technique, outlining common uses and showing them in action on simple examples and more substantial classical results. The focus is predominantly on non-asymptotic methods and results. All chapters provide a detailed background review section, plus exercises and signposts to the wider literature. Readers are assumed to have undergraduate-level linear algebra and basic real analysis, while prior exposure to graduate-level probability is recommended. This much-needed broad overview of discrete probability could serve as a textbook or as a reference for researchers in mathematics, statistics, data science, computer science and engineering.

Contents:

Cover

Half-title page

Series page

Title page

Imprints page

Dedication

Contents

Preface

Notation

1 Introduction

1.1 Background

1.1.1 Review of Graph Theory

1.1.2 Review of Markov Chain Theory

1.2 Some Discrete Probability Models

Exercises

2 Moments and Tails

2.1 Background

2.1.1 Definitions

2.1.2 Basic Inequalities

2.2 First Moment Method

2.2.1 The Probabilistic Method

2.2.2 Boole's Inequality

2.2.3 Random Permutations: Longest Increasing Subsequence

2.2.4 Percolation: Existence of a Non-trivial Threshold on Z[sup(2)]

2.3 Second Moment Method

2.3.1 Paley-Zygmund Inequality

2.3.2 Random Graphs: Subgraph Containment and Connectivity in the Erdos-Rényi Model

2.3.3 Percolation: Critical Value on Trees and Branching Number

2.4 Chernoff-Cramér Method

2.4.1 Tail Bounds Via the Moment-Generating Function

2.4.2 Sub-Gaussian and Sub-Exponential Random Variables

2.4.3 Probabilistic Analysis of Algorithms: Knapsack Problem

2.4.4 Epsilon-Nets and Chaining

2.4.5 Data Science: Johnson-Lindenstrauss Lemma and Application to Compressed Sensing

2.4.6 Data Science: Classification, Empirical Risk Minimization, and VC Dimension

3 Martingales and Potentials

3.1 Background

3.1.1 Stopping Times

3.1.2 Markov Chains: Exponential Tail of Hitting Times and Some Cover Time Bounds

3.1.3 Martingales

3.1.4 Percolation: Critical Regime on Infinite d-regular Tree

3.2 Concentration for Martingales and Applications

3.2.1 Azuma-Hoeffding Inequality

3.2.2 Method of Bounded Differences

3.2.3 Random Graphs: Exposure Martingale and Application to the Chromatic Number in Erdos-Rényi Model

3.2.4 Random Graphs: Degree Sequence of Preferential Attachment Graphs

3.2.5 Data Science: Stochastic Bandits and the Slicing Method.

3.2.6 Coda: Talagrand's Inequality

3.3 Potential Theory and Electrical Networks

3.3.1 Martingales, the Dirichlet Problem and Lyapounov Functions

3.3.2 Basic Electrical Network Theory

3.3.3 Bounding the Effective Resistance via Variational Principles

3.3.4 Random Walks: Pólya's Theorem, Two Ways

3.3.5 Randomized Algorithms: Wilson's Method for Generating Uniform Spanning Trees

4 Coupling

4.1 Background

4.1.1 Basic Definitions

4.1.2 Random Walks: Harmonic Functions on Lattices and Infinite d-regular Trees

4.1.3 Total Variation Distance and Coupling Inequality

4.1.4 Random Graphs: Degree Sequence in Erdos-Rényi Model

4.2 Stochastic Domination

4.2.1 Definitions

4.2.2 Ising Model: Boundary Conditions

4.2.3 Correlation Inequalities: FKG and Holley's Inequalities

4.2.4 Random Graphs: Janson's Inequality and Application to the Clique Number in the Erdos-Rényi Model

4.2.5 Percolation: RSW Theory and a Proof of Harris' Theorem

4.3 Coupling of Markov Chains and Application to Mixing

4.3.1 Bounding the Mixing Time via Coupling

4.3.2 Random Walks: Mixing on Cycles, Hypercubes, and Trees

4.3.3 Path Coupling

4.3.4 Ising Model: Glauber Dynamics at High Temperature

4.4 Chen-Stein Method

4.4.1 Main Bounds and Examples

4.4.2 Some Motivation and Proof

4.4.3 Random Graphs: Clique Number at the Threshold in theErdos-Rényi Model

5 Spectral Methods

5.1 Background

5.1.1 Eigenvalues and Their Variational Characterization

5.1.2 Elements of Spectral Graph Theory

5.1.3 Perturbation Results

5.1.4 Data Science: Community Recovery

5.2 Spectral Techniques for Reversible Markov Chains

5.2.1 Spectral Gap

5.2.2 Random Walks: A Spectral Look at Cycles and Hypercubes

5.2.3 Markov Chains: Varopoulos-Carne and Diameter-BasedBounds on the Mixing Time.

5.2.4 Randomized Algorithms: Markov Chain Monte Carlo and a Quantitative Ergodic Theorem

5.2.5 Spectral Radius

5.3 Geometric Bounds

5.3.1 Cheeger's Inequality

5.3.2 Random Walks: Trees, Cycles, and Hypercubes Revisited

5.3.3 Random Graphs: Existence of an Expander Family andApplication to Mixing

5.3.4 Ising Model: Glauber Dynamics on Complete Graphs and Expanders

5.3.5 Congestion Ratio

6 Branching Processes

6.1 Background

6.1.1 Basic Definitions

6.1.2 Extinction

6.1.3 Percolation: Galton-Watson Trees

6.1.4 Multitype Branching Processes

6.2 Random-Walk Representation

6.2.1 Exploration Process

6.2.2 Duality Principle

6.2.3 Hitting-Time Theorem

6.2.4 Percolation: Critical Exponents on the Infinite b-ary Tree

6.3 Applications

6.3.1 Probabilistic Analysis of Algorithms: Binary Search Tree

6.3.2 Data Science: The Reconstruction Problem, the Kesten-Stigum Bound and a Phase Transition in Phylogenetics

6.4 Finale: The Phase Transition of the Erdos-Rényi Model

6.4.1 Statement and Proof Sketch

6.4.2 Bounding Cluster Size: Domination by Branching Processes

6.4.3 Concentration of Cluster Size: Second Moment Bounds

6.4.4 Critical Case via Martingales

6.4.5 Encore: Random Walk on the Erdos-Rényi Graph

Appendix A Useful Combinatorial Formulas

Appendix B Measure-Theoretic Foundations

B.1 Probability Spaces

B.2 Random Variables

B.3 Independence

B.4 Expectation

B.5 Fubini's Theorem

B.6 Conditional Expectation

B.7 Filtered Spaces

Bibliography

Index.

Notes:

Title from publisher's bibliographic system (viewed on 15 Dec 2023).

Includes bibliographical references and index.

ISBN:

9781009305136

1009305131

9781009305129

1009305123

OCLC:

1479864286