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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|improve this answer
    
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)$. – maybeshewill Mar 4 at 10:02

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.