Let $X \text{~} \text{Binomial}(n, p)$.


What is $\text{P}[X \mod 2 = 0]$? Is it of the form $1/2 + O(1/2^n)$?



Binomial distribution parity
This probability is in fact $1/2 + (1-2p)^n/2$.


Here's a proof. The probability generating function of $X$ is $f(z) = (q+pz)^n$, where $q = 1-p$. That is, the coefficient of $z^k$ in $(q+pz)^n$ is the probability $P(X=k)$.


Now, consider $(f(z)+f(-z))/2$. This polynomial contains just the terms of $f(z)$ which contain $z$ to some even power. If we set $z = 1$, then we get just the sum of those terms. So the probability you want is $(f(1)+f(-1))/2$.


For example, if $n = 3$ we have 
$$f(z) = q^3 + 3 p q^2 z + 3 p^2 q z^2 + p^3 z^3$$
$${f(z) + f(-z) \over 2} = q^3 + 3 p^2 q z^2$$
$${f(1) + f(-1) \over 2} = q^3 + 3 p^2 q$$.


Now, we have
$$ {f(1) + f(-1) \over 2} = {(q+p)^n + (q-p)^n \over 2} = {1 + (1-2p)^n \over 2} $$
which is the result.


