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?
Discovering properties of a graph by means of random walk
-
0I would guess that the circle graph and the complete graph are your two "edge cases" (no pun intended) in this problem. – 2011-04-17
1 Answers
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.
-
0@cardinal The expensive draw to ensure stationarity would often come from running the random walk for a long time, in which case we come full circle back to the burn-in idea. – 2011-04-18