573random walks in an infinite state space
- Oct 14 1:19 AMPage 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?
- Next post in topic >>