2
$\begingroup$

Two '$n$' bit binary strings $S_1$ and $S_2$ are chosen randomly with uniform probability. The probability that the hamming distance between these strings (the number of bit positions where the two strings differ) is equal to $d$ is ?


My approach

We can choose 2 random strings out of $2^n$ strings possible in $2^n C 2$ ways.

Now the probability of 2 bits being different is $0.5$

Applying binomial distribution we get,

$2^n C 2 * (0.5)^d * (0.5)^{n-d}$ .

Here $(0.5)^d$ means probability of 'd' bits being different in 2 strings which were chosen.

Why is this approach wrong ?

$\endgroup$

1 Answer 1

2
$\begingroup$

The approach is wrong because you don't say which random variable satisfies which binomial distribution. The answer is that the number $X$ of bits that differ between the two strings satisfies $B(n, \frac{1}{2})$. Hence the probability is $$ P(X=d)=\binom{n}{d}(1/2)^d (1/2)^{n-d} = \frac{1}{2^n}\binom{n}{d} $$

Edit As your comment implies that you want a more complete model, here it is: let $K = \{0, 1\}^n$ be the set of n-bit strings. Let $d\in [0, n]$ and $K_d$ the substet of $K$ consisting of the strings with exactly $d$ bits set. Note that $\text{Card}(K_d) = \binom{n}{d}$.

We choose randomly two strings $s_1, s_2\in K$. They can be the same string, so this amounts to choosing an ordered random pair $(s_1, s_2)\in K^2$. There are $2^{2 n}$ possible choices, each of them has the probability $2^{-2n}$. The number $\delta(s_1, s_2)$ of bits that differ between $s_1$ and $s_2$ is the number of bits set in their bitwise xor sum $s_1 \oplus s_2$, or bitwise sum mod 2. This operation makes $K$ a group where each element is its own opposite. We need to count the number of pairs $(s_1, s_2)$ such that $s_1\oplus s_2 \in K_d$. It is very easy, because this is equivalent to $s_2 = s \oplus s_1$ with $s \in K_d$. It follows that for each $s_1\in K$ and each $s \in K_d$, there is exactly one $s_2$. Hence the number of ordered pairs is $\text{Card}(K\times K_d) = 2^n \binom{n}{d}$. Finally, the probability is $$ 2^{-2n} 2^n \binom{n}{d} = \frac{1}{2^n}\binom{n}{d} $$

$\endgroup$
7
  • $\begingroup$ What about choosing 2 strings out of 2^n strings? Why are you not considering that ? $\endgroup$
    – Zephyr
    Commented Nov 19, 2017 at 8:30
  • $\begingroup$ So in your first solution, you already assumed that we have two strings instead of choosing them? $\endgroup$
    – Zephyr
    Commented Nov 19, 2017 at 10:01
  • $\begingroup$ No, the reasoning for the first solution is that for each bit, there are 4 equiprobable choices: $(0,0), (0,1), (1, 0), (1, 1)$. The probability that the two strings differ on this bit is $1/2$. As the values of the strings on each bit are independent, it follows that $\delta(s_1, s_2)$ obeys $B(n, 1/2)$. $\endgroup$ Commented Nov 19, 2017 at 10:12
  • $\begingroup$ Yes I understand that. But you assume that you have 2 strings of n bits with you. Out of those n bits, probability of X=d is as shown by you right ? $\endgroup$
    – Zephyr
    Commented Nov 19, 2017 at 10:14
  • 1
    $\begingroup$ Let's say we have $2n$ randomly and independently chosen bits. $\endgroup$ Commented Nov 19, 2017 at 10:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .