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

1 to 7 have the most significant digit as 0. Rest 6 have 1 as MSB.

 

So, $((7*7) + (6 * 6) )/ (13 * 13)$

which is 0.5029

Answer 2

As there are only 6 numbers in set A out of 13 numbers whose MSB will be 1 ( from 8-13) so the probility is 6/13 i.e. 0.4615

Comments

all are saying o.508 because of independence word

---

I got answer as 0.503

Answer 3

Answer : 0.503

the word "chosen independently and uniformly at random" makes big impact on approach,

0001 , 0010 , 0011 , 0100 , 0101 , 0110 , 0111   total=7  :- have 0 at MSB

1000 , 1001 , 1010 , 1011 , 1100 , 1101              total=6 :- have 1 at MSB

(C(7,1)*C(7,1) + C(6,1)*C(6,1)) / ( C(13,1) * C(13,1) )

= ((7*7)+(6*6)) / (13*13) = 0.503

Answer 4

We determine the probability that two numbers selected independently and uniformly from $\{1, 2, \dots, 13\}$ have the same most significant bit (MSB) in their 4-bit unsigned binary representation.

In 4-bit binary, the MSB is the $2^3 = 8$'s place:  

• Numbers 1 to 7 have MSB = 0 → 7 numbers.  
• Numbers 8 to 13 have MSB = 1 → 6 numbers.

1. First selection:  

• Choose a number with MSB = 0 with probability $\frac{7}{13}$.  
• Choose a number with MSB = 1 with probability $\frac{6}{13}$.

2. Second selection (independent):  

• From the MSB = 0 branch, the second number has MSB = 0 with probability $\frac{7}{13}$ → path leads to same MSB.  
• From the MSB = 1 branch, the second number has MSB = 1 with probability $\frac{6}{13}$ → path leads to same MSB.

According to the arrow method, the probability of each complete path is the product of the probabilities along its edges.

Thus:  

• Probability of both having MSB = 0: $\frac{7}{13} \times \frac{7}{13} = \frac{49}{169}$  
• Probability of both having MSB = 1: $\frac{6}{13} \times \frac{6}{13} = \frac{36}{169}$

Adding the probabilities of the two “same MSB” paths gives:  
$$
\frac{49 + 36}{169} = \frac{85}{169} \approx 0.503
$$

Therefore, the required probability, rounded to three decimal places, is 0.503.