retagged by
12,134 views
24 votes
24 votes
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______________
retagged by

2 Answers

Best answer
47 votes
47 votes
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$.
selected by
47 votes
47 votes
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
Answer:

Related questions

33 votes
33 votes
4 answers
1
Arjun asked Feb 7, 2019
16,085 views
Suppose $Y$ is distributed uniformly in the open interval $(1,6)$. The probability that the polynomial $3x^2 +6xY+3Y+6$ has only real roots is (rounded off to $1$ decimal...
61 votes
61 votes
3 answers
2
Arjun asked Sep 26, 2014
17,287 views
Suppose you break a stick of unit length at a point chosen uniformly at random. Then the expected length of the shorter stick is ________ .