2
$\begingroup$

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.
$\endgroup$
1
  • 2
    $\begingroup$ 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$ $\endgroup$
    – Henry
    Nov 25 at 15:10
1
$\begingroup$

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}$$

$\endgroup$

Your Answer

VitoShade is a new contributor. Be nice, and check out our Code of Conduct.

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.