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