GATE CSE 2020 Q55: Probability that a·x is odd for a random binary vector x

Engineering Mathematics
2 marks
NAT
No negative marking

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 $\sum_{i=1}^{n} a_i x_i$ is an odd number is _______.

Try it: numerical answer: type the value

Your answer

Numerical answer. No negative marking.

Show answer and explanation

Answer: 0.5 (official GATE 2020 final answer key)

Concept used: Parity of a sum over a fixed non-empty subset of uniformly random bits.

First step: Pick one index $j$ with $a_j = 1$ ; for any fixed values of the other bits, flipping $x_j$ flips the parity.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2020 CS question paper and final answer key, organised by IIT Delhi. Question paper · Answer key

PracticePractise Engineering Mathematics questions →Full paperAll GATE CSE 2020 questions →

GATE CSE 2020 Q55: Probability that a·x is odd for a random binary vector x

Question

Full step-by-step solution

More Engineering Mathematics PYQs