For , let be a non-zero vector. Suppose that is chosen uniformly at random from . Then, the probability that is an odd number is ____.
GATE 2020 CS Q.45: solution and answer
Answer and solution
ANSWER
The probability is .
Official answer: 0.5Source: Official answer key, GATE 2020 CS (IIT Delhi)
Only the coordinates with matter. Let and , since is non-zero.
Then , the number of ones among the bits with .
The bits are independent and uniform, so the number of ones is Binomial and .
Use and for . Subtracting the second from the first gives , so .
So .
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.
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
- GATE 2020 EC Q.54 · NAT · 2 marksX is a random variable with uniform probability density function in the interval [-2, 10].
- GATE 2020 IN Q.16 · NAT · 1 markA player throws a ball at a basket kept at a distance. The probability that the ball falls into the basket…
- GATE 2020 IN Q.32 · NAT · 2 marksConsider two identical bags B1 and B2 each containing 10 balls of identical shapes and sizes.
- GATE 2019 BT Q.22 · NAT · 1 markThe median value for the dataset (12, 10, 16, 8, 90, 50, 30, 24) is.
