11
$\begingroup$

Consider an integer cube of size $\sqrt{k} \times \sqrt{k} \times \sqrt{k}$, where $k$ is an asymptotically large perfect square number. Place k points in this cube at uniformly random locations, i.e., for each point choose its co-ordinates uniformly at random $(r_0,r_1,r_2)$ where $ 0 \leq r_i < \sqrt{k}$.

For an arbitrarily small number $\alpha >0$. Let $E$ be an event that there exists a subset of points of size $S = \alpha k$ such that the projection of these S points on every face of the cube, is of size at most $S/2$.

What is an upper bound on the probability of event $E$, i.e., P(E)?

Caution: If you start with a fixed set of size $S$, you would need to consider all possible subsets of $k$ points of size $S$. The event $E$ is defined as there exists a subset of size $S$ in $k$ points which are randomly placed.

Improve this question
$\endgroup$
2
  • $\begingroup$ You are fixing $\alpha$ and then you let $k$ go to infinity? $\endgroup$
    – Douglas Zare
    Commented May 1, 2013 at 4:58
  • $\begingroup$ yes. First fix $\alpha >0$ to be a small constant and then let $k$ go to $\infty$. $\endgroup$
    – codingTheorist
    Commented May 1, 2013 at 19:06

1 Answer 1

Reset to default
1
$\begingroup$

You're essentially asking if you drop $k$ objects each into one of $k$ bins, what is the probability that only $k/2$ bins are occupied. (You can forget the extra dimension and only think about the dimensions you're looking at).

If you let $E_i$ be the event that the $i$th bin is empty, this has probability $((k-1)/k)^k\approx 1/e$. The events $E_i$ are approximately independent. Letting $N=\sum_{i=1}^k \mathbf 1_{E_i}$, $N$ has expectation $k/e$. The probability that there are $k/2$ unoccupied bins will decay as $e^{-\alpha k}$ using large deviation estimates.

--- Added to answer ---

If you want to pick a subset of size $\alpha k$ of the set of size $k$, it's obvious how to do it: take the boxes with the most elements first. You expect the distribution of elements in each box to be approximately Poisson with parameter 1. This means that approximately $(1-2/e)k$ of the boxes have two or more elements. As long as $\alpha$ is less than $1-2/e$, there's a high probability that you can find a subset $S$ of size $\alpha k$ whose shadow has size at most $|S|/2$.

Improve this answer
$\endgroup$
10
  • 1
    $\begingroup$ It seems that you have computed an upper bound on the probability of a set of size $S = k$ occupying less than $S/2$ bins on one face of the cube. I am interested when there exists a subset (of size $\alpha k$) of the original set of $k$ points, such that they occupy less than or equal to $S/2$ bins on each face of the cube. Note, that there are exponential number of such subsets, i.e., $k \choose \alpha k$. $\endgroup$
    – codingTheorist
    Commented May 1, 2013 at 1:05
  • $\begingroup$ The events may be approximately pairwise independent, while not being close to $k/2$-fold independent. $\endgroup$
    – Douglas Zare
    Commented May 1, 2013 at 1:07
  • $\begingroup$ I don't think they don't need to be $k$-fold independent for this kind of argument to work. $\endgroup$
    – Anthony Quas
    Commented May 1, 2013 at 2:13
  • 2
    $\begingroup$ Ok, I believe the conclusion, I just don't see what level of independence exists which implies it. It's also unclear to me how knowing that some subset $S$ projects to have size $|S|/2$ in one direction implies that there is some set which has small projections in all three directions. I'm only getting $\frac{2}{3}|S|$ from something like that. $\endgroup$
    – Douglas Zare
    Commented May 1, 2013 at 5:05
  • 2
    $\begingroup$ Although this probability does decay exponentially in $k$ (as long as the large deviation methods are valid, which I'm sure they are), the exponential decay is slower than the increase in the number of choices of subsets. This means that something more subtle is needed to finish off the argument. BTW: Even the 2D version of this problem seems non-trivial... $\endgroup$
    – Anthony Quas
    Commented May 3, 2013 at 0:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .