3
$\begingroup$

I vaguely recall a result like the following from one of my complexity theory classes in school: given a 2d maze (which I guess we can think of as a directed graph with a fixed start node and exit node), if we simply take a random walk through the maze, then with high probability we will reach the exit from the start in a short amount of time.

What is the exact statement of the result, and can anyone point me to where I can read about it more? (Googling a bit turns up a paper called Random walks, universal traversal sequences, and the complexity of maze problems, but it's behind a paywall, so I'm not sure if it's what I'm looking for.)

1 Answers 1

7

A random walk on an connected, undirected graph will eventually visit every node with probability $1$ (this is trivial). The expected time until this happens is $O(n^3)$ (where $n$ is the number of vertices) - this is Theorem 6.8 in the Motwani/Raghavan Randomized Algorithms textbook.

  • 1
    Note that the result of Theorem 6.8 in this book is, that the expected time until we visit every node in an undirected connected graph is $\leq 2m(n-1)$. So depending on the number of edges you might get a much better bound -- e.g. in a planar graph it is in $\mathcal{O}(n^2)$.2016-03-04