Brémaud P. Discrete Probability Models and Methods: Probability on Graphs and Trees, Markov Chains and Random Fields, Entropy and Coding

Springer International Publishing, Switzerland, 2017. — 561 p. — (Probability Theory and Stochastic Modeling 78) — ISBN: 9783319434759Discrete probability deals with random elements taking their values in a finite space, or an infinite yet denumerable space: integer-valued random variables, but also random elements with values in a complex space, for instance a graph, a tree, or a combinatorial stucture such as a set partition.
Many problems of a probabilistic nature arising in the applied sciences can be dealt with in the framework of discrete probability. This is especially true in the information, computing and communications sciences. For instance, the study of random graphs has relatively recently been revived with the advent of social networks and community marketing, and percolation graphs have become a popular model of connection in mobile communications. The link between randomness and computation is an area of investigation where discrete probability methods play a priviledged role. When does a logical equation admits a solution, when does there exist a graph with a given property? If the structure of the equation or of the graph is very complex, the probabilistic approach can be efficient. It also features random algorithms that efficiently solve a variety of problems, such as sorting a list of numbers in increasing order or deciding if a given (large) number is prime, and compete with the corresponding available deterministic algorithms. Also of interest to computer science is the Markov chain theory of sampling, exact or approximate, in view of evaluating the size of complex sets for instance. The theory of Markov chains also finds applications in the performance evaluation of communications systems as well as in signal processing.Events and Probability
Random Variables
Bounds and Inequalities
Almost Sure Convergence
The probabilistic Method
Markov Chain Models
Recurrence of Markov Chains
Random Walks on Graphs
Markov Fields on Graphs
Random Graphs
Coding Trees
Shannon’s Capacity Theorem
The Method of Types
Universal Source Coding
Asymptotic Behaviour of Markov Chains
The Coupling Method
Martingale Methods
Discrete Renewal Theory
Monte Carlo
Convergence Rates
Exact Sampling