Random graph walking can be random, but it is not always. The following paper on random walks on graphs as a tool for derandomizing probability algorithms gives

Random graph walking can be random, but it is not always. The following paper on random walks on graphs as a tool for derandomizing probability algorithms gives insight on this, as well as the probability of a random walk on a RANDOM graph being a random sampling: http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf Wikipedia's page on random walks is also pretty insightful: http://en.wikipedia.org/wiki/Random_walk http://en.wikipedia.org/wiki/Random_walk