# Probability calculus on random bitstrings

If I randomly choose 2 bitstring on length (n) with n to be an even number, what is the probability, parametrized on n, that at least n/2 of the bits are equals?

In my mind, since the random choice of every single bit is considered independent, I presume that the total probability is 1/2, but i'm sincerely confused.

Edit: My English is bad, let me give a little example

If bistring_1(4) = 1001 and bitstring_2(4) = 1010 the statement is true because they have in common at least n/2 bits.

New contributor
VitoShade is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• If all strings are equally likely and independent and $n$ is even then the probability that two match exactly $n/2$ times is $\frac{n!}{((n/2)!)^2 2^n}$. The probability they match more than $n/2$ times is half of the remaining probability. Add these together and you get slightly more than $\frac12$ Nov 25 at 15:10

## 1 Answer

If we assume that all bitstrings are equally likely then the problem is quite simple. Each matched pair of bits in the bitstrings will match with fixed probability $$\tfrac{1}{2}$$ and the number of matches has distribution:

$$M \sim \text{Bin}(n, \tfrac{1}{2}).$$

Consequently, the probability of at least $$n/2$$ matches (for even $$n$$) is:

\begin{align} \mathbb{P}(\text{At least } \tfrac{n}{2} \text{ matches}) &= \sum_{m=n/2}^n \text{Bin}(m|n, \tfrac{1}{2}) \\[6pt] &= \frac{1}{2^n} \sum_{m=n/2}^n {n \choose m} \\[6pt] &= \frac{1}{2} \Bigg[1 + \frac{1}{2^n} {n \choose n/2} \Bigg]. \\[6pt] \end{align}