Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.