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

random walks in an infinite state space

Expand Messages
  • Neil Conway
    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
    View Source
    • 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
    • Robert Futrelle
      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
      View Source
      • 0 Attachment
        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@...
        _______________________________________________________________
      Your message has been successfully submitted and would be delivered to recipients shortly.