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?
$\begingroup$
$\endgroup$
4
asked Apr 17, 2011 at 10:51
-
1$\begingroup$ Suppose the gold colored vertices are all clustered together. If you start your random walk in that part and the set of golden vertices is large enough, the connections with black ones being only on the "boundary" of that set, then you're pretty much screwed if you don't let your random walker go on for long enough. So you'll need some homogeneity assumption on your distribution of colours for the random walker to be effective in discovering the proportion $c/N$. $\endgroup$– RaskolnikovCommented Apr 17, 2011 at 10:59
-
$\begingroup$ @Raskolnikov - I think that because my graph has the stated properties (regular, undirected, non-bipartite, finite, connected) the random walk is ergodic, with (unique) uniform stationary distribution. You can walk around the graph and sample as you like. Does this resolve your issue? $\endgroup$– Undercover MathematicianCommented Apr 17, 2011 at 11:06
-
$\begingroup$ While the graph may be ergodic, that does not mean that all vertices can be reached in reasonable times. I don't see how any of the properties listed can guarantee that. But I'm no expert on graph theory, just going on my physics intuition here. I think what you really need is a hypothesis on the distribution of the colors. $\endgroup$– RaskolnikovCommented Apr 17, 2011 at 14:15
-
$\begingroup$ I would guess that the circle graph and the complete graph are your two "edge cases" (no pun intended) in this problem. $\endgroup$– cardinalCommented Apr 17, 2011 at 14:26
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
13
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.
-
$\begingroup$ (+1) To me this question (perhaps naively) sounds like a graph covering problem. We know $c$ if and only if we've visited each vertex at least once (assuming we get to record the color of each vertex in a list as we visit it). For the complete graph, this reduces to the birthday problem. Fixing the number of vertices $n$, I'm guessing the complete graph is covered the "fastest" and the circle graph is covered the "slowest" under the conditions imposed by the OP. $\endgroup$– cardinalCommented Apr 17, 2011 at 14:53
-
$\begingroup$ @cardinal Hmmm... yes the question is pretty vague about "what machinery" means. I agree that questions on covering the graph are a lot harder. Perhaps my answer will still be of some use. $\endgroup$– user940Commented Apr 17, 2011 at 14:58
-
$\begingroup$ @cardinal @Byron , what if I throw in an extra condition: N is large enough that you cannot feasibly visit every vertex, and the number of gold vertices are not "too small" so that you see them in feasible time. As before, you can sample vertices uniformly at random. Now, if at time t you've seen k gold vertices, how sure can you be that the true ratio is k/t? I was thinking the Chernoff bound might help, but I'm not sure.. Thanks for answer so far! $\endgroup$ Commented Apr 17, 2011 at 18:32
-
1$\begingroup$ @Undercover Mathematician I have added some further information if you want to investigate the quality of my estimate. $\endgroup$– user940Commented Apr 18, 2011 at 2:24
-
2$\begingroup$ @cardinal On the other hand, if you can sample uniformly from the nodes you might be better off taking an i.i.d. sample instead of using the Markov chain approach. The best solution depends on what is possible, I suppose. $\endgroup$– user940Commented Apr 18, 2011 at 12:19