Loading ...
Sorry, an error occurred while loading the content.

573random walks in an infinite state space

Expand Messages
  • Neil Conway
    Oct 14 1:19 AM
    • 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?

    • Show all 2 messages in this topic