Browse Groups

• Page 126 of AIMA, 2nd ed, notes that: It is easy to prove that a random walk will eventually find a goal or complete its exploration, provided that the space
Message 1 of 2 , Oct 14, 2005
View Source
Page 126 of AIMA, 2nd ed, notes that:

"It is easy to prove that a random walk will eventually find a goal or
complete its exploration, provided that the space is finite."

Here, a footnote continues:

"The infinite case is much more tricky. Random walks are complete on
infinite one-dimensional and two dimensional grids, but not on three
dimensional grids! In the latter case, the probability that the walk
ever returns to the starting point is only about 0.3405."

I was surprised by the claim above (random walks are complete for 1 and
2 dimensions but not for 3). Can anyone explain why this is true?

-Neil
• It all began with Polya s 1921 proof: http://mathworld.wolfram.com/PolyasRandomWalkConstants.html Then follow the link from there [Pages Linking Here] which
Message 2 of 2 , Oct 14, 2005
View Source
It all began with Polya's 1921 proof:

http://mathworld.wolfram.com/PolyasRandomWalkConstants.html

which has links to discussions of 1-, 2-, and 3-dimensional walks.

- Bob

_______________________________________________________________
Robert P. Futrelle | Biological Knowledge Laboratory
Associate Professor | College of Computer and Information
| Science MS WVH202
Office: (617)-373-4239 | Northeastern University
Fax: (617)-373-5121 | 360 Huntington Ave.
futrelle@... | Boston, MA 02115
http://www.ccs.neu.edu/home/futrelle
http://www.bionlp.org http://www.diagrams.org

http://biologicalknowledge.com
mailto:biologicalknowledge@...
_______________________________________________________________

>Page 126 of AIMA, 2nd ed, notes that:
>
>"It is easy to prove that a random walk will eventually find a goal or
>complete its exploration, provided that the space is finite."
>
>Here, a footnote continues:
>
>"The infinite case is much more tricky. Random walks are complete on
>infinite one-dimensional and two dimensional grids, but not on three
>dimensional grids! In the latter case, the probability that the walk
>ever returns to the starting point is only about 0.3405."
>
>I was surprised by the claim above (random walks are complete for 1 and
>2 dimensions but not for 3). Can anyone explain why this is true?
>
>-Neil
>
>
>
>
>
>
>"<http://groups.yahoo.com/group/aima-talk>aima-talk" on the web.
>
> To unsubscribe from this group, send an email to:
>
><mailto:aima-talk-unsubscribe@yahoogroups.com?subject=Unsubscribe>aima-talk-unsubscribe@yahoogroups.com
>
> Your use of Yahoo! Groups is subject to the

--
_______________________________________________________________
Robert P. Futrelle | Biological Knowledge Laboratory
Associate Professor | College of Computer and Information
| Science MS WVH202
Office: (617)-373-4239 | Northeastern University
Fax: (617)-373-5121 | 360 Huntington Ave.
futrelle@... | Boston, MA 02115
http://www.ccs.neu.edu/home/futrelle
http://www.bionlp.org http://www.diagrams.org

http://biologicalknowledge.com
mailto:biologicalknowledge@...
_______________________________________________________________
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.