- 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 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

>

>

>

>

>

>YAHOO! GROUPS LINKS

>

> Visit your group

>"<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

><http://docs.yahoo.com/info/terms/>Yahoo! Terms of Service.

_______________________________________________________________

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@...

_______________________________________________________________