Redirected
retagged by
19,768 views
35 votes
35 votes
Two numbers are chosen independently and uniformly at random from the set $\{1,2,\ldots,13\}.$
The probability (rounded off to $3$ decimal places) that their $4\text{-bit}$ (unsigned) binary representations have the same most significant bit is ___________.
retagged by

9 Answers

Best answer
57 votes
57 votes

These are two groups:

  1. MSB with $1$
  2. MSB with $0$


$n_{\text{MSB0}} = 7, n_{\text{MSB1}} = 6, n_{\text{total}}=13$

Choose randomly and INDEPENDENTLY two elements out of $13$ elements such that MSB is the same.

$P = \frac{n_{\text{MSB1}}\;\ast\; n_{\text{MSB1}} + n_{\text{MSB0}}\;\ast \;n_{\text{MSB0}}}{n_{\text{Total}}}$

$\implies P = \frac{7 \ast 7+ 6 \ast 6}{13 \ast 13} = \frac{85}{169} = 0.5029$

edited by
30 votes
30 votes

Two events are said to be independent of each other if the probability of occurrence of the first event does not affect the probability of occurrence of the second event.

So, here it means that whenever we choose one element from the set of 7 elements with MSB 0 for the first time, we can choose one more element from those 7 elements for the second time which gives us 7*7=7^2 favourable outcomes. Similarly, for the case of set of 6 elements with MSB 1, we get 6^6=6^2  more favourable outcomes. So,total favourable outcomes = 7^7 + 6^6 = 85 and the final answer is 85/13^2=0.502.

PS: I too kept the answer as (7C2  + 6C2)/(13C2) = 0.461 in Gate exam but realized the mistake later.

26 votes
26 votes

$\mathbf{\underline{Answer:\Rightarrow}}\;\;\mathbf{\underline{\bbox[orange, 5px, border:2px solid red]{\color{darkblack}{.5029}}}}$

$\mathbf{\underline{Explanation:\Rightarrow}}$

$\mathbf{\underline{Importance\; of \;word\; \color{blue}{"independently"} \;in\; the\; question:}}$

The word $\underline{\color{blue}{\mathbf{independent}}}$ here means that after selecting a number from the set of numbers, your count of number, that is, the sample space hasn't decreased.

In other words, it can be compared with the problem of picking a ball from the bag and then keeping it again in the bag. Then you can pick the next ball again from the same number of balls.

$\mathbf{\underline{Explanation:\Rightarrow}}$

Total numbers with $\mathbf{0}$ as the significant bits $=\mathbf 7$

Total numbers with $\mathbf{1}$ as the significant bits $=\mathbf 6$

Now,

The probability of picking the number with same $\mathbf{MSB-0} =\mathbf{ \dfrac{7C_1\times7C_1}{13\times13}}$

The probability of picking the number with same $\mathbf{MSB-1 = \dfrac{6C_1\times6C_1}{13\times13}}$

$\therefore$ Total probability $\mathrm{=\dfrac{7C_1\times7C_1}{13\times13}+\dfrac{6C_1\times6C_1}{13\times13} =\mathbf {\dfrac{49+36}{169} }= \mathbf{\underline{\bbox[orange, 5px, border:2px solid red]{\color{darkblack}{.5029}}}}}$

$\mathbf{\color{blue}{\underline{Binary\;representation\;of\;Numbers:}}}$

$\mathbf{NUMBER}$ $\mathbf{MSB}$     $\mathbf{LSB}$
0 $\bbox[yellow, 5px, border:2px solid red]{\color{darkorange}0}$ 0 0 0
1 $\bbox[yellow, 5px, border:2px solid red]{\color{darkorange}0}$ 0 0

1

2 $\bbox[yellow, 5px, border:2px solid red]{\color{darkorange}0}$ 0 1 0
3 $\bbox[yellow, 5px, border:2px solid red]{\color{darkorange}0}$ 0 1 1
4 $\bbox[yellow, 5px, border:2px solid red]{\color{darkorange}0}$ 1 0 0
5 $\bbox[yellow, 5px, border:2px solid red]{\color{darkorange}0}$ 1 0 1
6 $\bbox[yellow, 5px, border:2px solid red]{\color{darkorange}0}$ 1 1 0
7 $\bbox[yellow, 5px, border:2px solid red]{\color{darkorange}0}$ 1 1 1
8 $\bbox[blue, 5px, border:2px solid red]{\color{darkorange}1}$ 0 0 0
9 $\bbox[blue, 5px, border:2px solid red]{\color{darkorange}1}$ 0 0

1

10 $\bbox[blue, 5px, border:2px solid red]{\color{darkorange}1}$ 0 1 0
11 $\bbox[blue, 5px, border:2px solid red]{\color{darkorange}1}$ 0 1 1
12 $\bbox[blue, 5px, border:2px solid red]{\color{darkorange}1}$ 1 0 0
13 $\bbox[blue, 5px, border:2px solid red]{\color{darkorange}1}$ 1 0 1

 

$\therefore$ The correct answer is $\mathbf{.5029}$

edited by
16 votes
16 votes
No of choices with MSB 0 = ( 1, 2, 3, 4, 5, 6, 7}

No of choices with MSB 1 = ( 8, 9, 10, 11, 12, 13}
 

Since independently assumption is made , Probability = (7*7 + 6*6) / 13*13 = 0.503

The choosing of a number from the set doesn't depend upon the previous selection.
edited by
Answer:

Related questions

19 votes
19 votes
4 answers
1
Arjun asked Feb 7, 2019
11,034 views
In $16$-bit $2$’s complement representation, the decimal number $-28$ is:$1111 \: 1111 \: 0001 \: 1100$$0000 \: 0000 \: 1110 \: 0100$$1111 \: 1111 \: 1110 \: 0100$$1000...
19 votes
19 votes
5 answers
2
Arjun asked Feb 7, 2019
13,451 views
Consider $Z=X-Y$ where $X, Y$ and Z are all in sign-magnitude form. X and Y are each represented in $n$ bits. To avoid overflow, the representation of $Z$ would require a...
29 votes
29 votes
4 answers
3
33 votes
33 votes
4 answers
4
Arjun asked Feb 7, 2019
16,081 views
Suppose $Y$ is distributed uniformly in the open interval $(1,6)$. The probability that the polynomial $3x^2 +6xY+3Y+6$ has only real roots is (rounded off to $1$ decimal...