4
$\begingroup$

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?

  • 0
    I 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 1

6

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