Denumerable Markov chains. Generating functions, boundary theory, random walks on trees. (Q834045): Difference between revisions

This is a textbook on discrete time Markov chains on countable state spaces (denumerable Markov chains as they are called in the title). What sets this work apart from the multitude of available textbooks on the subject is the emphasis on some aspects that are usually not treated in much detail in introductory texts on Markov chains: generating functions, boundary theory, and random walks on trees. The author has a very clear and pleasant style of writing. There are many examples and exercises throughout the text. Solutions to all exercises are given at the end of the book. (A selection of) the text can serve as the basis of a one-semester course on the subject. But its accessible style also makes it perfectly suitable for an individual study. In fact, the book starts with three examples of Markov chains and possible questions about their long time behavior. Only then are Markov chains formally introduced and constructed with the help of Kolmogorov's extension theorem. Very soon after that, generating functions are introduced and used to answer some of the questions raised in the first examples. The next two chapters treat classical aspects of the theory: irreducibility, periodicity, and recurrence/transience. The convergence theorem for irreducible, positive recurrent, aperiodic Markov chains is proved in two different ways: The first proof is based on the Perron-Frobenius theorem and applies mostly to chains on finite state spaces. The second proof is based on coupling methods. The fourth chapter focuses on reversible Markov chains. The network interpretation of a reversible chain is presented, and some discrete potential theory is introduced. For reversible chains on finite state spaces, the speed of convergence to equilibrium is described in terms of the spectrum of the transition operator. Then, the Poincaré inequality is proved and used to obtain estimates on the spectral gap in a large number of examples, among others card shuffling. There is also a section on infinite reversible chains. The fifth chapter treats in detail some Markov chains that arise as models in population evolution: birth and death processes, Galton-Watson processes, and branching Markov processes. The treatment here is based very much on generating functions. The next three chapters treat the potential theory of Markov chains. Chapter 7 focuses on boundary theory. The longest chapter is Chapter 9, which treats the nearest neighbor random walk on trees (mostly infinite ones). Here, many questions can be answered with the help of generating functions, and the author consistently does so. Finally, there are solutions to all exercises.