3
$\begingroup$

Let $D\subseteq \mathbb{R}^k$. Assume that $Pr_{u,v\leftarrow U_D}[|u-v| <B]>p$ for some $B,p$, where $|u-v|$ is the L1 distance of the vectors.

$S\subseteq D$ is obtained by sampling $n$ elements uniformly from $D$. Give a lower bound, as tight as possible, on $P\equiv Pr_{S\leftarrow U_D}[\exists u,v\in S:|u-v|<B]$. The bound can depend on the $k$, which should be thought of as a small constant, i.e., $k<<|D|$.

Specifically, the bound has to be tighter than the following trivial one: $P\ge 1-(1-p)^{n/2}$. This is obtained by dividing the $n$ points to $n/2$ pairs that are sampled independently. Then, $1-P$, the probability that $\forall u,v\in S:|u-v|\ge B$, is at least as low as the probability that none of these pairs will have distance lower than $B$. Since these events are independent, we get $1-P\le (1-p)^{n/2}\Rightarrow P\ge 1-(1-p)^{n/2}$.

Intuitively, since $S$ has $\frac{n^2}{2}=O(n^2)$ pairs of points, each corresponding with a possible "closeness" event, we would expect to get something like $P\ge 1-(1-p)^{O(n^2)}$, following a similar calculation to the above. However, without event independence this not easy to show (and possibly not true).

We are thus looking for a bound $C$ s.t. $P\ge C, C=1-(1-p)^{\omega (n)}$. Or to show that it does not exist. $C$ can be a function of the constant $k$.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Given that you want your bound independent of $k$, this should be equivalent to asking about the probability that a random vertex set in a graph is an independent set. (That is an interesting question, probably already studied?) $\endgroup$ – daniello May 1 '17 at 20:34
  • 1
    $\begingroup$ Well, it is not equivalent, but rather a specific case of independent set testing. Unfortunately, in the general case of independent set testing, the above trivial bound is actually tight: Assume $N$ vertice graph. Assume all the edges in the graph are connected to $pN$ specific vertices, each of which connected to all vertices in the graph. This satisfies probability $p$ of hitting an edge randomly (since there are $pN^2$ edges). However, probability of "hitting" an edge in sampling $n$ vertices is the probability that we hit one of the $pN$ vertices, $(1-p)^n$ (assuming $N>>n$). $\endgroup$ – Roei Schus May 1 '17 at 21:22
  • $\begingroup$ And oh, the bound does not have to be independent of $k$. I edited to clarify, thank you. $\endgroup$ – Roei Schus May 1 '17 at 21:27
  • $\begingroup$ When $k$ can depend on $n$ one can for any graph $G$ make a point set such that points correspond to vertices and two points are close iff the corresponding vertices are adjacent. The bound on $k$ makes things more interesting. $\endgroup$ – daniello May 1 '17 at 21:38
  • 1
    $\begingroup$ I hope we can assume that $D$ is a finite point set and that $S$ is sampled with repetition? This seems to make the math easier. $\endgroup$ – daniello May 2 '17 at 6:08
3
$\begingroup$

Here's a counter-example showing your desired bound is not possible, unless I am mistaken. It's a simple variant of the example in Roei's comment.

Fix any $n$ and $N\ge 4n$. Take $D$ to contain $N/2$ points that are all the same (or all within distance 1 from each other), and $N/2$ points that are all widely separated (at distance at least 1 from every other point in $D$). This can be done even with $D\subset\mathbb{R}^1$.

The probability that two uniformly random points in $D$ are within distance 1 from each other is $1/4$. In your notation, $p=1/4$ for $B=1$.

The probability that $n$ uniformly random points in $D$ don't contain some pair within distance 1 from each other is (at least) the probability that all $n$ points are in the widely separated set and distinct, which is at least $[(N/2-n)/N]^n \ge 1/4^n$.

So, in your notation $1-P \ge 1/4^n \ge (3/4)^{5n} = (1-p)^{5n}$.

So, $P \le 1 - (1-p)^{5n}$. So your desired upper bound $P \ge 1-(1-p)^{\omega(n)}$ does not hold.

(If you generalize the example above for arbitrary (small) $p>0$, I think you get something like $P \le 1- (1-\sqrt p)^n \approx 1-(1-p)^{n/\sqrt p}$, which is not a counterexample if $p\rightarrow 0$ as $n\rightarrow \infty$.)

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Nice, Neal! This definitely sheds some light on the problem. However, I am definitely looking for a solution that does not set $p$. Specifically, the bound $P\ge 1-(1-\sqrt{p})^n$ would be amazing. In fact, what is interesting in practice is the relationship between $p$ and $n$ that is required, or how large should $n$ be for a given $p$ to ensure a "closeness" event. So really, $P\ge 1-(1-\sqrt{p})^n$ is actually practically equivalent to $P\ge 1-(1-p)^{n^2}$. $\endgroup$ – Roei Schus May 2 '17 at 18:05
  • $\begingroup$ One generalization of the above example would be to take some $N$ points, partition them, and make each part a clique (within $1$ of each other). Analyzing such an example is similar, but maybe a little more subtle (?), than analyzing the birthday paradox with non-uniform birthday probabilities. For the latter problem I guess it's known that the uniform distribution maximizes the number of people you can have before you're likely to have two with the same birthday. $\endgroup$ – Neal Young May 4 '17 at 5:31
  • $\begingroup$ You're absolutely right. If we're talking about a graph of cliques, the problem becomes exactly equivalent to the birthday paradox. Clique implies transitivity of "closeness" events, which means we can treat the cliques as buckets like in the paradox. And indeed, for the birthday case, a lower bound exists (and it is exactly the one I would expect). To get a collision, you will need $O(\frac{1}{\sqrt{p}})$ samples. This is why your example is not a counter-example for the bound's existence... $\endgroup$ – Roei Schus May 4 '17 at 16:58
  • $\begingroup$ What's the lower bound you mention? If you define $q_i$ to be the size of the $i$th clique, normalized so $\sum_i q_i = 1$, then your $p$ is $\sum_i q_i^2$. How do you bound your $1-P$ (probability of no collision in $n$ draws from the distribution $q$) in terms of this $p$? $\endgroup$ – Neal Young May 5 '17 at 0:26
  • $\begingroup$ I was implicitly assuming the result you mentioned, that in the birthday setting, the uniform distribution is "worst case" (minimizes probability of collision in a set). I guess it is not trivial to show. But building on this known result, we get that the bound for the uniform case, $1-P\le 1-e^{\frac{-n^2}{2\frac{1}{p}}}$, also bounds the non-uniform case $\endgroup$ – Roei Schus May 5 '17 at 18:14

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.