GATE CSE 2019 | Question: 22

Question

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 ___________.

Comments

Total number of possible outcomes = 13*13 = 169

( In given set we have 13 numbers i.e. {1, 2, ..., 13}. we have choosen 2 number indipendently and uniformly.

number of possible ways to get 1st number is 13 ways.

number of possible ways to get 2nd number is 13 ways 

so number of possible pairs can form = 13 * 13 = 169 {(1, 1), (1, 2), ...(1, 13), (2, 1), (2,2), ......, (13, 13)})

Number of favorable outcomes : 

Just assume like abcd is 4bit binary number where a-is called most significant bit, d-is called as least significant bit.

here we can get 2 cases

case 1: most significant bit = 0

case 2: most significant bit = 1

CASE 1:

    In this case we can represent a binary numbers from 1 to 7 ( i.e. 0001 to 0111 )

   set1 : {1, 2, 3, 4, 5, 6, 7}, set2: {1, 2, 3, 4, 5, 6, 7}

   each number in set1 can map to set2 in 7 ways

   in set1 we have 7 numbers 

    so number of possible ways we can form a pair is = 7*7 = 49 {(1,1), (1, 2), .....(7, 7)}

CASE 2:

In this case we can represent a binary numbers from 8 to 13 ( i.e. 1000 to 1101 )

   set3 : {8, 9, 10, 11, 12, 13}, set4: {8, 9, 10, 11, 12, 13}

   each number in set3 can map to set4 in 6 ways

   in set3 we have 6 numbers 

    so number of possible ways we can form a pair is = 6*6 = 36 {(8, 8), (8, 9),.......(13, 13)}

Number of favorable outcomes = case1 + case1 = 49+36 = 85

 

Probability of an event = (Number of favorable outcomes) / (Total number of possible outcomes)

                                     = 85/169

                                      = 0.5029

(Note : if anyone thinking like why we can not make a pair like (1, 8) or (8, 1) because 

          1 we can represent in 4 bit binary number = 0001

          8 we can represent in 4 bit binary number = 1000

          Here 1 and 8 numbers most significant bit is different )))

---

Ans is  =0.502

MSB=1 7 no's and MSB=0 6 no's

7/13*7/13 (MSB=1 )+6/13*6/13(MSB=0)

= 49/169+36/169

=85/169

=0.502

WHEN independent (With replacement)

---

MSB same means (either both have MSB 0 or MSB 1)

i feel tree method is very straightforward and ideal for exam.

P(MSB SAME) = P(MSB = 1) + P(MSB = 0)

Answer 1

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$

Comments

@Akash Papnai, @Satbir, @@akash.dinkar12, @srestha

1) why is the denominator  also 13^2 ? Is it because of independence of events ?

Is there any rule that ,for independence events, the Sample space will also be independent ?

 

2)Can someone pls elaborate the  use of the word “Uniformly” in this problem ?

 

Thanks in advance

---

@MohanK, 

1) Yes denominator is $13^2$, as both can be picked independently. You can think of it as picking up two cards from the deck of cards with replacement. So the second time when you will pick up the card, you will still have all the options open to choose from. Same goes here.

2) Uniformly at random means you have to pick one number randomly, and uniform means that the probability of picking a number is same across the set which will be $1/13$.

---

yes if the independent term not given then ans would have been :-0.462

$\frac{7C_{2} + 6C_{2}}{13C_{2}}$ =0.462

Answer 2

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.

Comments

same mistake :(  

the word "INDEPENDENT" plays a significant role here.

Answer 3

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

Comments

You are right but I am unable to edit it as it is showing some thing like “userid, content is needed”, something like that.
It seems there is some error with the editor as of now.

If someone have the edit authority please make the last line as

$\dfrac{49+36}{169}$

---

Now fully corrected.

---

Thanks for great Explanation

Answer 4

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.

Comments

SILLY QUESTION ALERT:- Why denominator = 13*13? Is Independency the reason for this?

---

2 numbers are chosen out of 13

---

Got it Thnx :)

Answer 5

If we do $$\frac{{^7C_2} + {^6C_2}}{{^{13}C_2}}$$

it won't be correct as by doing this we ensure that in choosing 2 elements, they both will necessarily be distinct.

But to be independent, we should be able to select an item n number of times in n trials. Because choosing the same item before shouldn't matter in the present, as the trials are independent. We need to allow repetitions.

 

So,

$$\frac{7}{13}*\frac{7}{13}+\frac{6}{13}*\frac{6}{13}$$

will be correct.

 

0.503 is the answer.

Answer 6

Ans will be 0.462 only!!

​​​

Comments

What I have done --

(7C2  + 6C2)/(13C2)

Got 0.461.