A biased coin showing heads with probability p ∈ (0, 1) is tossed n times. Find the probability that the total number of heads is a) even b) divisible by 3.
For the following solution I am confused about part b "identity we wrote is an equality for polynomials on R" what is the identity and what is the polynomial?
Secondly, "Since the identity we wrote is an equality for polynomials on R, it in fact holds for all complex numbers t" why does this imply that complex numbers t work as well?
Thirdly, i dont understand the root of unity part or how it is derived to $\frac {G(1) + G(ε) + G(ε^2)} 3$ part. Please explain thanks.
Solution. Let X be the number of heads. We have X ∼ Bin(n, p) and let us write its probability generating function G(t), $G(t) = (1 − p + tp)^n = P (X = 0) + tP (X = 1) + t^2P (X = 2) + . . . + t^nP (X = n).$
a) We would like to find P (X is even) = P (X = 0) + P (X = 2) + . . .. We have $$\frac {G(t) + G(−t)} 2 = P (X = 0) + t^2P (X = 2) + . . . $$ thus $$P (X is even) = \frac {G(t) + G(−t)} 2 =\frac {1+(1−2p)^n} 2$$
b) Since the identity we wrote is an equality for polynomials on R, it in fact holds for all complex numbers t. We would like to find P (3 divides X) = P (X = 0) + P (X = 3) + . . .. Let ε = $e^{2πi/3}$ be a third root of unity. Since $1^k + ε^k + (ε^2)^k$ is zero unless k is a multiple of 3, in which case it is 3, we get
$$\frac {G(1) + G(ε) + G(ε^2)} 3 = P (X = 0) + P (X = 3) + . . . .$$
The identity is \begin{align*} (1 - p + tp)^n = P (X = 0) + tP (X = 1) + t^2P (X = 2) + . . . + t^nP (X = n)\tag{1} \end{align*} where both sides represent a polynomial in $t$ having degree $n$ with equal coefficients.
This is due to the Identity theorem. The polynomials in (1) are holomorphic functions which are also defined on $\mathbb{C}$. Since left-hand side and right-hand side agree on $\mathbb{R}$ which is a subset of $\mathbb{C}$ with accumulation points, the identity is valid in $\mathbb{C}$.
Note: Similarly we can show for instance that from the validity of the identity $\cos(z)=\frac{e^{iz}+e^{-iz}}{2}$ for $z\in\mathbb{R}$ the validity for $z\in \mathbb{C}$ follows. See this MSE post for more information.
The $r$-th roots of unity $\varepsilon_j=\exp\left(\frac{2\pi ij}{r}\right), 0\leq j<r$ have the nice property to filter elements. For $r>0$ we obtain \begin{align*} \frac{1}{r}\sum_{j=0}^{r-1}\exp\left(\frac{2\pi ij n}{r}\right)= \begin{cases} 1&\qquad r\mid n\\ 0& \qquad \text{otherwise} \end{cases} \end{align*}
See this MSE answer for some details and H.Wilf's Generatingfunctionology (2.4.4) - (2.4.9) for more information.