Binomial distribution parity 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)$?
 A: 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.
A: The effect of adding a Bernoulli$(p)$ on the parity applies this matrix 
$$M=\left(\begin{array}{cc} 1-p & p \\\ 
p & 1-p \end{array}\right)$$
to $(prob(even), prob(odd))$.
We can decompose the initial vector of $(1,0)$ for Binomial$(0,p)$  as the sum of the eigenvectors $(1/2,1/2)$ and $(1/2,-1/2)$ with eigenvalues $1$ and $1-2p$, respectively. So, the parity vector of Binomial$(n,p)$ is 
$(1,0)M^n = 1^n (1/2,1/2) + (1-2p)^n (1/2,-1/2)$.
$1/2 + (1-2p)^n /2$ even, $1/2 - (1-2p)^n / 2$ odd.
A: Some general remarks.  There is a family of linear operators $\phi_{a,d}$ which, given a generating function $f(x) = \sum f_n x^n$, returns the generating function $\sum f_{an+d} x^n$.  Observe that, for $\zeta$ a primitive $a^{th}$ root of unity,
$$f(\zeta^k x) = \sum_{i=0}^{a-1} \zeta^{ki} \phi_{a,i}(f(x)).$$
This is precisely the discrete Fourier transform matrix of order $a$, and inverting it tells us how to write down these operators $\phi_{a,d}$ explicitly and in particular to compute all sums of the form $\displaystyle \sum {n \choose ak+d}$; this case is $a = 2, d = 0$.  
In this particular case there is a dirty trick I like to employ.  Given a generating function $f(x) = \sum f_n x^n$, the generating function $g(x) = \sum g_n x^n$ where
$$g_n = \sum_{k=0}^{n} {n \choose k} f_k$$
satisfies
$$g(x) = \frac{1}{1 - x} f \left( \frac{x}{1 - x} \right).$$
One may deduce this using the Laplace transform, finite differences, or a combinatorial argument.  It allows us to evaluate the sums $\displaystyle \sum {n \choose ak+d}$ by setting $f(x) = \frac{x^d}{1 - x^a}$.  
Finally, there is a nice interpretation of the above sums in graph-theoretic terms.  Consider the family of undirected cyclic graphs $C_a$, consisting of $a$ vertices arranged in a regular $a$-gon with an edge between adjacent vertices.  Labeling the vertices $0, 1, 2, ... a-1$, the probability of starting at vertex $0$ and ending at vertex $2d-a$ in $n$ steps is precisely
$$\frac{1}{2^n} \sum {n \choose ak+d}.$$
This is because a choice of whether to move left or right for each of the $n$ steps determines a subset of $\{ 1, 2, ... n \}$ whose cardinality $\bmod a$ determines your final location.  Now one can compute these probabilities by computing the eigenvalues of the adjacency matrix of $C_a$ and even compute mixing times using standard graph-theoretic techniques.  (Of course one may reintroduce the parameter $p$ into the adjacency matrix to model a random walk in which preference is given to moving to the left or right.)
