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, th...

Question

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_i * x_i is an odd number is ______________

Accepted Answer

P(sum a_i x_i is odd) = 0.5. We have a fixed non-zero binary vector a = (a_1, ..., a_n) and a uniformly random binary vector x = (x_1, ..., x_n). The sum S = a_1*x_1 + a_2*x_2 + ... + a_n*x_n counts 1s where both a_i and x_i equal 1. S is odd iff an odd number of positions where a_i=1 have x_i=1. Since a is non-zero, at least one a_i = 1. The x_i bits at positions where a_i=1 determine the parity of S. By symmetry, exactly half of all binary choices for those bits give an odd sum.