I have the following problem: I am working on the hypercube $C_K=[0;1]^K$, and I consider a point $\vec{x}=(x_1,\ldots,x_K)$ in it.

I now consider the subset $\Omega_{K,M}(\vec{x})$ of $C_K$ of points that have at least $M$ coordinates larger than $\vec{x}$ after a 1 to 1 comparison, i.e.:

$$\vec{y}\in \Omega_{K,M}(\vec{x}) \iff \exists (i_1,\ldots,i_M)\subset \{1,\ldots,K \}, \left\{\begin{matrix}y_{i_1}>x_{i_1}\\ \vdots \\ y_{i_M} > x_{i_M} \end{matrix}\right. $$

And I call $V_{K,M}(\vec{x})= \vert \Omega_{K,M}(\vec{x}) \vert $ the volume of that set. For instance, when $M=K$ I get that $V_{K,M}(\vec{x})=\prod_{i=1}^K (1-x_i)$. For $M<K$ the difficulty in the problem is that the actual volume is the sum of the volumes of lots of hyper-rectangles, each one corresponding to a different permutation of coordinates larger than those of $\vec{x}$.

The question I have is the following, given the hypercube dimension, $K$, how do I determine the lowest number $M$ such that the volume decreases in the following sense:

$\forall \vec{x}\in [0;1]^K, \vec{y}\in\Omega_{K,M}(\vec{x})\Rightarrow V_{K,M}(\vec{y})\leq V_{K,M}(\vec{x}) $.

Intuitively, I'd expect that $M>\frac{K}{2}$ should suffice.

I did numerical simulations to test this, for dimensions $K$ up to $20$, but I have found that finding the exact minimal value of $M$ isn't that simple.

Is there anything that could help me work this out ?

Thanks in advance.

  • $\begingroup$ For fixed $\vec{x}$ and $0 \le M \le M' \le K$, isn't it the case $\Omega_{K,M'}(\vec{x}) \subseteq \Omega_{K,M}(\vec{x})$ ? $\endgroup$ – hardmath Oct 23 '17 at 23:56

Your Answer

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

Browse other questions tagged or ask your own question.