For \(n>2\), let \(a ∈ \{0, 1\}^n\) be a non-zero vector. Suppose that \(x\)…
2020
For \(n>2\), let \(a ∈ \{0, 1\}^n\) be a non-zero vector. Suppose that \(x\) is chosen uniformly at random from \(\{0,1\}^n\). Then, the probability that \(\displaystyle{} \Sigma_{i=1}^n a_i x_i\) is an odd number is _________ .
Attempted by 36 students.
Show answer & explanation
Correct answer: 0.5
Answer: 1/2
Explanation:
Since a is non-zero, at least one coordinate of a equals 1. Reorder coordinates so that a_n = 1 (reordering does not change the distribution of x).
For any fixed values of x_1, …, x_{n-1}, the sum Σ_{i=1}^n a_i x_i differs by exactly 1 between x_n = 0 and x_n = 1 (because a_n = 1). Thus for each fixed choice of the first n−1 bits, exactly one choice of x_n makes the total sum odd.
There are 2^{n-1} choices for the first n−1 bits, and for each there is exactly one choice of x_n producing an odd sum. Hence the number of x giving an odd sum is 2^{n-1} out of 2^n total choices.
Therefore the probability the sum is odd is 2^{n-1}/2^n = 1/2.