0
$\begingroup$

I initially have all length-$L$ binary strings. Suppose I randomly sample without replacement $k\le 2^L$ strings from this set. What is the expected pair-wise hamming distances of the sampled $k$ binary strings?

$\endgroup$
  • $\begingroup$ How is the Hamming distance of $k$ strings defined? I only know the definition for two strings. $\endgroup$ – joriki Mar 7 '16 at 12:45
  • $\begingroup$ A pair of string has a hamming distance, what is the expectation of all pairs. $\endgroup$ – Adam I. Mar 7 '16 at 13:00
0
$\begingroup$

The method of sampling is irrelevant here; the individual pairs are uniformly sampled from all pairs, so the expected Hamming distance is just the expected Hamming distance of a uniformly sampled pair, which is $L/2$ (or, in case you were referring to the sum over all pairs, $\binom k2\cdot\frac L2$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.