2
$\begingroup$

I am working on a problem with a Loop Erased Random Walk used to create random spanning trees from a graph. The problem has many parts, but there are two hints to help with the more complicated problems. The hints are essentially:

1.Figure out the probability that any given edge will be contained in the uniform spanning tree.

2.Figure out the probability that an edge is added in a given direction (given the below algorithm) in the uniform spanning tree.

I have been working through this for hours and hours now and have hit a wall. Any tips towards figuring these out would be extremely helpful as I have no idea where to begin at this point.

Random Walk Algorithm:

Pick an arbitrary root in V. Begin at root and traverse graph randomly. Whenever we reach a vertex that has not yet been added to the tree, we add the edge that we used to reach that vertex to our spanning tree

$\endgroup$
  • $\begingroup$ My intuition is that the probability that any given edge $(u,v)$ will be contained in the uniform spanning tree is 1/#(path(u,v)). But I have no idea how to prove it sorry ... $\endgroup$ – wece Nov 27 '14 at 21:03
0
$\begingroup$

For the first question, I found this document, section 1.6 useful. It uses the Kirchoff's matrix tree theorem.

Denote:

  • $\mu$ is the uniform distribution,
  • $L_G$ as the Laplacian matrix if $G$ and $\tilde{L}_G$ be the Lapacian with one row and column removed
  • $G \text{\\} \{e\}$ be the new graph of $G$ after edge $e$ is contracted.

the answer to question 1 is essentially:

$$ \begin{align*} \text{Pr}_{T \sim \mu}(e \in T) &= \frac{\text{number of spanning trees containing } e}{\text{number of spanning trees}} \\ &=\frac{\det(\tilde{L}_{G} \text{\\} \{e\})}{\det(\tilde{L}_{G})} \end{align*} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.