Binomial distribution parity

Question

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)$?

Answer 1

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.

Answer 2

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.

Answer 3

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