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

Re: [aima-talk] random walks in an infinite state space

Expand Messages
  • 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 1 of 2 , Oct 14, 2005
    • 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.