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 ______.
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
GATE 2019 CS Q32– Two numbers are chosen independently and uniformly at random from the set \1,2,,13\. The…
GATE 2019 CS Q57– Suppose Y is distributed uniformly in the open interval (1,6). The probability that the…
GATE 2018 CS Q25– Two people, P and Q, decide to independently roll two identical dice, each with 6 faces,…
GATE 2018 CS Q54– Consider Guwahati (G) and Delhi (D) whose temperatures can be classified as high (H),…
GATE 2016 CS (CS1) Q14– A probability density function on the interval [a, 1] is given by 1/x2 and outside this…
GATE 2016 CS (CS1) Q39– Consider the following experiment. Step 1. Flip a fair coin twice. Step 2. If the outcomes…