Question

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

Answer 1

Unsigned binary representation				Decimal	Set
0	0	0	0	0	Not Chosen
0	0	0	1	1	Chosen	0 as MSB
0	0	1	0	2	Chosen	0 as MSB
0	0	1	1	3	Chosen	0 as MSB
0	1	0	0	4	Chosen	0 as MSB
0	1	0	1	5	Chosen	0 as MSB
0	1	1	0	6	Chosen	0 as MSB
0	1	1	1	7	Chosen	0 as MSB
1	0	0	0	8	Chosen	1 as MSB
1	0	0	1	9	Chosen	1 as MSB
1	0	1	0	10	Chosen	1 as MSB
1	0	1	1	11	Chosen	1 as MSB
1	1	0	0	12	Chosen	1 as MSB
1	1	0	1	13	Chosen	1 as MSB
1	1	1	0	14	Not Chosen
1	1	1	1	15	Not Chosen

 

MSB as 0:

\(P\left( {MSB = 0} \right) = \frac{7}{{13}}\)

Since events are independent

\(P\left( {MSB = 0\;and\;MSB = 0} \right) = \frac{7}{{13}} \times \frac{7}{{13}} = 0.28994\)

OR

MSB as 1:

\(P\left( {MSB = 1} \right) = \frac{6}{{13}}\)

Since events are independent

\(P\left( {MSB = 1\;and\;MSB = 1} \right) = \frac{6}{{13}} \times \frac{6}{{13}} = 0.21301\)

Probability that both numbers has same MSB

\(= P\left( {MSB = 0\;and\;MSB = 0} \right)\;or\;P\left( {MSB = 1\;and\;MSB = 1} \right)\)

\(= \frac{7}{{13}} \times \frac{7}{{13}} + \frac{6}{{13}} \times \frac{6}{{13}}\)

= 0.50295

= 0.502 or ≈ 503