Press "Enter" to skip to content

Markov chains

A two states Markov chain

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:

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

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?

One Comment

  1. […] Complexity had a guest post (and lots of discussion) from the IT History Society. Finally, Libres pensées d’un mathématicien ordinaire shared a large list of references on Markov Chains and The Geomblog saw some conference blogging […]

Leave a Reply

Your email address will not be published. Required fields are marked *