{"id":34,"date":"2010-05-09T00:12:28","date_gmt":"2010-05-08T22:12:28","guid":{"rendered":"http:\/\/djalil.chafai.net\/blog\/?p=34"},"modified":"2011-04-15T10:34:45","modified_gmt":"2011-04-15T08:34:45","slug":"how-to-speed-up-mcmc-algorithms","status":"publish","type":"post","link":"https:\/\/djalil.chafai.net\/blog\/2010\/05\/09\/how-to-speed-up-mcmc-algorithms\/","title":{"rendered":"How to speed up MCMC algorithms"},"content":{"rendered":"<p style=\"text-align: justify;\"><a title=\"The Markov chain Monte Carlo revolution\" href=\"http:\/\/www.ams.org\/mathscinet-getitem?mr=2476411\">Markov-Chains-Monte-Carlo<\/a> (MCMC for short) methods are widely used in practice for the approximate computation of integrals on various types of spaces. More precisely, let \\(\\mu\\) be a probability measure on \\(E\\), known only up to a multiplicative constant. Let \\(K\\) be an irreducible Markov kernel on \\(E\\). Then by using a classical Metropolis-Hastings type construction, one cook up a computable ergodic Markov kernel \\(M\\) on \\(E\\) which admits \\(\\mu\\) as a unique reversible invariant law. One can then simulate a Markov chain \\((X_n)_{n\\geq1}\\) with state space \\(E\\) and kernel \\(M\\). When \\(n\\) is large, the law of the random variable \\(X_n\\) is approximately \\(\\mu\\). The construction of \\(K\\) relies in general on the knowledge of the  local structure of \\(E\\). The quantitative control of the speed of convergence is a delicate problem. Many research articles are devoted to specific models. You may take a look at the expository article of <a title=\"Analyse semiclassique d\u2019algorithmes  de type Metropolis\" href=\"http:\/\/smf4.emath.fr\/Publications\/Gazette\/2010\/123\/smf_gazette_123_16-34.pdf\">Laurent Michel<\/a> and of <a title=\"The Markov chain Monte Carlo revolution\" href=\"http:\/\/www.ams.org\/mathscinet-getitem?mr=2476411\">Persi Diaconis<\/a>.<\/p>\n<p style=\"text-align: justify;\">It is well known that nonreversible ergodic Markov chains can avoid diffusive effects and may converge faster than reversible ergodic Markov chains. It is thus tempting to think about nonreversible MCMC algorithms. This program is currently under developpement. You may take a look at the <a title=\"About convergence of second order Markov chains\" href=\"http:\/\/www.math.univ-toulouse.fr\/EVOL\/Workshop%20May%202010?action=AttachFile&amp;do=view&amp;target=miclo.pdf\">recent work of Diaconis, Miclo, and Zu\u00f1iga<\/a> on the spectral analysis of second order Markov chains i.e. \\(\\mathcal{L}(X_{n+1}|X_n,X_{n-1},\\ldots)=\\mathcal{L}(X_{n+1}|X_n,X_{n-1})\\).<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Markov-Chains-Monte-Carlo (MCMC for short) methods are widely used in practice for the approximate computation of integrals on various types of spaces. More precisely, let \\(\\mu\\)&#8230;<\/p>\n<div class=\"more-link-wrapper\"><a class=\"more-link\" href=\"https:\/\/djalil.chafai.net\/blog\/2010\/05\/09\/how-to-speed-up-mcmc-algorithms\/\">Continue reading<span class=\"screen-reader-text\">How to speed up MCMC algorithms<\/span><\/a><\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"iawp_total_views":152},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/34"}],"collection":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/comments?post=34"}],"version-history":[{"count":2,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/34\/revisions"}],"predecessor-version":[{"id":1677,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/34\/revisions\/1677"}],"wp:attachment":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/media?parent=34"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/categories?post=34"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/tags?post=34"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}