I have a question regarding exercise 14.17 in An Introduction to Information Retrieval by Manning et al.

The problem is:

"Assuming two classes, show that the percentage of non-separable assignments of the vertices of a hypercube decreases with dimensionality M for M > 1. For example, for M = 1 the proportion of non-separable assignments is 0, for M = 2, it is 2/16. Solve the exercise either analytically or by simulation."

The total number of assignments of vertices of an N-dimensional hypercube is: $2^{(2^N)}$

And as I found in here the number of separable assignments is O($2^{(N^2)}$). So the percentage of non-separable assignments is increasing with N (which is the opposite of what is said in the exercise).

What am I missing here?

  • $\begingroup$ I agree, this seems incorrect. $\endgroup$ – Ben Reiniger Jun 19 '19 at 21:36

You appear to be correct. I believe this is a simple proof of the opposite fact:

Let $s(n)$ denote the number of separable sets in the $n$-cube. Let $Q_0, Q_1$ denote the subcubes of one smaller dimension, with say last coordinates equal to 0, 1 respectively. The key fact is that any separable set of the whole cube intersects with each of $Q_0, Q_1$ in separable sets. (The separating hyperplane intersects the codimension-1 spaces to form separating hyperplanes.) So $$s(n)\leq [s(n-1)]^2.$$

Now the proportion $r(n)$ satisfies $$r(n)= \frac{s(n)}{2^{2^n}}\leq \frac{[s(n-1)]^2}{(2^{2^{n-1}})^2}= [r(n-1)]^2< r(n-1),$$ where the last inequality holds because $r(n-1)<1$ for $n>2$.

| improve this answer | |
  • $\begingroup$ Thank you for your answer! $\endgroup$ – Mahsa Jun 29 '19 at 21:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.