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

Question

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

Answer 1

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.

Answer 2

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.