Random Spanning Tree Edge Probability

Question

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

Answer 1

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*} $$