I was reading Artificial Intelligence: Modern Approach (Norvig and Russell), and there was a footnote that really caught my attention. I apologize if the problem is more in the domain of CS than mathematics!

Random walks are complete on infinite one-dimensional and two-dimensional grids. On a three-dimensional grid, the probability that the walk ever returns to the starting point is only about .3405 (Hughes 1995).

(Hughes 1995 is "Random Walks and Random Environments, Vol. 1", a damn expensive book.)

Overall, I had two questions. 1) What does returning to the start have to do with completeness? Returning to start seems necessary in 1-d case (otherwise you'd never reach the other side), but not in any higher dimensions. 2) How was that .3405 probability calculated, and why is it not 1? How would it be calculated for k dimensions?

3) Bonus: I know there's a notion of fractional dimensions, and it seems weird to talk about it in this context (how can a node in a grid have 4 and a half edges leading off of it?), but there is some way in which it does make sense, what fractional dimension would be the cut-off between complete-ness and not?

  • $\begingroup$ Here are some free links: about the constant .3405, see Pólya's Random Walk Constants; on the more general setting of recurrence/transience, see Doyle and Snell's marvelous little book Random Walks and Electric Networks. $\endgroup$ – Did Jun 7 '12 at 17:46
  • $\begingroup$ This is indeed more of a math question than a CS question. $\endgroup$ – Stefan Smith Jun 8 '12 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.