# Probability that a vertex in the spanning tree of an $N$ x $N$ grid graph is a leaf

Suppose we have an $N$ x $N$ grid graph $G(V,E)$ and we construct a spanning tree of this graph in the following way.

Start with a set $S$ which contains only the vertex at the top left corner of the grid graph (i.e location $(0,0)$), and an empty set $T$ which will contain our spanning tree.
Now pick an edge at random (with equal probability) from the set of edges $(p,q)\in E(G)$ such that $p \in S$ and $q \not \in S$.
Add this edge to our set $T$ and add $q$ to set $S$, repeat this process until we obtain a spanning tree.

Now, the problem is this:
What is the probability that a given vertex of the grid graph at location $(x,y)$ is a leaf in our spanning tree? In general, what is the expected number of leafs in a spanning tree constructed in this way? If this problem is too difficult, what can we say about a smaller grid? For example if we consider an $N$ x $2$, $N$ x $3$, ... e.t.c grid graph

Note:
This was inspired by a more general question asked by Nick Wu on Quora

• Are all edges $(p, q)$ equiprobable? Nov 21, 2013 at 6:39
• Yes, all edges $(p,q)$ where $p \in S$ and $q \not \in S$ are equally likely to be chosen at any given instance. Nov 21, 2013 at 7:02
• My only issue with the example of the $N \times N$ grid is that all the vertices will be slightly different. The torus $\mathbb{Z}_n \times \mathbb{Z}_n$ would be simpler... is that acceptable? Nov 27, 2013 at 14:21
• Yes, that would be interesting, I'm basically trying to see if there are known techniques for solving problems of this nature. Nov 27, 2013 at 16:46

I used a computer to compute the probabilities on small grids.

For $2x2$ :

$$\begin{array}{|c|c|}\hline\frac{1}{4}&\frac{1}{2}\\\hline\frac{1}{2}&\frac{3}{4}\\\hline\end{array}=\begin{array}{|c|c|}\hline \frac{ 1}{4 } & \frac{ 2}{4 } \\\hline \frac{ 2}{4 } & \frac{ 3}{4 } \\\hline \end{array}$$

For $3x2$ :

$$\begin{array}{|c|c|}\hline \frac{7}{27}&\frac{19}{144}&\frac{5}{8}\\\hline \frac{14}{27}&\frac{7}{24}&\frac{161}{216}\\\hline\end{array}= \begin{array}{|c|c|}\hline \frac{112}{432} & \frac{57}{432} & \frac{270}{432} \\\hline \frac{224}{432} & \frac{126}{432} & \frac{322}{432} \\\hline \end{array}$$

For $4x2$ : $$\begin{array}{|c|c|}\hline \frac{299}{1152}&\frac{4261}{31104}&\frac{1949}{10368}&\frac{41491}{62208}\\\hline \frac{7177}{13824}&\frac{6283}{20736}&\frac{1829}{6912}&\frac{29843}{41472}\\\hline\end{array}= \begin{array}{|c|c|}\hline \frac{32292}{124416} & \frac{17044}{124416} & \frac{23388}{124416} & \frac{82982}{124416} \\\hline \frac{64593}{124416} & \frac{37698}{124416} & \frac{32922}{124416} & \frac{89529}{124416} \\\hline \end{array}$$

For $3x3$ :

$$\begin{array}{|c|c|}\hline \frac{1459}{5400} & \frac{6359}{43200} & \frac{143129}{216000} \\\hline \frac{6359}{43200} & \frac{153293}{972000} & \frac{483341}{1296000} \\\hline \frac{143129}{216000} & \frac{483341}{1296000} & \frac{1217}{1500} \\\hline \end{array}$$

For larger grids, numerators and denominators don't fit in 64 bits integers, and computations become slow. But those results seem to show that there is no obvious answer to your question.

• Would you mind if I can know the details of how you computed these probabilities? Did you just count the number of times a cell is leaf and divide by the total number of trees? The algorithmic details might be a little useful. I really don't care about the programming language it was written in. Thanks! Nov 22, 2013 at 14:33
• I already computed a few but wasn't sure of how to keep track of generated spanning trees without using up too much memory in the computer. That's why the algorithmic details might be useful. Nov 22, 2013 at 14:36
• I used maps over balanced binary trees to keep track of the partial spanning trees and the probability to obtain them (because one spanning tree can be obtained from several different choices path). Once each spanning tree is computed with its probability, I just sum the probabilities of all such trees where one specific node is a leaf to obtain the probability of this node.
– Xoff
Nov 22, 2013 at 14:46
• Consider the grid $3\times 2$ with $$\begin{array}{|c|c|c|}\hline A&B&C\\ \hline D&E&F\\ \hline\end{array}$$ The tree $A-B-C-F-E-D$ can only be obtain from the choice $A-B$ ($p=\frac{1}{2}$ among $(A-B)$, $(A-D)$), then $B-C$ ($p=\frac{1}{3}$ among $(A-D)$, $(B-C)$, $(B-E)$) then $C-F$ ($p=\frac{1}{3}$), then $(F-E)$ $p=\frac{1}{3}$, then $E-D$ $p=\frac{1}{2}$. So the probability of this tree is $\frac{1}{2^2.3^3}$.
– Xoff
Nov 24, 2013 at 13:25
• It must be 1, because at each step, if you have $n$ possible edges, each edges has $p=\frac{1}{n}$. So the sum is always 1 at each step. But you must take into account that some trees can be obtained from different choices order.
– Xoff
Nov 24, 2013 at 13:35

You asked some questions related to the Uniform Spanning Tree model in Statistical Mechanics and Combinatorics. Let's try to address your first question:

What's the probability a given vertex of the grid $(x,y) \in N \times N$ is a leaf in our spanning tree?

First, we need to count all the spanning trees of the $N \times N$ grid. This is in the Online Encyclopedia of Integer Sequences A007341

1, 4, 192, 100352, 557568000, ...


This number grows large very quickly. And we have an exact formula:

$$a_n = \frac{2^{n^2-1} }{n^2} \prod_{m_1, m_2 =1}^{n-1} \left(2 - \cos \frac{\pi m_1}{n} - \cos \frac{\pi m_2}{n}\right) \in \mathbb{Z}$$

One way to check this is an integer is to verify this is invariant under the Galois group of $\mathbb{Q}[\omega]$ with $\omega^n = 1$ is a root of unity.

We can also tell that from the $2^{n^2}$ factor that we need $n^2$ bits in order to uniquely describe our spanning tree.

This formula is disccussed on MathOverflow: https://mathoverflow.net/questions/8497/number-of-spanning-trees-in-a-grid

## Deriving the Product Formula for the Number of Spanning Trees

We can use the Matrix Tree Theorem which states that number of trees of any graph - in our case the $N \times N$ grid - is equal to the determinant of the Laplacian of the grid.

$$\# \{ \text{spanning trees}\} = \det \Delta_G = \frac{1}{n}\lambda_1\dots \lambda_{n-1}$$

In the case of the $\{ 1, 2, \dots n \} \times \{ 1, 2, \dots n \}$ we can write down explicit eigenfunctions so that

$$\lambda \; f(x,y) = \frac{1}{4} \big[ f(x+1,y) + f(x-1,y) + f(x,y+1) + f(x,y-1)\big]$$

The functions we get are $(x,y) \mapsto \exp\left(\frac{\pi m_1 x}{n}\right)\exp\left(\frac{\pi m_2 x}{n}\right)$ with eigenvalues $\lambda = 2 - \cos \frac{\pi m_1}{n} - \cos \frac{\pi m_2}{n}$.

So, the number of spanning trees on the grid has something to do with Harmonic analysis on $\mathbb{Z}_N^2$, random walks and the roots of unity.

• Thanks! But the random spanning tree generated isn't a uniform spanning tree. Intuitively, we see that more trees are likely to have the lower right vertex as a leaf. Nov 29, 2013 at 19:19
• In fact, we can say that the probability that the lower right vertex is a leaf is greater than the probability that the top left vertex is a leaf. If the trees generated were uniform then they would be equal by symetry since we can simply rotate (and/or reflect) every tree which has the lower right as a leaf to form a tree with the top left as a leaf (and vice versa). Nov 29, 2013 at 19:27
• I see. Judging from your link to Quora, you are interested in comparing Prim's algorithm and Kruskal's algorithm on $\mathbb{Z_m} \times \mathbb{Z}_m$. Even if this model isn't the same, the strategy should apply... Nov 29, 2013 at 22:16
• Prim's algorithm in this case may be related to Diffusion Limited Aggregation Nov 29, 2013 at 23:38
• ^ That's interesting. I'll look into that. Thanks! Nov 30, 2013 at 1:43

Not sure if it helps and it's a bit late but for the case of the $N\times N$ grid in the limit of $N\rightarrow \infty$ the following exact result for the leaf-probability has been derived here based on an equivalence to the Abelian sandpile model:

$$\frac{8}{\pi^2}\left( 1 - \frac{2}{\pi}\right) \approx 0.29454$$

• That's for a model where all spanning trees are equiprobable. Here we have an asymmetric process that starts at the top left corner and presumably produces different spanning trees with different probabilities. Apr 20, 2020 at 23:47