GATE CS 2019 Q.32 (CS Q.22): Probability and Statistics

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

Your answer

Official answer and solution

Accepted answers: 0.502 to 0.504
From: Official GATE 2019 answer key

Solution

Classify the numbers by their most significant bit in 4-bit unsigned binary, then calculate the joint probability.

The set of numbers is $S = \{1, 2, \dots, 13\}$ , so $|S| = 13$ .
Let us examine the 4-bit unsigned binary representations of each element:

For numbers $1$ to $7$ ( $0001_2$ to $0111_2$ ):
The most significant bit (MSB, 4th bit) is $0$ . There are $7$ such numbers.
For numbers $8$ to $13$ ( $1000_2$ to $1101_2$ ):
The most significant bit (MSB, 4th bit) is $1$ . There are $6$ such numbers.

Two numbers are chosen independently and uniformly at random with replacement from $S$ .
The total number of equally likely outcomes is:

N_{\text{total}} = 13 \times 13 = 169

The favorable outcomes where both numbers have the same MSB are:

Both have $\text{MSB} = 0$ : $7 \times 7 = 49$ ways.
Both have $\text{MSB} = 1$ : $6 \times 6 = 36$ ways.

N_{\text{fav}} = 49 + 36 = 85

Therefore, the probability is:

P = \frac{85}{169} \approx 0.5029585...

Rounding off to 3 decimal places gives 0.503.

Final answer

0.503

Common trap

Assuming sampling without replacement (which yields (7*6 + 6*5) / (13*12) = 72/156 = 0.462) instead of independent draws.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2019 Computer Science and Information Technology (CS)
Question: 32 of 65, printed as CS Q.22
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source