GATE CS 2019 Set 1 — Question 32

To find the probability that two independently and uniformly chosen numbers from the set $S = \{1, 2, \dots, 13\}$ have the same most significant bit (MSB) in their 4-bit unsigned binary representation, we analyze the binary representations of the elements in $S$.

Step 1: Determine the MSB of each number in the set

The numbers in the set $S = \{1, 2, \dots, 13\}$ can be represented as 4-bit unsigned binary numbers (from 0000 to 1111):

• Numbers with MSB = 0:

These are the numbers in the range $[1, 7]$, which in 4-bit binary are:

• $1 = 0001_2$
• $2 = 0010_2$
• $3 = 0011_2$
• $4 = 0100_2$
• $5 = 0101_2$
• $6 = 0110_2$
• $7 = 0111_2$

There are $n_0 = 7$ such numbers.

• Numbers with MSB = 1:

These are the numbers in the range $[8, 13]$, which in 4-bit binary are:

• $8 = 1000_2$
• $9 = 1001_2$
• $10 = 1010_2$
• $11 = 1011_2$
• $12 = 1100_2$
• $13 = 1101_2$

There are $n_1 = 6$ such numbers.The total number of elements in the set is $N = 13$.---

Step 2: Calculate the probability

Two numbers, say $X$ and $Y$, are chosen independently and uniformly at random from $S$. The probability that both numbers have MSB = 0 is:$$P(\text{both MSB } 0) = \left(\frac{n_0}{N}\right) \times \left(\frac{n_0}{N}\right) = \left(\frac{7}{13}\right)^2 = \frac{49}{169}$$The probability that both numbers have MSB = 1 is:$$P(\text{both MSB } 1) = \left(\frac{n_1}{N}\right) \times \left(\frac{n_1}{N}\right) = \left(\frac{6}{13}\right)^2 = \frac{36}{169}$$Since these two events are mutually exclusive, the total probability $P$ that both numbers have the same MSB is:$$P = P(\text{both MSB } 0) + P(\text{both MSB } 1)$$$$P = \frac{49}{169} + \frac{36}{169} = \frac{85}{169}$$---

Step 3: Convert to decimal representation

Performing the division:$$P = \frac{85}{169} \approx 0.502958...$$Rounding off to 3 decimal places, we get:$$P \approx 0.503$$