Markov chains

In 1906, at the age of 50, Andrey Markov introduced his chain model known nowadays as Markov chains. This model played a key role in the development of the theory of stochastic processes during the twentieth century, and is still the source of numerous open and rich problems, with applied or theoretical motivations. It is amusing to note that Perron and Frobenius studied the spectral decomposition of positive matrices during the same period, but the connection with Markov chains was not made immediately. You may read the historical paper of Seneta on the subject. On the theoretical side of probability theory, the study of Markov processes was extremely active after the second world war, but was gradually superseded by the study of general stochastic processes and (semi)martingales for a while.

Persi Diaconis (2005): “I only met P.-A. Meyer once (Luminy, 1995). He kindly stayed around after my talk and we spoke for about an hour. I was studying rates of convergence of finite state space Markov chains. He made it clear that, for him, finite state space Markov chains is a trivial subject. Hurt but undaunted, I explained some of our results and methods. He thought about it and said, “I see, yes, those are very hard problems”. […] In the present paper I treat rates of convergence for a simple Markov chain. I am sorry not to have another hour with Paul-Andre Meyer. […]”.

Finite Markov chains coincide with random walks on weighted graphs. Personally, I have learnt Markov chains at the end of the past century from Dominique Bakry and Laurent Saloff-Coste. I like very much this probabilistic subject, connected to linear algebra, algebra, analysis, statistics, geometry, and ergodic theory. It plays a role in many applied domains, has connections with Computer Science and Physics(*), and allows simulation. Last but not least, it carries many fascinating elementary  problems. Here is one of them: consider a sequence of complex numbers lying in the unit disk of the complex plane, stable by conjugacy and containing the unity. Can you construct a Markov chain which admits this sequence as its spectrum? How? Some answers can be found in a book by Chu and Golub (section 4.5).

(*) to me econometrics and mathematical finance/biology are part of Physics at large.

The famous Mersenne twister pseudo-random generator is an example of a finite state space Markov chain (matrix linear recurrence over \( \mathrm{F}_{\!\!2}\)) used billions of times daily worldwide.

Here are some basic books (in English) about discrete Markov chains that I like:

• Markov chains, by Norris (Englishman)
• Markov chains, by Revuz (Frenchman)
• Finite Markov chains and algorithmic applications, by Haggström
• Construction of Stochastic Processes, Coupling and Regeneration, by Ferrari and Galves
• Markov processes and applications. Algorithms, networks, genome and finance, by Pardoux

and more advanced or specialized books (listed here in a pseudo-random order):

• Reversible Markov Chains and Random Walks on Graphs, by Aldous and Fill
• General irreducible Markov chains and nonnegative operators, by Nummelin
• Lectures on finite Markov chains, by Saloff-Coste
• Non-negative matrices and Markov chains, by Seneta
• Group representations in probability and statistics, by Diaconis
• Markov chains, Gibbs fields, Monte-Carlo simulation, and queues, by Brémaud
• Markov chains and mixing times, by Levin, Peres, and Wilmer
• Eight lectures on mixing time by Berestycki
• Mathematical Aspects of Mixing Times in Markov Chains, by Tetali and Montenegro
• Markov chains and stochastic stability, by Meyn and Tweedie
• Reversibility and stochastic networks, by Kelly
• Random walks on electric networks, by Doyle and Snell
• Lectures on the coupling method, by Lindvall

• Large deviations and metastability, by Olivieri and Vares
• Mathematical population genetics, by Ewens
• Ancestral inference in population genetics, by Tavaré
• Bayesian methods for data analysis, by Carlin and Louis
• Interacting particle systems, by Liggett
• Branching processes, by Athreya and Ney
• Principles of random walks, by Spitzer
• Feynman-Kac formulae, by Del Moral
• Gibbs measures and phase transitions, by Georgii
• Lectures on Glauber dynamics for discrete spin models, by Martinelli
• Random polymer models, by Giacomin
• Random fragmentation and coagulation processes, by Bertoin
• Combinatorial stochastic processes, by Pitman

Still I am not completely satisfied by this list of references. The subject is actually so rich that all these books are complementary. About Markov chains, did you know that Noam Chomsky became famous fifty years ago by proving that no matter how complex a finite state machine is, it could not handle all constructions of English?