IAE Academy

GATE 2020 CS Q.45: solution and answer

GATE 2020 · CSQ.45 · 2 marks · NAT

For , let be a non-zero vector. Suppose that is chosen uniformly at random from . Then, the probability that is an odd number is ____.

See the question in the paper

Answer and solution

ANSWER

The probability is .

Official answer: 0.5Source: Official answer key, GATE 2020 CS (IIT Delhi)

  1. Only the coordinates with matter. Let and , since is non-zero.

  2. Then , the number of ones among the bits with .

  3. The bits are independent and uniform, so the number of ones is Binomial and .

  4. Use and for . Subtracting the second from the first gives , so .

  5. So .

  6. Another way to see it: fix for one and let the other bits take any values. Flipping flips the parity of the sum, so exactly one of its two values makes the sum odd. This pairs up the vectors into equal halves.

  7. The answer is for every non-zero , so it does not depend on or on .

KEY IDEA

The sum of a non-empty set of independent fair bits is odd with probability one half. Flipping any one included bit flips the parity, which pairs up the outcomes into equal halves.

WATCH OUT FOR

Thinking the answer depends on or on how many ones has, or counting only the all-zero vector as even. The even outcomes are not just one case. Exactly half of all give an even sum.

From the GATE 2020 CS paper. Every question of this paper · Download the full paper · All 60 Probability & statistics questions, with notes

More Probability & statistics questions