The reduced graph Laplacian is $L^{(0)}=\Delta(I-P^{(0)})$. By the <matrix-tree theorem>, the number $\tau(D)$ of spanning trees is
$$
\tau(D)=\det L^{(0)}=\Delta^n\det(I-P^{(0)}).
$$
Combining this with part (a) gives
$$
\prod_{j=1}^n g_{D\setminus\{x_0,\ldots,x_{j-1}\}}(x_j)
=\frac{\Delta^n}{\tau(D)}.
$$
This is also the normalization behind <Wilson algorithm>: loop-erased random walks attach the vertices successively, and the order-independent product ensures that every rooted spanning tree has probability $1/\tau(D)$.

Solution

Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 209 / 4 / b / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2025/iii/paper-209/4/b/solution