Dark Mode

8,551 views

19 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______________

6

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.

2

37 votes

Best answer

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$.

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$.

38 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

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