pr.probability - 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. 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} cdotsfrac{ (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 expleft[-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.

• Next co.combinatorics - Finding a chromatic polynomial by polynomial fitting
• Previous gt.geometric topology - A problem/conjecture related to 4-manifolds that deserves a name. What name does it deserve?