Welcome to our community

Be a part of something great, join today!

Expected value of minimum Hamming distance

billobillo

New member
Nov 22, 2012
1
The Hamming distance(HD) between two strings of equal length is the number of characters that differ between the two strings at the same position, for example the HD between "gold" and "wolf" is 2; the MHD is between N strings and is equal to the minimum of HD's among all possible combinations of size k.
My question is: If I randomly select k binary strings of length n out of N=2^n strings , what is the expected value of minimum Hamming distance(MHD) between the k selected strings?
I need to find a general formula that gives me the expected value of the MHD between k random strings of size n selected out of N where (N =2^n)


Below is a table that shows, for N=8 and all k's, the MHD plus its occurrences frequency:

MHD OF
k=2k=3k=4k=5k=6k=7k=8
1124868562881
21282
34

Below another table for N=16

MHD OF
k=2k=3k=4k=5k=6k=7k=8k=9.......
132352159242407952114241286811440
24820822812856162
332
48

There are more results if you need, I appreciate any help from you.
Regards.