Markov Chains: Analytic and Monte Carlo Computations

Introduction

This book is written with a broad spectrum, that allows for different readings at various levels. It tries nevertheless to plunge quickly into the heart of the matter. The basic analytical tool is the maximum principle, which is natural in this setting. It is superficially compared to martingale methods in some instances. The basic probabilistic tool is the Markov property, strong or not.

After the first definitions in Chapter 1, matrix notation is described and random iterative sequences are introduced. An elementary algebraic study is performed, which could be used for a study of finite-state Markov chains. The Doeblin condition and its consequences are very present. The fundamental examples are then introduced.

Probabilistic techniques start in earnest in Chapter 2, which study filtrations, the Markov property, stopping times, and the strong Markov property. The technique of conditioning on the first step of the chain, called “the one step forward method,” is then developed. It is applied to Dirichlet problems and, more generally, to the study of first hitting times and locations.

Chapter 3 delves into the analysis of the probabilistic behaviors of the sample paths. This results in the fundamental theorems which link the algebraic notions of invariant laws and measures with sample-path notions such as transience and recurrence (null or positive). Its Complements subsections extend this perspective to the links between nonnegative superharmonic functions and transience-recurrence ...