{"id":184522,"date":"2003-11-13T00:00:00","date_gmt":"2009-10-31T13:51:03","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/msr-research-item\/random-walk-and-random-aggregation-derandomized\/"},"modified":"2016-09-09T09:51:25","modified_gmt":"2016-09-09T16:51:25","slug":"random-walk-and-random-aggregation-derandomized","status":"publish","type":"msr-video","link":"https:\/\/www.microsoft.com\/en-us\/research\/video\/random-walk-and-random-aggregation-derandomized\/","title":{"rendered":"Random walk and random aggregation, derandomized"},"content":{"rendered":"
\n

This talk will describe a general recipe for replacing discrete stochastic processes by deterministic analogues that satisfy the same first-order limit laws but have smaller fluctuations. The recipe will be applied to several illustrative problems in the study of random walk and random aggregation. In particular, a derandomized version of the internal diffusion-limited aggregation model in two dimensions gives rise to a growing blob that is remarkably close to circular and also displays intriguing internal structures (see http:\/\/www.math.wisc.edu\/~propp\/million.gif). This is joint work with Ander Holroyd and Lionel Levine.<\/p>\n

An early write-up of derandomized aggregation:<\/b><\/p>\n

www.math.wisc.edu\/~propp\/hidden\/rotor<\/p>\n

Email-log of some messages I sent out about derandomized walk:<\/b><\/p>\n

www.math.wisc.edu\/~propp\/hidden\/test\/rotorwalk.to<\/p>\n

Lionel Levine’s undergraduate thesis:<\/b><\/p>\n

www.math.berkeley.edu\/~levine\/rotorrouter.pdf<\/p>\n

Slides from a talk given by Lionel Levine:<\/b><\/p>\n

www.math.berkeley.edu\/~levine\/slides\/<\/p>\n

Lionel Levine and Adam Kampff’s picture of the rotor-router aggregation blob after 270,000 particles have aggregated:<\/b><\/p>\n

www.math.berkeley.edu\/~levine\/private\/rotorrouter\/bigblob.bmp<\/p>\n

Two close-ups of that same picture:<\/b><\/p>\n

www.math.berkeley.edu\/~levine\/private\/rotorrouter\/closeup.bmp<\/p>\n

Ed Pegg’s picture of the rotor-router blob after 750,000 particles have aggregated:<\/b><\/p>\n

www.math.wisc.edu\/~propp\/proppcircle.gif<\/p>\n

Ander Holroyd’s picture of the rotor-router blob after 1,000,000 particles have aggregated:<\/b><\/p>\n

www.math.wisc.edu\/~propp\/million.gif<\/p>\n

Vishal Sanwalani’s picture of the state achieved by the abelian sandpile model when sixty thousand grains have been added:<\/b><\/p>\n

www.math.wisc.edu\/~propp\/hidden\/501.gif<\/p>\n

Hal Canary’s applets for demonstrating derandomized walk and aggregation:<\/b><\/p>\n

http:\/\/ups.physics.wisc.edu\/~hal\/SSL\/2003\/<\/p>\n<\/div>\n

<\/p>\n","protected":false},"excerpt":{"rendered":"

This talk will describe a general recipe for replacing discrete stochastic processes by deterministic analogues that satisfy the same first-order limit laws but have smaller fluctuations. The recipe will be applied to several illustrative problems in the study of random walk and random aggregation. In particular, a derandomized version of the internal diffusion-limited aggregation model […]<\/p>\n","protected":false},"featured_media":195465,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr_hide_image_in_river":0,"footnotes":""},"research-area":[],"msr-video-type":[],"msr-locale":[268875],"msr-post-option":[],"msr-session-type":[],"msr-impact-theme":[],"msr-pillar":[],"msr-episode":[],"msr-research-theme":[],"class_list":["post-184522","msr-video","type-msr-video","status-publish","has-post-thumbnail","hentry","msr-locale-en_us"],"msr_download_urls":"","msr_external_url":"https:\/\/youtu.be\/KS7lSF5R4Qw","msr_secondary_video_url":"","msr_video_file":"","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/184522","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-video"}],"version-history":[{"count":0,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/184522\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media\/195465"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=184522"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=184522"},{"taxonomy":"msr-video-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video-type?post=184522"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=184522"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=184522"},{"taxonomy":"msr-session-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-session-type?post=184522"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=184522"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=184522"},{"taxonomy":"msr-episode","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-episode?post=184522"},{"taxonomy":"msr-research-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-theme?post=184522"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}