GATE 2020 CS – Question 55
For $n>2$, let $a\in\{0,1\}^n$ be a non-zero vector. Suppose that $x$ is chosen uniformly at random from $\{0,1\}^n$. Then, the probability that $\sum_{i=1}^{n}a_ix_i$ is an odd number is ______.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 0.5 to 0.5
Explanation
Pick an index $j$ with $a_j=1$. Fixing all other bits, exactly one of the two values of $x_j$ makes the sum odd. So the probability is 1/2.