How to compute a marginal probability

Question

Given a weighted graph, using the Kirchhoff's matrix tree theorem, how can I compute the marginal edge presence probability: $$P_\beta(ij)=Z_\beta^{-1}\sum_{\text{T spanning tree:$(i,j)\in E(T)$}}e^{-\beta W(T)}$$ knowing that:

• $Z_\beta=\sum_{\text{T spanning tree:}}e^{-\beta W(T)}$
• $W(T)=\sum_{(i,j)\in E(T)}W(i,j)$
• $P_{\beta}(T)=Z^{-1}_{\beta}e^{-\beta W(T)}$ (Boltzmann distribution).

I managed to calculate $Z_\beta$ using the Kirchhoff's matrix tree theorem, but I couldn't handle the sum.

Answer 1

Supposing that "compute" here means express in terms of determinants of Laplacian matrices:

Let $Z_\beta$ be as you've defined it for a given graph $G$ and let $Z_\beta'$ be this quantity evaluated for the graph $G/e$, which is $G$ but with the edge $e=\{i,j\}$ contracted. Note that both of these quantities can be expressed via Kirchhoff's Matrix-Tree theorem as determinants of Laplacian matrices.

The key fact that you need is that the spanning trees of $G$ that include a particular edge are in bijection with spanning trees of $G/e$ (via contracting $e$ or reversing that contraction).

Thus the probability you want is equal to the ratio $Z_\beta'/Z_\beta$.

As an aside, Kirchhoff also showed that this ratio is equal to the effective resistance of the graph if every edge has resistance $e^{-\beta W(i,j)}$.