1
$\begingroup$

Given three random bits, pick two (without replacement). What is the probability that the two you pick are equal?

I would like to know if the following analysis is correct and/or if there is a better way to think about it.

$$\Pr[\text{choose two equal bits}] = \Pr[\text{2nd bit} = 0 \mid \text{1st bit} = 0] + \Pr[\text{2nd bit} = 1 \mid \text{1st bit} = 1]$$

Given three random bits, once you remove the first bit the other two bits can be: 00, 01, 11, each of which occurring with probability $\frac{1}{2}\cdot\frac{1}{2}=\frac{1}{4}$. Thus,

$$\Pr[\text{2nd bit} = 0] = 1\cdot\frac{1}{4} + \frac{1}{2}\cdot\frac{1}{4} + 0\cdot\frac{1}{4} = \frac{3}{8}$$

And $\Pr[\text{2nd bit} = 1] = \Pr[\text{2nd bit} = 0]$ by the same analysis.

Therefore,

$$\Pr[\text{2nd bit}=0 \mid \text{1st bit} = 0] = \frac{\Pr[\text{1st and 2nd bits are 0}]}{\Pr[\text{1st bit}=0]} = \frac{1/2\cdot3/8}{1/2} = \frac{3}{8}$$

and by the same analysis, $\Pr[\text{2nd bit} = 1 \mid \text{1st bit} = 1] = \frac{3}{8}$.

Thus, $$\Pr[\text{choose two equal bits}] = 2\cdot\frac{3}{8} = \frac{3}{4}$$

$\endgroup$
2
  • 1
    $\begingroup$ Not correct. Whatever the first bit picked, the probability the second bit matches it is $1/2$. $\endgroup$ – André Nicolas Feb 21 '13 at 20:22
  • $\begingroup$ Why "$\Pr[\text{2nd bit} = 0] = 1\cdot\frac{1}{4} + \frac{1}{2}\cdot\frac{1}{4} + 0\cdot\frac{1}{4} = \frac{3}{8}$"? And "$\Pr[\text{choose two equal bits}] = \Pr[\text{2nd bit} = 0 \mid \text{1st bit} = 0] + \Pr[\text{2nd bit} = 1 \mid \text{1st bit} = 1]$" should be "$\Pr[\text{choose two equal bits}] = \Pr[\text{2nd bit} = 0, \text{1st bit} = 0] + \Pr[\text{2nd bit} = 1, \text{1st bit} = 1]$" $\endgroup$ – TMM Feb 21 '13 at 20:26
1
$\begingroup$

In your listing of possibilities you missed 10. That would get $\Pr[\text{2nd bit} = 0] =\frac 12$

Then when you say $\Pr[\text{choose two equal bits}] = \Pr[\text{2nd bit} = 0 \mid \text{1st bit} = 0] + \Pr[\text{2nd bit} = 1 \mid \text{1st bit} = 1]$ you need to multiply the first term by $\Pr[\text{1st bit} = 0]=\frac 12$ and the second by $\Pr[\text{1st bit} = 1]=\frac 12$

This will give a final answer of $\frac 12$

Really, starting with three bits is a red herring. The possibilities for the two bits are $00,10,01,11$, all equally likely. $2$ of the $4$ have the bits the same.

$\endgroup$
0
1
$\begingroup$

Clearly the intuition tells us that the answer should be $\frac{1}{2}$, because choosing 2 random bits at random without replacing is just like simply choosing two random bits which are equal with probability $\frac{1}{2}$.

There are 3 way to choose two bits out of 3, i.e. choosing $B_1$ and $B_2$ or $B_2$ and $B_3$ or $B_1$ and $B_3$ which are equally likely, thus: $$ \Pr\left(\text{two same bits}\right) = \frac{1}{3} \Pr\left(B_1 = B_2\right) + \frac{1}{3} \Pr\left(B_2 = B_3\right) + \frac{1}{3} \Pr\left(B_1 = B_3\right) $$ since each bit is independent and equally likely to be either 0 or 1, $\Pr\left(B_1 = B_2\right) = \Pr\left(B_2 = B_3\right) = \Pr\left(B_1 = B_3\right) = \frac{1}{2}$.

$\endgroup$
0
0
$\begingroup$

Whatever the first bit picked, the probability the second bit matches it is $1/2$.

Remark: We are assuming what was not explicitly stated, that $0$'s and $1$'s are equally likely. One can very well have "random" bits where the probability of $0$ is not the same as the probability of $1$.

$\endgroup$
0
$\begingroup$

I hope I'm not repeating anyone else's answer here.

Since there are 3 bits, there are $2^3$ possible combinations. We can break them down into 2 categories: Category 1: all bits are the same, i.e. $\{000,111 \}$.
Category 2: two bits are 0, one is 1. Category 3: two bits are 1, one is 0.

Clearly the last category is the same as 2.

Hence your law of total probability should be something like

$$ P(\text{sample two same bits})=P(\text{sample 2 same bits}|C1)P(C1) +2P(\text{sample 2 same bits}|C_2)P(C_2)\\ =1 \cdot \frac{2}{2^3} + 2 \cdot \frac{2}{3} \cdot \frac{1}{2} \cdot \binom{3}{1}\cdot \frac{1}{2^3}=\frac{1}{2} $$

Expanation: $\binom{3}{1} \cdot \frac{1}{2^3}$ is the probability of the outcome 'two bits are the same 1, one is different' (since you have 3 slots). $\frac{2}{3} \cdot \frac{1}{2}$ is the probability to sample two of those equal bits without replacement. 2 is of course due to 2 options (0 or 1).

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