GATE CS 2020 Q45 — Probability: Random Variables and Distributions

We are given that $a \in \{0,1\}^n$ is a non-zero vector. This means that at least one component of $a$ is equal to $1$. Let $k$ be the number of ones in $a$, where $1 \le k \le n$.

Let the indices where $a_i = 1$ be $i_1, i_2, \dots, i_k$. The sum can be simplified as: $$\sum_{i=1}^n a_i x_i = \sum_{j=1}^k x_{i_j}$$

Since $x$ is chosen uniformly at random from $\{0,1\}^n$, each component $x_i$ is an independent Bernoulli random variable with: $$P(x_i = 1) = P(x_i = 0) = \frac{1}{2}$$

The sum of these $k$ independent random variables is odd if and only if an odd number of them are equal to $1$. The probability of this event is given by: $$P\left(\sum_{j=1}^k x_{i_j} \text{ is odd}\right) = \sum_{r \text{ is odd}} \binom{k}{r} \left(\frac{1}{2}\right)^r \left(\frac{1}{2}\right)^{k-r}$$ $$= \left(\frac{1}{2}\right)^k \sum_{r \text{ is odd}} \binom{k}{r}$$

Using the binomial identity for the sum of odd binomial coefficients for $k \ge 1$: $$\sum_{r \text{ is odd}} \binom{k}{r} = 2^{k-1}$$

Substituting this back into the probability expression: $$P\left(\sum_{i=1}^n a_i x_i \text{ is odd}\right) = \left(\frac{1}{2}\right)^k \cdot 2^{k-1} = \frac{2^{k-1}}{2^k} = \frac{1}{2} = 0.5$$