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

Let $S = \sum_{i=1}^n a_i x_i$. The parity of $S$ is equivalent to computing $S \pmod 2$.

Since $a$ is a non-zero binary vector, it has at least one component $a_k = 1$.

We can split the sum as: $$S = a_k x_k + \sum_{i e k} a_i x_i = x_k + \sum_{i e k} a_i x_i$$

Since $x$ is chosen uniformly at random from $\{0, 1\}^n$, the components $x_1, x_2, \dots, x_n$ are independent and identically distributed Bernoulli random variables with $\Pr(x_i = 0) = \Pr(x_i = 1) = \frac{1}{2}$.

Conditioning on any choice of $(x_i)_{i e k}$, the sum $\sum_{i e k} a_i x_i$ evaluates to some integer $C$. Then:

Since $x_k$ is independent of $(x_i)_{i e k}$ and takes values $0$ and $1$ with equal probability $1/2$: $$\Pr(S \text{ is odd} \mid (x_i)_{i e k}) = \Pr(x_k + C \text{ is odd}) = \frac{1}{2}$$

By the law of total probability, the overall probability is:

Thus, the answer is 0.5.