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?
