8,551 views
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 $\displaystyle{} \Sigma_{i=1}^n a_i x_i$  is an odd number is______________

I have got 0.476 as answer will it be considered as 0.5? This question seems very tough to me. It took me more than an  hour to just understand the question because of complex notations given in the question.

a belongs to {0,1}^n means that  ‘a’ is a vector of dimension n where each entry of the vector is 0 or 1. Hence total possible different vectors are 2^n. But ‘a’ is a non-zero vector hence possible vectors for ‘a’ are 2^n-1 .

Now the question is simply asking the probability  of dot product of two vectors being odd( following the conditions given in the question).

I hope it will save you some time.

Although a generalized answer is always good, we can also solve this question quickly by taking an example, say $n = 3$

Let $a = (0, 0, 1)$. Then, for all 8 combinations of 'x' only 4 combinations $(0, 0, 1), (0, 1, 1), (1, 0, 1), (1, 1, 1)$ will produce odd number (only $1$ in this case), so probability will be $0.5$.

@Ruturaj Mohanty
Thanks.
If a= (0,1,0) then what will be the combinations?

Will it not make every vector even?
A = $\begin{bmatrix}a_{1}\\ a_{2} \\ . \\ . \\ .\\a_{n} \end{bmatrix}$ be a non zero vector.

X = $\begin{bmatrix}x_{1}\\ x_{2} \\ . \\ . \\ .\\x_{n} \end{bmatrix}$ be a randomly chosen vector

Since A is non zero, 'k' entries in A are '1's, where 0 $<$ k $\leq$ n.

n - k entries are '0's.

Moreover these n - k entries multiplied with corresponding entries in X vector is 0. So need not bother about these n - k entries

Let $a_{j_{1}}$, $a_{j_{2}}$, $a_{j_{3}}$, .... , $a_{j_{k}}$ be the entries in A which are '1's, where $j_{1}$ $<$ $j_{2}$ $<$ $j_{3}$ $<$ .... $<$ $j_{k}$

( Note : $j_{1}$ , $j_{2}$ , $j_{3}$ , .... , $j_{k}$ necessarily need not be a continuous sequence as well )

Now consider corresponding $x_{j_{1}}$ , $x_{j_{2}}$ , $x_{j_{3}}$ , ... , $x_{j_{k}}$ entries in X vector.

In order for $\sum_{i=1}^{n}$ $a_{i}$ $x_{i}$ to be odd we need odd number of entries to be '1's in $x_{j_{1}}$ , $x_{j_{2}}$ , $x_{j_{3}}$ , ... , $x_{j_{k}}$ and the rest '0's

So total number of vectors having odd number of '1's in $x_{j_{1}}$ , $x_{j_{2}}$ , $x_{j_{3}}$ , ... , $x_{j_{k}}$ so that $\sum_{i=1}^{n}$ $a_{i}$ $x_{i}$ being odd is

$\binom{k}{1}$ + $\binom{k}{3}$ + $\binom{k}{5}$ + ... + $\binom{k}{k}$ if k is odd = $2^{k-1}$

$\binom{k}{1}$ + $\binom{k}{3}$ + $\binom{k}{5}$ + ... + $\binom{k}{k-1}$ if k is even = $2^{k-1}$

Note : Following is not part of the answer

/*

Similarly,

In order for $\sum_{i=1}^{n}$ $a_{i}$ $x_{i}$ to be even we need even number of entries to be '1's in $x_{j_{1}}$ , $x_{j_{2}}$ , $x_{j_{3}}$ , ... , $x_{j_{k}}$ and the rest '0's

So total number of vectors having even number of '1's in $x_{j_{1}}$ , $x_{j_{2}}$ , $x_{j_{3}}$ , ... , $x_{j_{k}}$ so that $\sum_{i=1}^{n}$ $a_{i}$ $x_{i}$ being even is

$\binom{k}{0}$ + $\binom{k}{2}$ + $\binom{k}{4}$ + ... + $\binom{k}{k-1}$ if k is odd = $2^{k-1}$

$\binom{k}{0}$ + $\binom{k}{2}$ + $\binom{k}{4}$ + ... + $\binom{k}{k}$ if k is even = $2^{k-1}$

*/

The total number of combinations in $x_{j_{1}}$ , $x_{j_{2}}$ , $x_{j_{3}}$ , ... , $x_{j_{k}}$ is $2^{k}$

that is $\binom{k}{0}$ + $\binom{k}{1}$ + $\binom{k}{2}$ + ... + $\binom{k}{k}$ = $2^{k}$ or in other words $2_{j_{1}}$ $\times$ $2_{j_{2}}$ $\times$ $2_{j_{3}}$ $\times$ ... $\times$ $2_{j_{k}}$ = $2^{k}$

Now Probability = $\frac{Odd\,Combinations}{Total\,Combinations}$ = $\frac{2^{k-1}}{2^{k}}$ = 0.5

I get the summation for k is even but how is it 2^(k-1) for when k is odd?

see this Wow thanks! this is awesome