Minimum Hamming Distance Distribution in a Random Subset of Binary Vectors+ - MathOverflow

Minimum Hamming Distance Distribution in a Random Subset of Binary Vectors+

2010-02-25T03:45:01Z

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.

Answer by Shiva Kaul for Minimum Hamming Distance Distribution in a Random Subset of Binary Vectors+

2010-03-03T04:33:15Z

Here is a direct application of Theorem 21 from Gabor Lugosi's concentration of measure notes. 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.

Answer by serdar for Minimum Hamming Distance Distribution in a Random Subset of Binary Vectors+

2010-03-07T12:59:54Z

@ unknown (google): In response to your comment I am interested in both. The asymptotic results I am aware of usually focus on linear codes, but in my case the codewords are chosen by an adversary, at random, from the uniform distribution. Please feel free to point to the results you're aware of.

@ Shiva Kaul: Thanks, I will look up Lugosi's notes.

Answer by Michel Schellekens for Minimum Hamming Distance Distribution in a Random Subset of Binary Vectors+

2010-05-11T15:28:14Z

Hi, does anyone have info on the average hamming distance of random binary numbers of fixed length?

Michel Schellekens