The expectation of partition times needed separate two elements in a set

Question

I met a problem which can be formulated as set partition.

Given a set $S=\{s_1,s_2,...,s_n\}$ having $n$ elements, I want to separate two elements, say $s_1,s_2$, in $S$ by repeatedly using set partition operations. Each set partition operation randomly partitions the very subset containing $s_1,s_2$, say $A$, into two non-empty subsets, $B$ and $C$, such that $A=B\cup C$ and $B\cap C=\emptyset$. The randomness of partition means that, $B$ and $C$ are random.

I want to calculate or approximate the expectation of partition time, $E(n)$, to separate $s_1$ and $s_2$.

Let see two simple cases when $n$ is small.

(1) $n=2$:

In this case, $S=\{s_1,s_2\}$. The only feasible partition will separate $S=\{s_1,s_2\}$ as $\{s_1\}$ and $\{s_2\}$. So, $E(2) = 1$.

(2) $n=3$:

In this case, $S=\{s_1,s_2,s_3\}$. There are two possible situations when performing the first partition:

(a) if the first partition is $\{s_1\},\{s_2,s_3\}$ or $\{s_2\},\{s_1,s_3\}$, then 1 partition is ok!

(b) if the first partition is $\{s_1,s_2\},\{s_3\}$, then I need a second partition making $\{s_1,s_2\}$ into $\{s_1\},\{s_2\}$. So the partition time is 2.

The possibility of situation (a) is 2/3 and situation (b) 1/3 due to the randomness. So, $E(3)=1*(2/3)+2*(1/3)=4/3$.

I tried using recursive formula but it seems to be a non-closed form. I also wonder whether or not $E(n)$ can be approximated by some other continuous functions?

Answer 1

First answer

It’s very close to 2, but it’s a little less.

Consider the following closely related process (which isn’t the same).

Easier process: at each step, take the set containing $\{s_1, s_2\}$, and randomly divide it into two sets with all such divisions being equally likey (perhaps one of which is empty). Keep going until the elements are separated.

If we do easier process, then each time we do it, the chance that it ends as a result of the next step is exactly $1/2$ (independent of set size), and it’s a geometric process with probability $1/2$. So ‘easier process’ lasts an expected 2 steps exactly.

Your process is the same as the easier process, but if easier process ever does a trivial cut (where nothing happens) then you don’t consider that a step. So we can just do easier process and then ignore every step that did nothing.

With this coupling, we see your process ends sooner than the easier one, so your expected value is at most 2.

And if $n$ is large, these processes are very close, so 2 will be a very good approximation. If you’re happy saying the expected value is between 1 and 2, then this does it. If you want to argue the expected value is in fact very close to 2, we’d have to think just a little bit more. Let me know if this works for you.

---

More exact answer

Let $E(n)$ denote the expectation you care about. Then we have the recurrence $E(2) = 1$ and for all $n > 2$,

$$ E(n) = 1 + \dfrac{1}{2^{n-1} -1} \sum_{k=2} ^{n-1} {{n-2} \choose {k-2}} E(k), $$

which follows since ${{n-2} \choose {k-2}} / (2^{n-1} -1)$ is the probability that after the first split, $s_1$ and $s_2$ are still together, and they are in a set of cardinality $k$. From this, you might be able to find a generating function for $E(n)$ if you really wanted to.

But from this recurrence, it's not difficult to prove by induction that $2 - \frac{2}{n} \leq E(n) \leq 2 - (2^{n-1}-1)^{-1}$ for all $n \geq 2$. The base case ($n=2$) is clear. For the induction step we use

$$ 1 + \dfrac{1}{2^{n-1} -1} \sum_{k=2} ^{n-1} {{n-2} \choose {k-2}} \left(2 - \dfrac{A}{k} \right) = 2 - \dfrac{A}{n} + \dfrac{1}{2^{n-1} -1} - \dfrac{A}{n^2 - n}. $$

By induction, using the above with $A=2$ gives a lower bound on $E(n)$ [which happens to be greater than $2 - 2/n$ for all $n$], and setting $A=0$ gives an upper bound on $E(n)$ of $2 - (2^{n-1} -1)^{-1}$.