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.)
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.