Discrete Probability Models and Methods: Probability on Graphs and Trees, Markov Chains and Random Fields, Entropy and Coding

Description

The emphasis in this book is placed on general models (Markov chains, random fields, random graphs), universal methods (the probabilistic method, the coupling method, the Stein-Chen method, martingale methods, the method of types) and versatile tools (Chernoff's bound, Hoeffding's inequality, Holley's inequality) whose domain of application extends far beyond the present text. Although the examples treated in the book relate to the possible applications, in the communication and computing sciences, in operations research and in physics, this book is in the first instance concerned with theory. The level of the book is that of a beginning graduate course. It is self-contained, the prerequisites consisting merely of basic calculus (series) and basic linear algebra (matrices). The reader is not assumed to be trained in probability since the first chapters give in considerable detail the background necessary to understand the rest of the book. Front Matter....Pages i-xiv Events and Probability....Pages 1-19 Random Variables....Pages 21-63 Bounds and Inequalities....Pages 65-77 Almost Sure Convergence....Pages 79-92 The probabilistic Method....Pages 93-115 Markov Chain Models.3....Pages 117-144 Recurrence of Markov Chains....Pages 145-183 Random Walks on Graphs....Pages 185-214 Markov Fields on Graphs....Pages 215-253 Random Graphs....Pages 255-286 Coding Trees....Pages 287-317 Shannon’s Capacity Theorem....Pages 319-339 The Method of Types....Pages 341-355 Universal Source Coding....Pages 357-371 Asymptotic Behaviour of Markov Chains....Pages 373-396 The Coupling Method....Pages 397-415 Martingale Methods....Pages 417-440 Discrete Renewal Theory....Pages 441-455 Monte Carlo....Pages 457-474 Convergence Rates....Pages 475-508 Exact Sampling....Pages 509-534 Back Matter....Pages 535-559