Re: minimum Hamming distance among random bit vectors
From: Michael Amling (nospam_at_nospam.com)
Date: 04/29/04
- Next message: Tom St Denis: "Re: Crossposts"
- Previous message: Michael Amling: "Re: Blowfish Sign Extension implementation risk"
- In reply to: Francois Grieu: "minimum Hamming distance among random bit vectors"
- Next in thread: Francois Grieu: "Re: minimum Hamming distance among random bit vectors"
- Reply: Francois Grieu: "Re: minimum Hamming distance among random bit vectors"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Thu, 29 Apr 2004 12:16:28 GMT
Francois Grieu wrote:
> 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
You assume d>0
>
> [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
How can there be a nonzero probability of "two distinct vectors which
differ by at most" 0 bits?
>
> 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)
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). The equality holds at least at N(7,1)=16+1, from
the error correction code posted not too long ago.
> 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 ?
--Mike Amling
- Next message: Tom St Denis: "Re: Crossposts"
- Previous message: Michael Amling: "Re: Blowfish Sign Extension implementation risk"
- In reply to: Francois Grieu: "minimum Hamming distance among random bit vectors"
- Next in thread: Francois Grieu: "Re: minimum Hamming distance among random bit vectors"
- Reply: Francois Grieu: "Re: minimum Hamming distance among random bit vectors"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
|
