{"id":81,"date":"2020-02-24T09:24:20","date_gmt":"2020-02-24T09:24:20","guid":{"rendered":"http:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/kim-ward\/?p=81"},"modified":"2022-08-10T10:19:17","modified_gmt":"2022-08-10T10:19:17","slug":"coupling-from-the-past","status":"publish","type":"post","link":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/kim-ward\/2020\/02\/24\/coupling-from-the-past\/","title":{"rendered":"Coupling From The Past"},"content":{"rendered":"\n<p> In Mathematics, often you don\u2019t have a neat formula for the things you want to calculate. However, you can sometimes use an algorithm to get an answer that\u2019s as close as you want, for example finding the root of an equation by rearranging it in your calculator and then pressing the = sign a lot of times.<\/p>\n\n\n\n<p>These algorithms usually have starting values, and picking the wrong starting value can affect how long the algorithm needs to run to get a \u201dgood enough\u201d answer. But what if you didn\u2019t need to pick a starting value or an amount of time to run the algorithm, and it just gave you the exact right answer? This report examines one way to do this, called Coupling From The Past or CFTP for short.<\/p>\n\n\n\n<p>Instead of running our algorithm into the future (where no matter how long we run it we\u2019ll always be a tiny bit away from the true answer), CFTP asks us to pretend that our algorithm has been running for an infinite time in the past up until now. It then finds out where we would be if that was the case. Since the algorithm has been running for an infinitely long time, it turns out we must be exactly at the right answer. CFTP works by considering every single possible starting value, and then tries to make them \u201dcouple up\u201d to end up at the same place as quickly as possible by fiddling about with the random numbers the algorithm uses. Then it doesn\u2019t matter where the algorithm started from infinitely far in the past, because all the roads lead here!<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"408\" src=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/kim-ward\/wp-content\/uploads\/sites\/16\/2020\/02\/cftp_monotone-1024x408.png\" alt=\"\" class=\"wp-image-82\" srcset=\"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/kim-ward\/wp-content\/uploads\/sites\/16\/2020\/02\/cftp_monotone-1024x408.png 1024w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/kim-ward\/wp-content\/uploads\/sites\/16\/2020\/02\/cftp_monotone-300x119.png 300w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/kim-ward\/wp-content\/uploads\/sites\/16\/2020\/02\/cftp_monotone-768x306.png 768w, https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/kim-ward\/wp-content\/uploads\/sites\/16\/2020\/02\/cftp_monotone.png 1090w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><figcaption>  Coupling From The Past makes every starting value end up at the same place. Source for image:  <a href=\"https:\/\/arxiv.org\/abs\/math\/9912225\">https:\/\/arxiv.org\/abs\/math\/9912225<\/a> <\/figcaption><\/figure>\n\n\n\n<p>CFTP is quite a tricky method. It only works for some algorithms and needs to have random numbers, and running something \u201dfrom the past\u201d is a lot harder to get your head around than running it the normal way. In particular, you need to be very careful where you\u2019re getting those random numbers from, or the end answer won\u2019t be right.<\/p>\n\n\n\n<p>Luckily, we can tell the computer to give us the same random numbers we asked it for a while ago by setting a random \u201dseed\u201d. Without this, CFTP wouldn\u2019t be possible.<\/p>\n\n\n\n<p>See the creator of CFTP&#8217;s website  <a href=\"http:\/\/www.dbwilson.com\/exact\/\">http:\/\/www.dbwilson.com\/exact\/<\/a> to get more into the mathematics of this algorithm.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In Mathematics, often you don\u2019t have a neat formula for the things you want to calculate. However, you can sometimes&hellip;<\/p>\n","protected":false},"author":16,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-81","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/kim-ward\/wp-json\/wp\/v2\/posts\/81","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/kim-ward\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/kim-ward\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/kim-ward\/wp-json\/wp\/v2\/users\/16"}],"replies":[{"embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/kim-ward\/wp-json\/wp\/v2\/comments?post=81"}],"version-history":[{"count":1,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/kim-ward\/wp-json\/wp\/v2\/posts\/81\/revisions"}],"predecessor-version":[{"id":83,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/kim-ward\/wp-json\/wp\/v2\/posts\/81\/revisions\/83"}],"wp:attachment":[{"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/kim-ward\/wp-json\/wp\/v2\/media?parent=81"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/kim-ward\/wp-json\/wp\/v2\/categories?post=81"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.lancaster.ac.uk\/stor-i-student-sites\/kim-ward\/wp-json\/wp\/v2\/tags?post=81"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}