3 ms·
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+ran
by adrianN 16y ago
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 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 16y agoInterestingly, even over an infinite grid you should get to your target with probability 1: http://www.math.cornell.edu/~mec/Winter2009/Thompson/randomwalks.html http://www.math.cornell.edu/~mec/Winter2009/Thompson/randomw...