In this paper, at the beginning of page 3, the formula below is given for calculating the expected hamming distance between two binary vectors, one random vector $\mathbf{A}$, and one vector $\mathbf{X}$ which is the result of "chunking" K random vectors (K=3,5,7,..), one of which is $\mathbf{A}$. $$\delta(\mathbf{X},\mathbf{A}) = {1 \over 2} - {K - 1 \choose 0.5(K-1)} / 2^K $$ Chunking here means to set each element in the output vector to 1 if the majority of inputs for corresponding elements is 1 and vice versa.
I would like to understand why that formula works.
If I try to solve the problem, I use the binomial formula, and sum up all the probabilities that $0.5(K - 1) + 1$ or more bits are different:
$$\delta(\mathbf{X},\mathbf{A}) = {K - 1 \choose 0.5(K -1) + 1}/2^{K-1} + {K - 1 \choose 0.5(K - 1) + 2}/2^{K-1} + \\ ... + {K - 1 \choose k - 1}/2^{K-1}$$
This formula gives results consistent with the formula in the article. But I don't see how my formula can be simplified to the first formula.
Your sum is equal to: $$ \frac{1}{2}\frac{1}{2^{K-1}}(\sum_{i=0}^{K-1}\binom{K-1}{i}-\binom{K-1}{(K-1)/2})= \frac{1}{2^K}(2^{K-1}-\binom{K-1}{(K-1)/2})=1/2-\binom{K-1}{(K-1)/2}/2^K $$
I used $2^n=(1+1)^n=\sum_{i=0}^n\binom{n}{i}$, $\binom{n}{i}=\binom{n}{n-i}$ and the fact that $K$ is odd.