Gate CS 2020 | Question - 45 | Engineering Mathematics

For n>2, let a ∈ {0, 1}ⁿ 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 ______.

Correct Answer:

0.5

Solution:

A = [a₁, a₂, . . . , a_n] be a non-zero vector

X = [x₁, x₂, . . . , 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{O d d C o m b i n a t i o n s}{T o t a l C o m b i n a t i o n s} = \frac{2^{k - 1}}{2^{k}} = 0.5$

Gate CS 2020 | Question - 45 | Engineering Mathematics

Related Topics