Discovering properties of a graph by means of random walk Suppose I have a regular, undirected, non-bipartite, finite, connected graph on $N$ vertices. Some fraction $\frac{c}{N}$ of the vertices are coloured gold, the rest are coloured black. If I let you perform a random walk on my graph, what machinery exists for you to discover what the value of $c$ is?
 A: I don't know how practical this is, but theoretically the empirical proportion of visits to gold sites 
will converge almost surely to the true proportion. That is, as $n\to\infty$ we get
$${1\over n}\sum_{k=1}^n 1\lbrace X(k)\mbox{ is gold }\rbrace\to {c\over N}.$$ 
This holds even if graph is bipartite. The important requirement is connectedness so
that the chain is irreducible.     
Added:
The quality of this estimate is a significantly more difficult, 
and more interesting problem.
Look at Section 12.6 (especially equation (12.27)) 
of Markov Chains and Mixing Times by  Levin, Peres, and Wilmer 
(freely available at http://pages.uoregon.edu/dlevin/MARKOV/)
The authors suggest a burn-in time, i.e., throwing away the first
$r$ observations. The burn-in time $r$ and the number $t$ of 
additional observations to get a good estimate depend on the 
eigenstructure of the transition matrix. These will depend heavily on 
the shape and geometry of the graph.
See also section 6.3 of Markov chains: Gibbs fields, Monte Carlo simulation, and queues
 by Pierre Brémaud, where he calculates the asymptotic variance of the estimator.
