Lower bound on probability of getting two close points in a sample of $n$ points Let $D\subseteq \mathbb{R}^k$. Assume that $Pr_{u,v\leftarrow U_D}[|u-v| &lt;B]&gt;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|&lt;B]$. The bound can depend on the $k$, which should be thought of as a small constant, i.e., $k&lt;&lt;|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$.
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&gt;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$.)