TAOCP 1.2.10 Exercise 4

Section 1.2.10: Analysis of an Algorithm

Exercise 4. [M10] Give an explicit, closed formula for the values of $p_{nk}$ in the coin-tossing experiment, Eq. (17).

Verified: yes
Solve time: 1m10s

From Eq. (17), the recurrence for the probabilities is

$$ p_{nk}=p,p_{n-1,k-1}+q,p_{n-1,k}, $$

where $q=1-p$. The generating function therefore satisfies

$$ G_n(z)=(q+pz)^n $$

by Eq. (18). Expanding this by the binomial theorem gives

$$ G_n(z)=\sum_{k=0}^n \binom{n}{k} q^{,n-k}p^k z^k. $$

Since $G_n(z)=\sum_k p_{nk}z^k$, comparison of coefficients yields

$$ p_{nk}=\binom{n}{k}p^k q^{,n-k}, \qquad 0\le k\le n. $$

For $k<0$ or $k>n$, we have $p_{nk}=0$. Hence the probability distribution is

$$ \boxed{p_{nk}=\binom{n}{k}p^k(1-p)^{n-k}}. $$