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 i=1naixi is an odd number is ______.

Correct Answer:



A = [a1, a2, . . . , anbe a non-zero vector

X = [x1, x2, . . . , xn]  be a randomly chosen vector

Since A is non-zero, 'k' entries in A are '1's, where 0 < k ≤ n and the (n – k) entries are '0's. Moreover, when these (n – k) entries are multiplied with corresponding entries in the X vector they will also be 0. So we can ignore these (n – k) entries.

Let aj1, aj2, aj3,..., ajk be the entries in A which are '1's, where j1 < j2 < j3 < . . . < jk

( Note: j1, j2, j3,..., jk necessarily need not be a continuous sequence as well )

Now consider corresponding xj1, xj2, xj3,..., xjk entries in X vector.

In order for i=1naixi to be odd, we need an odd number of entries to be 1 and the rest as 0.

Hence, The total number of combinations in xj1, xj2, xj3,..., xjk is 2k

Probability can be given as:

=Odd CombinationsTotal Combinations = 2k-12k = 0.5