The GATE Grind

GATE 2020 CS – Question 55

Engineering Mathematics · Probability and Statistics · 2 marks · Numerical answer

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$ (it exists because $a$ is non-zero). Fix all the other bits $x_i$ ($i\ne j$) arbitrarily. Then
$$\sum_ia_ix_i=\underbrace{\sum_{i\ne j}a_ix_i}_{\text{fixed}}+x_j.$$
Exactly one of the two values $x_j\in\{0,1\}$ makes the total odd. Since $x_j$ is uniform, the probability of an odd sum is $\dfrac12=\mathbf{0.5}$ for every choice of the other bits, hence overall.

More Probability and Statistics questions

All Probability and Statistics questions →