Minimum Hamming Distance Distribution in a Random Subset of Binary Vectors+ - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T00:26:11Z http://mathoverflow.net/feeds/question/16359 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/16359/minimum-hamming-distance-distribution-in-a-random-subset-of-binary-vectors Minimum Hamming Distance Distribution in a Random Subset of Binary Vectors+ serdar 2010-02-25T03:45:01Z 2010-05-11T15:28:14Z <p>Select $K$ random binary vectors $Y_i$ of length $m$ uniformly at random.</p> <p>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.$</p> <p>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 &lt; K$) tincreases then the distances between $Y_{i_j}$ and the remaining vectors will tend to decrease. Take $s=v+1.$</p> <p>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}}$</p> <p>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.</p> <p>I will be happy with any pointers to literature or any other suggestions.</p> http://mathoverflow.net/questions/16359/minimum-hamming-distance-distribution-in-a-random-subset-of-binary-vectors/16955#16955 Answer by Shiva Kaul for Minimum Hamming Distance Distribution in a Random Subset of Binary Vectors+ Shiva Kaul 2010-03-03T04:33:15Z 2010-03-03T04:33:15Z <p>Here is a direct application of Theorem 21 from Gabor Lugosi's <a href="http://www.econ.upf.edu/~lugosi/anu.pdf" rel="nofollow">concentration of measure notes</a>. 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.</p> http://mathoverflow.net/questions/16359/minimum-hamming-distance-distribution-in-a-random-subset-of-binary-vectors/17375#17375 Answer by serdar for Minimum Hamming Distance Distribution in a Random Subset of Binary Vectors+ serdar 2010-03-07T12:59:54Z 2010-03-07T12:59:54Z <p>@ 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.</p> <p>@ Shiva Kaul: Thanks, I will look up Lugosi's notes.</p> http://mathoverflow.net/questions/16359/minimum-hamming-distance-distribution-in-a-random-subset-of-binary-vectors/24252#24252 Answer by Michel Schellekens for Minimum Hamming Distance Distribution in a Random Subset of Binary Vectors+ Michel Schellekens 2010-05-11T15:28:14Z 2010-05-11T15:28:14Z <p>Hi, does anyone have info on the <strong>average</strong> hamming distance of random binary numbers of fixed length? </p> <p>Michel Schellekens</p>