Discrete stochastic processes and applications (Q1704456)

This textbook gives a self-contained and excellent introductory material to the beautiful theory of stochastic processes and their applications. It includes discrete and continuous-time Markov chains and elements of information theory, with applications to population dynamics, search engine design and coding theory. The text is also complemented by a number of exercises with solutions, which makes the material an ideal basis for an introductory teaching material to the above-mentioned topics. The book consists of eight chapters, and an appendix discussing some useful linear algebra, calculus and probability theory facts and results (with proofs) used throughout the text. In the first chapter, the author introduces the concept of a discrete-time Markov chain and discusses its certain structural properties. The emphasis is put on the ergodic properties and the convergence theorem for ergodic Markov chains. In the first chapter this is treated by employing purely probabilistic techniques (coupling method), while in Chapter 2 (in the case of Markov chains on a finite state space) it relies on linear algebra methods (Perron-Frobenius theorem). The chapter also includes an application of the ergodic theory of Markov chains to the page-rank algorithm used in search engines. In Chapter 3, the author gradually moves to continuous-time Markov chains by first introducing and analyzing a Poisson process. The fourth chapter is devoted to general continuous-time Markov chains and their structural properties, by again putting emphasize on the ergodic properties and the convergence theorem. Chapter 5 brings a number of examples of discrete and continuous-time Markov chains, including random walks and birth-death processes. Chapter six opens the second part of the book, dedicated to the information theory, first discussing some elements of convex analysis. In the seventh chapter, basic quantities of the information theory are presented. It begins by introducing the concept and basic properties of entropy, it continues with the notion and certain facts about \(\Phi\)-divergences and in particular the Kullback-Leibler divergence, and it concludes with a third and purely analytical proof of the convergence theorem for ergodic Markov chains on finite state spaces. The book concludes with the eighth chapter, where the author discusses the connection of the information theory and entropy with binary coding. In conclusion, this textbook is a very nice introductory material to the subjects of discrete and continuous-time Markov chains, and information theory with applications to binary coding. It is nicely written and it provides a self-contained treatment of the topics.