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


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.

  • 1
    $\begingroup$ I just want to comment that the solutions by Douglas Zare and Qiaochu Yuan are also good. I just happen to like generating functions. $\endgroup$ – Michael Lugo Feb 24 '10 at 14:21

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.


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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.