tag:blogger.com,1999:blog-3722233.post5701624028183470062..comments2024-10-10T06:29:39.038-05:00Comments on Computational Complexity: Intuitive ProofsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-89197110004934074022015-04-21T22:50:03.663-05:002015-04-21T22:50:03.663-05:00A guess at how to try it: consider only the direct...A guess at how to try it: consider only the direction you're more biased towards, since you're more likely to get lost that way.isomorphismeshttp://isomorphism.esnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44725571306398839472015-03-31T03:23:41.985-05:002015-03-31T03:23:41.985-05:00This is explored in great detail in the book "...This is explored in great detail in the book "Random Walks and Electrical Networks" by Peter Doyle and J. Laurie Snell. (now available free via a GNU FDL on the web.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10021868840440145832015-03-30T14:41:27.358-05:002015-03-30T14:41:27.358-05:00I had asked a similar question on cstheory a while...I had asked a similar question on cstheory a while back, and the intuition you describe is confirmed in even more detail by the answers (and the linked MO question). In other words, even "2+eps" dimensional walks are transient. <br /><br />http://cstheory.stackexchange.com/questions/8058/drunken-birds-vs-drunken-ants-random-walks-between-two-and-three-dimensionsSuresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90763521785671226692015-03-30T13:46:42.026-05:002015-03-30T13:46:42.026-05:00I really appreciate this intuition. Before, all I ...I really appreciate this intuition. Before, all I had was a vague idea that 3-dimensions was too "sparse" but 2-dimensions wasn't, which was pretty unsatisfying.<br /><br />Any chance this intuition can generalize to biased random walks? (I don't see it, but maybe someone else does...)Joshua BrulĂ©https://www.blogger.com/profile/07163957187678854120noreply@blogger.com