minimum Hamming distance among random bit vectors

From: Francois Grieu (fgrieu_at_francenet.fr)
Date: 04/29/04 

Date: 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)

Any idea or reference ?

  François Grieu

Note: Followup-To is set to sci.crypt

Relevant Pages

  • Re: minimum Hamming distance among random bit vectors
    ... > Let pbe the probability that among a set of ... > n ramdom vectors of b bits, ... > vectors which differ by at most d bits out of b. ... > So far I fail to find a workable technique to exactly compute ...
    (sci.crypt)
  • Re: minimum Hamming distance among random bit vectors
    ... >n ramdom vectors of b bits, ... >vectors which differ by at most d bits out of b. ... >So far I fail to find a workable technique to exactly compute ... So Nis at most 2^b / the above sum. ...
    (sci.crypt)
  • Re: Please help me to find a mistake here
    ... probability of event E equal to about 1.76E-10. ... slightly different from James Waldby's answer. ... thought the answers should differ by only an imperceptible amount. ... Using this second method I get Pr= 1.7611E-10, ...
    (sci.math)
  • Re: SHA1 broken
    ... >> probability of occuring above a given threshold. ... When the diff occurs only a limited subset of keys are possible. ... for all p then the attack can't work. ...
    (sci.crypt)
  • Re: MLOC with style
    ... Mark Foster wrote: ... that's where we have to differ. ... I fail to see how that can ... taking proper care at all times? ...
    (uk.rec.driving)