3 fixed typo in probability bound; added 3 characters in body; edited title

# Minimum Hamming Distance Distribution in a Random Subset of Binary VectorsVectors+

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$ 2w+1$thus$Pr[ D_{min} > 2w-1Pr[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} > 2w-1\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. 2 added upper bound 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 exponentV_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$thus$Pr[ D_{min} > 2w-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} > 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. 1 # Minimum Hamming Distance Distribution in a Random Subset of Binary Vectors 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. 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 negatively correlated, 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.

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