1
$\begingroup$

Came across this problem, and while i know the correct answer, I cannot seem to rationalize it.

Given 2 bit strings that are generated randomly , where each bit is either 0 or 1 (eg 001010101010). What is the probability that the bit at a specific place will equal the bit in the same place in the other string?

Now, the correct answer is noticing that there are only four possible combinations for this; 00, 01, 10, 11 , where only two of them lead the numbers being the same. Thus the answer is 1/2

However, the way that I think about this, is to say, the probability that the bit in string 1 will be a certain number is 1/2, the probability that the bit in the other string will be 1/2 , so 1/4.

Or using the formula , two random integers are equal in a range [m,n]

1/(n-m+1)*(n-m+1) = 1/(2)(2) = 1/4

Can someone help me rationalize this

$\endgroup$
3
  • 2
    $\begingroup$ The probability that they are both $0$ is $1/4$ and the probability that they are both $1$ is $1/4$. The probability that they are both the same is therefore the sum of these two probabilities $\endgroup$ – jacer21 Nov 23 '16 at 16:01
  • $\begingroup$ It's kinda hard to rationalize something that is not true. $\endgroup$ – barak manos Nov 23 '16 at 16:02
  • 1
    $\begingroup$ the probability of 1/4 you are working out is the probability that both bits are 1. it is also the independent probability that both bits are 0. Since 11 and 00 are the only two ways the bits can be the same P(both the same) = 1/4 + 1/4 = 1/2 $\endgroup$ – Cato Nov 23 '16 at 16:02
2
$\begingroup$

Whatever the value of the bit in the first number, the corresponding bit in the other number is either the same or different, with equal probability. In other words, the probability is $\frac12$. The probability of all bits being the same in two $n$-bit numbers is therefore $(\frac12)^n$. This should make sense because there are $2^n$ such numbers; fixing one, the second has a $\frac1{2^n}$ chance of being the same.

However, the way that I think about this, is to say, the probability that the bit in string 1 will be a certain number is 1/2, the probability that the bit in the other string will be 1/2 , so 1/4.

That's true, but you're accounting for only one of two possibilities. You've counted the probability of both bits being $0$, say. The probability of both being $1$ is also $\frac14$, so the overall probability that the bits are identical is $\frac14+\frac14=\frac12$, which agrees with my first paragraph.

$\endgroup$
0
$\begingroup$

There are lots of ways to try and rationalize your question, because your statement is correct and you seem to intuitively understand what is happening. I would point you in the direction of Conditional Probability to help you see what is happening.

What you are really asking is: What is the probability that the bit in the second string will be the same number as the bit in the first string?

It's commonly denoted as Bayes' Formula, but in our case it is simply reduced to $$P( E\, | \,F ) = {P(E\, \cap\,F)\over P(F)}.$$ where E is the event that depends strictly on F.

P(F) denotes the probability of choosing a one or a zero with equal probability, thus $$P(F) = 1$$ P(E) is going to denote the probability that we choose the same value that was chosen before, which makes $$P(E) = .5$$

Observe that$$P(E \cap F) = P(E)P(F)$$ due to the fact that the two events are independent. Substituting these values into the first equation shows that $$P(E\,|\,F) = {{1 \over 2}\cdot1 \over 1} = {1 \over 2}.$$

So the probability of the items being the same is 1/2, as you suspected.

$\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.