Re: minimum Hamming distance among random bit vectors

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

Date: Thu, 29 Apr 2004 22:34:02 +0200

In article <vm6kc.13304$os1.11938@newssvr31.news.prodigy.com>,
 Mike Amling wrote:

> How can there be a nonzero probability of "two distinct vectors which
> differ by at most" 0 bits?

Problem comes from my misuse of "set" instead of "array" of vectors,
and of "distinct vectors" to refer to vectors in distinct entries.

Formally:

With Xij denoting random unbiased independent bits,
p(b,n,d) is the probability that there exists indexes r s
such that 0<=r<n, 0<=s<n, r!=s, d >= sum (Xrj xor Xsj)
                                       j=0..b-1

Or more simply:

p(b,n,d) is the probability that among n random vectors
of b bits, there are two which differ by at most d bits.

> > I also fail to characterise
> > N(b,d) = min(n such that p(b,n,d)=1)
>
> Of course N(b,d) <= (2^b)/v(b,d)+1,
> where v(b,d) is the sum for k=0 through d of C(b,k).

Maybe, but I fail to see why. I'm stuck at the bound
suggested by Keith Lewis, which assigns a "ball" of
radius floor(d/2) to each of the n vectors, giving
   N(b,d) <= 2^b / v(b,floor(d/2))

  Francois Grieu

Relevant Pages

  • 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: 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: How much is Alice worth to Bob?
    ... >> X just about as efficiently without knowing S as if she did know S. ... >cases differ not only in Alice's knowledge of S, ... the error probability in your protocol can ...
    (sci.crypt)