Re: minimum Hamming distance among random bit vectors

From: Keith A. Lewis (lewis_at_spyder.mitre.org)
Date: 04/29/04 

Date: Thu, 29 Apr 2004 19:13:41 +0000 (UTC)

Francois Grieu <fgrieu@francenet.fr> writes in article <fgrieu-73C601.10142129042004@news.fu-berlin.de> dated Thu, 29 Apr 2004 10:14:21 +0200:
>Let p(b,n,d) be the probability that among a set of
>n ramdom vectors of b bits, there exists two distinct
>vectors which differ by at most d bits out of b.
>
>We restrict to integers such that b>0, n>0, 0<=d<=b
>
>
>Except for typo, we have:
>
>[1] p(b,1,d) = 0
>
>[2] p(b,2,d) = sum C(b,j)/2^b with C(i,j) = i! / j! / (i-j)!
> j=0..d
>
>[3] p(b,2^b,d) = 1
>
>[4] p(b,n+1,d) > p(b,n,d) or p(b,n+1,d) = p(b,n,d) = 1
>(in other words: p grows with n, then becomes stationary with p=1)
>
>assuming n<=2^b
>[5] p(b,n,0) = 1 - prod (1 - j/2^b)
> j=0..n-1
>
>assuming n>1
>[6] p(b,n,b) = 1
>
>assuming n>1
>[7] p(b,n,d+1) > p(b,n,d) or p(b,n,d+1) = p(b,n,d) = 1
>(in other words: p grows with d, then becomes stationary with p=1)
>
>
>So far I fail to find a workable technique to exactly compute
>p(n,b,d) in the general case. I wonder if in the domain
>2 <= n <= 2^(b/3) a valid approximation could be:
>[8] p(b,n,d) =~ 1 - (1 - p(b,2,d))^(n(n-1)/2)
>
>I also fail to characterise
> N(b,d) = min(n such that p(b,n,d)=1)
> D(b,n) = min(d such that p(b,n,d)=1)
>(in other word: when it is impossible to find n vectors which
>all differ by at least d bits)

If d is even, each bit vector "occupies" a space within d/2 of the bit
vector. That's sum( b!/j!/(b-j)! )
               j=0..d/2

So N(b,d) is at most 2^b / the above sum.

--Keith Lewis klewis {at} mitre.org
The above may not (yet) represent the opinions of my employer.