Random (Union Find) Spanning Tree, probability of resulting with two unconnected halves before the last step?

Question

Let N be a large even positive integer.

We start with a set of singletons from {1}, {2} ... to {N}. In each step we randomly pick two integers and merge the sets that contain them. We continue until only one set with all numbers 1 ... N remains. What is the probability that we'll be left with two sets of equal size before the last step?

I am thinking (assuming we skip steps that don't affect the structure which obviously affects this result) that it is like choosing edges in a graph such that no edges between two even group of vertices are picked. So we get something along the lines of:

Choose(N/2, N) * Choose(N/2 - 1, (N/2) ^ 2)^2 / Chose(N - 1, N^2)...

Is this about right?

Answer 1

Number of ways to break the set $\{1,2,\dots ,n\}$ into singletons (exactly the reverse process of what is asked) is $$a_n=\prod_{k=2}^{n}\binom{k}{2}=\frac{n!(n-1)!}{2^{n-1}}$$ corresponds with this sequence (as David Callan's comment on the page suggests)

This comes from the recursion: $a_n=\binom{n}{2}a_{n-1}$ and assuming $a_1=1$

In the first step, we choose a pair of singletons and merge them. From second step onwards, the pair may be thought as a one entity as they are not going to be separated ever. This leaves us with $n-1$ objects to operate with.

If $n$ is even, the required probability is $$\frac{\frac{1}{2}\binom{n}{\frac{n}{2}}\left( a_{\frac{n}{2}} \right)^2 \binom{n-2}{\frac{n}{2}-1}}{a_n}$$

The factor of $\binom{n-2}{\frac{n}{2}-1}$ is present to count the all orderings between two $\frac{n}{2}$ sized 'build ups'.

Answer 2

The event is that we start with $n$ singleton set and end up constructing two sets having $n/2$ elements each. To compute the probability of this event the first step is to find the number of ways in which we can do this.

Now, the final two sets can be formed by choosing $n/2$ elements and putting them into a set and putting the remaining elements into the other set. The number of such combinations is $n \choose n/2$. Now, fix one such combination. What is the number of ways by which we can get to these two sets configuration? Note that there will be exactly $n-2$ steps after which the number of sets at our hand is 2. The answer to the previous question is same as the number of ways you can get to the singleton sets starting with those two sets, traversing $n-2$ steps in reverse direction.

Let, $T(k)$ be the number of ways in which one can start with $k$ elements set and get to the singleton sets (it takes $k-1$ steps).

Then note that the number of ways in which two sets of size $n/2$ each can be found (after $n-2$ steps) is $$ {n \choose n/2} T(n/2)T(n/2)={n \choose n/2} {T(n/2)}^2$$

Now, how to find the value of T(k) ($k$ is even)? We'll form a recurrence relation. Note that if we start with $k$ elements set we can choose $i$ elements and split the set into two sets of size $i$ and $k-i$, $1 \leq i \leq k/2$. Then we do the same thing recursively until we get all singleton sets. We can choose $i$ elements in $k \choose i$ ways and the number of ways the $i$ and $k-i$ elements sets can be split is $T(i)*T(k-i)$. Thus, $$T(k) = {k \choose 1}T(1)T(k-1)+{k \choose 2}T(2)T(k-2)+\ldots+{k \choose 2}T(k/2)T(k/2)\\=\sum_{i=1}^{k/2} {k \choose i}T(i)T(k-i)$$

Unfortunately I don't have much idea how to solve this recurrence, but I think one can try the substitution technique.

Now, note that the total number of two sets configuration is $$\sum_{i=1}^{n/2}{n \choose i}T(i)T(n-i)$$ and thus the final probability is $$\frac{{n \choose n/2} {T(n/2)}^2}{\sum_{i=1}^{n/2}{n \choose i}T(i)T(n-i)}$$