Modern Discrete Probability: An Essential Toolkit

by Sébastien Roch

Overview

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.

Product Details

ISBN-13:	9781009305112
Publisher:	Cambridge University Press
Publication date:	01/18/2024
Series:	Cambridge Series in Statistical and Probabilistic Mathematics
Pages:	452
Product dimensions:	7.01(w) x 10.00(h) x 0.98(d)

About the Author

Sébastien Roch is Professor of Mathematics at the University of Wisconsin, Madison. He has been awarded an NSF CAREER award, an Alfred P. Sloan Fellowship, and a Simons Fellowship in Mathematics, and is a Fellow of the Institute for Mathematical Statistics.

Table of Contents

Preface; Notation; 1. Introduction; 2. Moments and tails; 3. Martingales and potentials; 4. Coupling; 5. Spectral methods; 6. Branching processes; A. Useful combinatorial formulas; B. Measure-theoretic foundations; Bibliography; Index.

Editorial Reviews

‘An immediate classic, this will be THE go to book for anyone interested in doing research in discrete probability and its applications in myriad fields. A perfect combination of breadth, covering all the major strands of the subject, and depth to prepare starting researchers with the tools to grasp the questions and techniques in the field.’ Shankar Bhamidi, University of North Carolina, Chapel Hill

‘The book has a wonderful collection of topics that are very useful for applications. The book has the same clear presentation and engaging style of the author's seminar talks. It will be a great addition to the libraries of researchers young and old.’ Rick Durrett, Duke University

‘This book is a must-read for anyone interested in discrete probability models. It is rigorous, concise, and well-written, and it covers the necessary tools to study advanced topics such as percolation, random graphs, and Markov random fields and even various applications in machine learning and data science. The author does an excellent job of explaining complex concepts in a clear and concise way, and he provides many helpful examples. I highly recommend this book to anyone who wants to learn more about discrete probability models.’ Csaba Szepesvári, University of Alberta

‘Modern Discrete Probability is essential reading for any graduate student in probability and fills an important gap in the graduate probability curricula. By focusing on the core underlying techniques, it gives a picture of their broad applicability across the field. At the same time readers will learn about percolation, random walks, random graphs and spin systems that make up the building blocks of so much of probability theory.’ Allan Sly, Princeton University

From the Publisher