Expected value of minimum Hamming distance
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 minimum Hamming distance(MHD) between k strings of same length selected out of N strings is equal to the minimum of the HDs among all possible combinations of size k selected out of N.
My question is: If I randomly select k binary numbers of length n out of N=2^n numbers, what is the expected value of the minimum Hamming distance between the k selected numbers? I need to find a general formula that gives me the expected value of the MHD from the values of K and N.
Below is a table that shows, for N=8 and all k's, the MHD plus its occurrences frequency (OF):
| MHD | | | | OF | | | |
| k=2 | k=3 | k=4 | k=5 | k=6 | k=7 | k=8 |
| 1 | 12 | 48 | 68 | 56 | 28 | 8 | 1 |
| 2 | 12 | 8 | 2 | | | | |
| 3 | 4 | | | | | | |
Below another table for N=16
| MHD | | | | OF | | | | | |
| k=2 | k=3 | k=4 | k=5 | k=6 | k=7 | k=8 | k=9 | ....... |
| 1 | 32 | 352 | 1592 | 4240 | 7952 | 11424 | 12868 | 11440 | |
| 2 | 48 | 208 | 228 | 128 | 56 | 16 | 2 | | |
| 3 | 32 | | | | | | | | |
| 4 | 8 | | | | | | | | |
Appreciate any help, regards.