brownian motion on a weighted undirected graph - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T05:00:34Z http://mathoverflow.net/feeds/question/47006 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/47006/brownian-motion-on-a-weighted-undirected-graph brownian motion on a weighted undirected graph noobcake 2010-11-22T21:44:54Z 2010-11-22T22:54:19Z <p>The question <a href="http://mathoverflow.net/questions/46991/brownian-bridge-interpreted-as-brownian-motion-on-the-circle" rel="nofollow">"Brownian bridge interpreted as Brownian motion on the circle"</a> reminds me of a question along similar lines. Say that you have a weighted undirected graph \$G\$, and you have constrained Brownian motion on the graph where edges have lengths equal to the reciprocal of their weights. So for example a cycle with weight 1 (and therefore length 1) would be like the Brownian bridge. By 'constrained' I mean that when edges meet at a vertex, the endpoints of each edge should have the same value.</p> <p>So my question is how to compute the matrix whose \$(i,j)\$ entry is the variance of the difference between values at vertices \$i\$ and \$j\$, given a matrix representation of the graph, for example the graph Laplacian or weighted adjacency matrix.</p> <p>For example, if the graph is a tree, then the \$(i,j)\$ entry should be proportional to the sum of edge lengths along the unique path between vertices \$i\$ and \$j\$. But when there are cycles in the graph, the variance should be lower because of the additional brownian-bridge-like constraints.</p> http://mathoverflow.net/questions/47006/brownian-motion-on-a-weighted-undirected-graph/47010#47010 Answer by Ori Gurel-Gurevich for brownian motion on a weighted undirected graph Ori Gurel-Gurevich 2010-11-22T22:22:45Z 2010-11-22T22:22:45Z <p>You're basically talking about the <a href="http://en.wikipedia.org/wiki/Gaussian_free_field" rel="nofollow">Gaussian Free Field</a> on a graph. There are many recent works on that and also on similar random embedding of graphs, e.g. <a href="http://arxiv.org/abs/1005.4636" rel="nofollow">hypercube</a>.</p>