For n>2, let *a ∈ {0, 1} ^{n}* be a non-zero vector. Suppose that

*x*is chosen uniformly at random from

*{0, 1}*. Then, the probability that $\sum _{i=1}^{n}{a}_{i}{x}_{i}$ is an odd number is ______.

^{n}0.5

**Solution:**

A = [a_{1}, a_{2}, . . . , a_{n}] *be a non-zero vector*

*X = [x _{1}, x_{2}, . . . , x_{n}] 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 a_{j1}, a_{j2}, a_{j3},..., a_{jk} 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 x_{j1}, x_{j2}, x_{j3},..., x_{jk} entries in X vector.

In order for $\sum _{i=1}^{n}{a}_{i}{x}_{i}$ 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 x_{j1}, x_{j2}, x_{j3},..., x_{jk} is 2^{k}

Probability can be given as:

=$\frac{OddCombinations}{TotalCombinations}=\frac{{2}^{k-1}}{{2}^{k}}=0.5$