in Probability retagged by
8,551 views
19 votes
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______________
in Probability retagged by
by
8.6k views

3 Comments

I have got 0.476 as answer will it be considered as 0.5?
1
1

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
2

2 Answers

37 votes
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$.
selected by

4 Comments

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

Will it not make every vector even?
1
1
pradhanaditya What if we take a =(1,1,0)
0
0
38 votes
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

4 Comments

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

see this

3
3

Wow thanks! this is awesome 

1
1
Answer: