Skip to main content
edited tags
Link
Andrés E. Caicedo
  • 32.5k
  • 5
  • 133
  • 240
clarification
Source Link

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 a setthe 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 the, $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?

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 a set, say $A$, into two non-empty subsets, $B$ and $C$, such that $A=B\cup C$ and $B\cap C=\emptyset$. 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:

(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 situations:

(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. So the $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?

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?

Source Link

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

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 a set, say $A$, into two non-empty subsets, $B$ and $C$, such that $A=B\cup C$ and $B\cap C=\emptyset$. 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:

(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 situations:

(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. So the $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?