# Random Spanning Tree Edge Probability

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

• 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 ...
– wece
Commented Nov 27, 2014 at 21:03

• $$\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.
\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*}