Select $K$ random binary vectors $Y\_i$ of length $m$ uniformly at random.


Let the following collection of random variables be defined: $X\_{i,j}=w(Y\_i \oplus Y\_j)$ where $w(\cdot)$ denotes the Hamming weight of a binary vector, i.e., the number of the nonzero coordinates in its argument. Define $D\_{min}(Y\_1,\ldots,Y\_K)$ as the smallest of the $X\_{i,j}$ for $i \neq j.$


Thus we have $n=C(K,2)=K(K-1)/2$ non-independent random variables $X\_{i,j}$ with support {$0,1,\ldots,m$} and individual distribution $Bin(m,1/2)$. It seems to me that the random variables $X\_{i,j}$ will be $s$-wise negatively correlated (for $s$ large enough) if distances between pairs chosen from a subcollection of $Y\_{i\_1},Y\_{i\_2},\ldots,Y\_{i\_v}$ where ($v < K$) tincreases then the distances between $Y\_{i\_j}$ and the remaining vectors will tend to decrease. Take $s=v+1.$


It is possible to get a bound on the following quantity. Fix $w$ an integer less than $m/2.$ The Hamming sphere of radius w has "volume", i.e., contains $V\_w(m)=\sum\_{s=0}^w C(m,s)$ vectors and we approximately have to first order in the exponent
$$
V\_w(m) =2^{m H((w+1)/2)}
$$
where $H(\cdot)$ is the binary entropy function. Then, for a random uniform choice of the $Y\_i$ for $i=1,2,\ldots,K$ it is clear that if the Hamming spheres centred at these vectors are disjoint then the minimum distance is at least $2w+1$ thus 
$Pr[D\_{min} \geq 2 w+1] \leq \frac{(2^m-V)}{2^m}\frac{ (2^m-2 V) }{2^m} \cdots\frac{ (2^m - (K-1)V)}{ 2^{m}}$


where $V=V\_w(m).$ This means that, by replacing each fraction of the form $(1-x)$ by $exp(-x)$ where $x >0$ but small, we get the approximate upper bound
$Pr[ D\_{min} \geq 2w+1] \leq exp\left[-K(K-1)V^2/(2^{m+1} \right]$ which then expresses this upper bound in terms of the entropy function, which is nice. Unfortunately this upper bound is quite loose.


I will be happy with any pointers to literature or any other suggestions.



Minimum Hamming Distance Distribution in a Random Subset of Binary Vectors+
Here is a direct application of Theorem 21 from Gabor Lugosi's [concentration of measure notes](http://www.econ.upf.edu/~lugosi/anu.pdf). Your $Y\_i$ corresponds to his $X\_{i,1}^m$ and your $X\_{i,j}$ to his $d(X\_{i,1}^m, X\_{j,1}^m)$. Take his $A$ to be your $\{X\_{i,j}\}\_{i \neq j}$. The birthday problem gives the probability that any two of the $Y\_i$ are exactly the same. That is:
$$\mathbb{P}(0^m \in A) = \mathbb{P}\left(\left\{X\_{i,j} = 0^m : i \neq j\right\}\right) = \mathrm{(omitted\ for\ simplicity)} $$
Now your $D\_{min}$ corresponds to his $d(0^m,A)$. By the Theorem, for any $t > 0$,
$$\mathbb{P}\left(D\_{min} \geq t + \sqrt{\frac{m}{2} \mathrm{log}\frac{1}{\mathbb{P}(0^m \in A)}}\right) \leq e^{-2t^2/m}.$$
This bound may be OK for your needs. If it isn't, see Lugosi's discussion of Talagrand's convex distance inequality, which is a big improvement.


