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$ Commented Feb 21, 2013 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
    Commented Feb 21, 2013 at 20:26

4 Answers 4

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .