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

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

Solution:

The 4-bit binary representation of numbers (1, 2, 3, 4………13):

0  – 0000

1  – 0001

2  – 0010

3  – 0011

4  – 0100

5  – 0101

6  – 0110

7  – 0111

8  – 1000

9  – 1001

10 – 1010

11 – 1011

12 – 1100

13 – 1101

There 6 numbers which start with MSB as 1, and 7 numbers which start with MSB as 0.

Therefore, probability that their 4-bit binary representations have the same most significant bit is,

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

= (7×7)/(13×13) + (6×6)/(13×13)

= (49+36)/169

= 85/169

= 0.5029