{"id":8094,"date":"2014-11-15T11:03:53","date_gmt":"2014-11-15T10:03:53","guid":{"rendered":"http:\/\/djalil.chafai.net\/blog\/?p=8094"},"modified":"2014-11-23T19:35:31","modified_gmt":"2014-11-23T18:35:31","slug":"metropolis-hastings-algorithm-who-cares","status":"publish","type":"post","link":"https:\/\/djalil.chafai.net\/blog\/2014\/11\/15\/metropolis-hastings-algorithm-who-cares\/","title":{"rendered":"Metropolis-Hastings algorithm - Who cares?"},"content":{"rendered":"

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

Certain probabilists and statisticians like to repeat that the Metropolis-Hastings algorithm<\/a> is one of the most important algorithms on earth, and drop<\/a> the name of Diaconis<\/a> to reinforce the statement. Well, beyond earth, this might be true in the whole universe, who knows?<\/p>\n

Let us recall that the Metropolis-Hastings algorithm is a remarkable recipe to produce a Markov kernel which can be simulated and which admits a prescribed probability distribution, known up to a multiplicative constant, as its unique reversible invariant distribution. The idea behind the Metropolis-Hastings algorithm is very simple, and can be traced back to an article published in 1953 entitled Equation of State Calculations by Fast Computing Machines<\/em>, written by Nicholas Metropolis<\/a>, Arianna & Marshall Rosenbluth, and Augusta & Edward Teller<\/a>, and to an article published in 1970 entitled Monte Carlo Sampling Methods Using Markov Chains and Their Applications<\/em>, written by\u00a0W. Keith Hastings<\/a>. It mixes the idea of rejection sampling<\/a> of Georges-Louis Leclerc Comte de Buffon<\/a> and John von Neumann<\/a> with the Markov chain<\/a> concept. By the way, Edward Teller is among other things credited as being the mother of the US H-bomb together with the father Stanislaw Ulam (who was by the way fond of the Monte-Carlo method)<\/a>. Nowadays, the Metropolis-Hastings algorithm is available in many versions and is at the heart of the so-called Monte-Carlo-Markov-Chain (MCMC)<\/a> numerical algorithms.<\/p>\n

Yes the Metropolis-Hastings algorithm is a remarkable widely used non exact algorithm for stochastic simulation. However, the most important algorithms used in the world are probably more related to information\/signal processing,\u00a0 number crunching, linear algebra, and optimization, such as the Huffman coding algorithm<\/a>, the Lempel-Ziv-Welch coding algorithm<\/a>, the Hamming coding algorithm<\/a>, the Reed-Muller coding algorithm<\/a>, the Gallager coding algorithm<\/a>, the Gram-Schmidt algorithm<\/a>, the QR algorithm<\/a>, the LU algorithms<\/a>,\u00a0 the Gauss elimination algorithm<\/a>, the Euclidean algorithm<\/a>, the Newton algorithm<\/a>, the Simplex algorithm<\/a>, the Hungarian algorithm<\/a>, the Fast Fourier Transform algorithm<\/a>, etc.<\/p>\n

Further reading.<\/strong><\/p>\n