## random walks in an infinite state space

Expand Messages
• 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
• 0 Attachment
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
• 0 Attachment
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.