{"id":2361,"date":"2011-09-08T10:10:33","date_gmt":"2011-09-08T08:10:33","guid":{"rendered":"http:\/\/djalil.chafai.net\/blog\/?p=2361"},"modified":"2012-12-13T10:12:29","modified_gmt":"2012-12-13T09:12:29","slug":"markov-chains","status":"publish","type":"post","link":"https:\/\/djalil.chafai.net\/blog\/2011\/09\/08\/markov-chains\/","title":{"rendered":"Markov chains"},"content":{"rendered":"

\"A<\/a><\/p>\n

In 1906, at the age of 50, Andrey Markov<\/a> introduced his chain model known nowadays as Markov chains<\/a><\/em>. 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<\/a> and Frobenius<\/a> studied the spectral decomposition of positive matrices<\/a> during the same period, but the connection with Markov chains was not made immediately. You may read the historical paper of Seneta<\/a> 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.<\/p>\n

Persi Diaconis (2005)<\/a>: ``I only met P.-A. Meyer<\/a> 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. [...]''<\/em>.<\/p>\n

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<\/a> and Laurent Saloff-Coste<\/a>. 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\u00a0 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<\/a> (section 4.5).<\/p>\n

(*) to me econometrics and mathematical finance\/biology are part of Physics at large.<\/p>\n

The famous Mersenne twister<\/a> 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.<\/p>\n

Here are some basic books (in English) about discrete Markov chains that I like:<\/p>\n