# Expected number of pairs with Hamming distance $d$ for a sample of $k$ random bit strings of length $n$

Say we were to uniformly sample $$k$$ times from a bit string with length $$n$$. What is the expected number of pairs with a Hamming distance $$d$$? In the limit of Hamming distance 0, I realize this becomes a birthday collision problem, but I am interested in the general case.

For example, say we generate 1000 random 10-bit strings, what is the expected number of strings with a Hamming distance of 3?

I found several related posts: Probability that a set of 'N' random binary strings are all at least a certain Hamming distance 'k' apart , birthday problem near misses , and Average number of strings with edit distance exactly 2 but I could not quite make the additional leap to answer my similar but not exactly the same question.

• The question, as you have it worded right now, does not make sense to me. Maybe you meant to ask, "What is the expected number of pairs of sampled strings whose distance is $d$?". Is that a fair interpretation? May 12, 2022 at 16:38
• Hi, yes that is what I mean. Thanks for clarifying it May 13, 2022 at 7:45

Actually this seems quite easy

Let $$A^d_{i,j}$$ be the event that two strings $$s_i$$ $$s_j$$ have distance $$d$$. Then, if both $$s_i,s_j$$ are random, we have $$P(A^d_{i,j})= \binom{n}{d} 2^{-n}$$

Then, if we sample $$k$$ random strings, the expected number of pairs with such distance is

$$\frac{k(k-1)}{2} \binom{n}{d} 2^{-n}$$

• Perfect, thank you very much. That makes total sense! May 13, 2022 at 13:50

The probability that a pair of strings has Hamming distance $$d$$ follows a binomial distribution: $$P(X=d)=\binom{n}{d}(1/2)^d (1/2)^{n-d} = \frac{1}{2^n}\binom{n}{d}$$
Then, this probability is multiplied by the total number of pairings that can be made in a set of $$k$$ items. This can be found from the series: $$(k-1) + (k-2) + ... (k-(k-1))$$ which reduces to $$\frac{k(k-1)}{2}$$