You can bound the expected cover time of a random walk on a graph. This is an in... | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

		adrianN on Jan 20, 2011 \| parent \| context \| favorite \| on: Maze Generation: Wilson's algorithm You can bound the expected cover time of a random walk on a graph. This is an intensively studied problem: http://scholar.google.de/scholar?q=covering+time+random+walk iirc the expected cover time for any graph is polynomial with high probability. Something like \|E\|^3 or so.

repsilat on Jan 20, 2011 [–]

Interestingly, even over an infinite grid you should get to your target with probability 1:

http://www.math.cornell.edu/~mec/Winter2009/Thompson/randomw...

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact