Probability that two numbers differ by one bit

Question

Assuming that t is the bit length of the numbers and that we can pick 2 random numbers (the same number cannot be chosen twice), which is the probability that the two numbers will differ by exactly one bit?

From my understanding, the probability to hit a specific bit pattern is $$\frac{1}{2^t}$$

Since there are only t - 1 other bit patterns which differs from the first one by one bit, then we have that the probability to hit two numbers which differ by one bit is:

$$\frac{1}{2^t}\frac{t-1}{2^t} = \frac{t-1}{2^{2t}}$$

Does this make sense?

Thanks

Answer 1

The exclusive-or of two $n$-bit patterns that differ by $k$ bits is an $n$-bit pattern with $k$ ones and $n-k$ zeros. Thus, after choosing the first $n$-bit pattern, there are $\binom{n}{k}$ patterns which differ by $k$ bits.

---

With Replacement

Since there are $2^n$ different $n$-bit patterns, the probability that two $n$-bit patterns differ by $k$ bits is $$ \frac{\binom{n}{k}}{2^n} $$ Therefore, the probability that they differ by $1$ bit is $$ \frac{n}{2^n} $$

---

Without Replacement

Without replacement, the case of $k=0$ is not included, thus, the probability that two $n$-bit patterns differ by $k$ bits is $$ \frac{\binom{n}{k}[k\ne0]}{2^n-1} $$ where $[\cdots]$ are Iverson Brackets.

Therefore, the probability that they differ by $1$ bit is $$ \frac{n}{2^n-1} $$

Answer 2

There are $2^t$ possibilities. The favorable cases are when only one bit is different. For the first time it doesn't matter, what you choose. For the second time this one different bit can be located on $t$ different places, if $t$ is the length. So the probability is: $$\frac{t}{2^t-1}$$ $2^t-1$ because after you choose the first number, after that you have one less.

Answer 3

For every value, there are $t$ values different by one bit

Since there are $2^t$ values, there are seemingly $2^t\cdot{t}$ such pairs

But we need to divide this number by $2$ in order to eliminate duplicates

So the total number of pairs differing by one bit is $\dfrac{2^t\cdot{t}}{2}=\color\red{2^{t-1}\cdot{t}}$

The total number of pairs is $\dbinom{2^t}{2}=\dfrac{2^t\cdot(2^t-1)}{2}=\color\green{(2^{t-1})\cdot(2^t-1)}$

Hence the probability of choosing a pair differing by one bit is $\dfrac{\color\red{2^{t-1}\cdot{t}}}{\color\green{(2^{t-1})\cdot(2^t-1)}}=\dfrac{{t}}{2^t-1}$