Computing the volume of partitions in boolean cubes

What's new

• I included the proof of some observation ( see). The way I used to analyze could be extended to give a characterization of all halfspaces that occur. Let's see what we can do with it ...

--Ed 11:39, 10 เมษายน 2007 (ICT)

ที่มา

จำไม่ได้ละ

ปัญหา

We have the n-dimensional unit cube:

$B=\{x\in \mathbb {R} ^{n}:(\forall i)0\leq x_{i}\leq 1\}$.

The unit cube has $2^{n}$ vertices (corners). For any subset $\mathbb {S} \subseteq \{0,1\}^{n}$ of k vertices, the partitions $\{P_{v}\}_{v\in \mathbb {S} }$ are defined as follows: the partition $P_{v}$ contains all points in the cube closer to v, with respect to $\ell _{2}$-norm, than any other vertices in $\mathbb {S}$.

Question

What is the volume of $P_{v}$'s?

ความคืบ

• Just proved that each partition defines a convex set.
  • hence, we can at worst calculate the volume for each partition in $O(n^{4})$ using simulated annealing MCMC of Vempala and Lovasz. But this straightforward approach is inefficient if $k$ is large because the total run-time will be $O(k*n^{4})$ where $k$ can be as much as $2^{n}$. Actually, we know that if $k=2^{n}$, the volume of each partition will be simply $1/2^{n}$ by symmetry.
    • I don't understand why the running time is $O(k*n^{4})$? Where does k come from? Is it from the complexity of the partition? Or... is it from the fact that you have to compute the volume of every partition? (do you?) But having k in the factor should be fine, right? Because you have to specify k points (for S) anyway. Am I missing something here? -- Jittat 23:30, 28 มีนาคม 2007 (ICT)

• That's true. I am just not satisfied with the way of calculating $O(n^{4})$ for every points; I hope it will be an easier and more intuitive way. Jung 15:06, 30 มีนาคม 2007 (ICT)

• It's even worse than that. That $O(n^{4})$ is the running time given that the oracle runs in constant time. You need another factor of $O(nk)$ for the oracle. --- Jittat 09:54, 31 มีนาคม 2007 (ICT)

• To DO: The structure of this problem might allow a better, simpler algorithm. There are a lot of orthogonal hyperplanes.

ไอเดียอื่นๆ #1

reduce the problem to other cube in smaller dimensions. hypercube embedding? -- to be continued ...

ไอเดียอื่นๆ #2

• Starting from the case $k=2^{n}$ (every point is a reference point). This case divides the volume up equally to ${\frac {1}{2^{n}}}$ for each partition. The idea is, for each $v\not \in \mathbb {S}$, assign the volume that v would have had (that is, 2^n) if it were to be in $\mathbb {S}$ to its closest vertices in $\mathbb {S}$ (we deal with ties by dividing the volume equally). The problem is how well this method approximate the volume? , or in more extreme, is this method exact??

• Very interesting. Intuitively, it should give an exact answer. But the way you're dividing volume might not work. Here's some argument. Here I assume that |S|>1. First of all, for very point v in S, $vol(P_{v})\geq 1/2^{n}$, i.e., it always takes its little cube. Now think of the way you're dividing little cubes associated with points not in S. Think of the case of 5 dimensions. Let's point u=(1,1,1,1,1), and it is not in S. The closes points to u in S are a=(0,0,1,1,1), b=(0,1,0,1,1), and c=(1,1,1,0,0). Now, note that a and b are closer to each other than to c. I guess that in this case, the volume of u should go to c more than to a or b. (I haven't proved it though.)

• Ok; there is a very simple example in the 3-dimensional unit cube which shows that the method is not exact. Let S = {(0,0,0), (1,1,1)}. Let u = (0,0,1) so that u is closer to (0,0,0) than (1,1,1). However, the partition of u is structured as alittle cube which has one corner at (1/2, 1/2, 1). This point, including some points nearby (which totally have non-zero measure), is closer to (1,1,1) more than (0,0,0). Hence, some volume of u will go to (1,1,1).

I make a simple experiment by generating points randomly within the partition of u; about 83% of the volume of u goes to (0,0,0), and the rest goes to (1,1,1). To me, it's interesting if I can explain/derive a formula for this 0.83:0.17 ratio -- Jung 15:41, 30 มีนาคม 2007 (ICT)

• Maybe a better way to distribute the volume might be to look at the subspace spanned by points in S closest to u, and compute the volumes of each partition (recursively).

• Can you explain in more details?? -- Jung 17:25, 30 มีนาคม 2007 (ICT)

• Anyway, this technique suffers from the fact that maybe the number of points not in S is exponential. --- Jittat 16:10, 29 มีนาคม 2007 (ICT)

• BTW, Ed is currently trying to prove whether this is going to be #P-hard or not (below) Jung 16:59, 30 มีนาคม 2007 (ICT)

• How about this vague idea? Consider point u in S. Find set C of closest points to u in S. (Should take $O(nk)$ time for each u.) I think that the distance from u to C should say something. Furthermore, we might be able look at how u and points in C share the volume (of something?) by considering some subspace. (There, we recurse. I guess that we won't suffer from the exponential blows up because, it seems that, we have only one subproblem.) --- Jittat 17:18, 29 มีนาคม 2007 (ICT)

Alright. This is broken. You can't find the volume with only closest points. --Jittat 22:56, 29 มีนาคม 2007 (ICT)

• Since we are trying to make things discrete, one thing to ask is whether the volume of each $P_{v}$ discrete? and how large the range is? If yes, we may hope to compute the exact volume.

• Another thing to look at is what is the complexity of this problem?. It looks like a #P-hard problem but may not be .... This problem is very similar to the following (which is known to be #P-hard): Given a hyperplane H, count the number of points in $\{0,1\}^{n}$ which lies on one side of the hyperplane H. In other word, count the number of x such that $h\cdot x\leq b$. This could be thought of as counting the number of solutions for 0-1 Knapsack problem where h is weight, b is the size of knapsack, and x is the solution. Counting the solutions for NP-complete problem is #P-hard. This problem is different in that we are not given a hyperplane but instead points on hypercubes, and as far as I tried, no obvious reduction from Knapsack would work.

Some more notes

1. Let's see some simple calculation. (Maybe we'll have some idea from it) There are at most $2^{n}$ points. But actually, there are only $n+1$ possible values for distances: $0^{1/n},1^{1/n},2^{1/n},...,n^{1/n}$. For a given point p, there are ${n \choose i}$ points of distance $i^{1/n}$.

2. Let's take $v=(0,0,0,0,...,0)$. Consider set $S\subseteq \{0,1\}^{n}-\{(0,0,...,0)\}$, and let $p_{v}$ denote a region in the cube which are closer to $v$ than other points in $S$.

Let $v'$ be another point not equal to v and not in S. A question is: is it true that there always some point in $p_{v}$ which are closer to $v'$ than to v?

The answer is no. E.g., v = (0,0), S = {(1,0),(0,1)} and v' = (1,1). But if S = {(1,0)}, some point in $p_{v}$ are closer to $v'$ than to v.

This question actually asks how we could say that $v'$ is out of the question, i.e. $v'$ is irrelevant to the answer.

• Please see my special case (3) below which should give some hints to this question -- Jung 03:03, 9 เมษายน 2007 (ICT)

Interesting special cases (which we know exact answers)

Let $n$ be the dimension of the unit hypercube. From all above discussions, I conclude that we know exact answers for just three cases (all are trivial): when $|S|\in \{1,2,2^{n}\}$

Here are three more special cases which the first two we know the exact answers, and the last one I think we also know the exact answer (I found good evidences empirically). The last case also provides some hints to P'Manow question above.

1. The case that $S$ can be reduced completely to a lower dimensional hypercube which we already know the exact answer.
2. The case that $S$ defines a perfect symmetry set.
3. The case that $|S|=2^{n}-1$.

These three cases will be described in turn in the following subsections.

(2) a perfect symmetry set

Consider a set $S$ with $m$ elements, i.e. $S=\{v_{1},...,v_{m}\}$. For each $j=1,...,m$ define $D_{j}=\{||v_{j}-v_{k}||$, for each $k\in S,k\neq j\}$, i.e. a set of distances from vertex $j$ to others.

I say that $S$ is a perfect symmetry set if all $D_{j}$ are identical, for all $j=1,...,m$. The volume of the hypercube then is divided equally of size $1/m$ to each vertex's partition.

Example: $S=\{(0,0,0,0,0,0,0,0),(0,0,0,0,1,1,1,1),(1,1,1,1,0,0,0,0),(1,1,1,1,1,1,1,1)\}$ is a perfect symmetry set.

(3) $|S|=2^{n}-1$

WLOG, suppose $v=(0,0,...,0)\not \in S$. I found empirically that the heuristic above (idea#2) is exact. More precisely, let $N(v)=\{w\in \{0,1\}^{n}s.t.||w-v||=1\}$ be the neighbor of $v$ (note that in our case, $N(v)\subset S$). Then, all the mass of $v$ will be divided to all elements in $N(v)$ equally; moreover, none of the mass of $v$ is assigned to non-neighbor of $v$.

This also has one more implication related to the above question of P'Manow: if $S$ contains all neighbors of $v$, i.e. $N(v)\subset S$, then no such $v'$ exists (see P'Manow notations above).

I will work mathematically on this observation. My intuition is: the condition of $N(v)\subset S$ is both necessary and sufficient to non-existence of $v'$.

see proof

อ้างอิง

Hardness proof for computing volume of convex body in general

Vempala and Lovasz