2.2b.3 Binomial Distribution

Binomial Distribution

A discrete random variable $X\ge 0$ follows the Binomial distribution $X\sim \text{Bin}(n,p)$ if it represents the number of successes in (i.e., the sum of) $n$ independent Bernoulli trials, where each trial has a probability $p$ of success. Formally, the Binomial distribution of a random variable is given by the PMF,
$p_X(x)=\left(\genfrac{}{}{0ex}{}{n}{x}\right)p^x(1-p{)}^{n-x},$
where $\left(\genfrac{}{}{0ex}{}{n}{x}\right)=\frac{n!}{x!(n-x)!}$ is the binomial coefficient, $p^k$ is the probability of exactly $k$ successes, and $(1-p{)}^{n-x}$ is the probability of the remaining trials being failures.

Properties

(Mean) $\mathbb{E}[X\sim \text{Bin}(n,p)]=np.$

(Variance) $\text{Var}[X\sim \text{Bin}(n,p)]=np(1-p)$.

\operatorname{Var}(X) &= \mathbb{E}(X^2) - \mathbb{E}(X)^2 \\ &= \sum_{i=1}^{n} \mathbb{E}(I_{i}) + \sum_{i \ne j}^{n}\mathbb{E}(I_{i}I_{j}) - n^2p^2 \\ &= np + n(n-1)p^2 - n^2p^2 \\ &= np + n^2p^2-np^2-n^2p^2 \\ &= np-np^2 \\ &= np(1-p). \end{align}$$ Since there are exactly $n(n-1)$ ordered distinct pairs of $i, j$ and $I_{i} \sim_{\text{iid}} \text{Ber}(p)$, so $\mathbb{E}(I_{i}I_{j})=\mathbb{E}(I_{i})\mathbb{E}(I_{j})$ for $i \neq j$. #### (*MGF*) $\mathbb{E}[e^{tX}]=(1-p+pe^t)^n$. #### (Sum) Let $X=\sum\limits^{n}_{i=1}X_{i}$, where $X_{i} \sim_{\text{iid}} \text{Bin}(n_{i}, p)$. Then, $X \sim \text{Bin}\left( \sum\limits_{i=1}^{n}n_{i}, \; p \right)$. # Examples >[!example] Packet Routing > >Consider a system with $n$ inputs and $n$ outputs. At each input, a packet appears independently with probability $p$. If a packet appears, it is destined for one of the $n$ outputs uniformly randomly, independently of the other packets. > > >>[!example]- Let $X$ denote the number of packets destined for the first output. What is the distribution of $X$? >>Let $A$ be the event that the packet appears, and let $B_{i}$ be the event that the packet hits the $i$-th output. Then, $\mathbb{P}(A \cap B_{i})=\mathbb{P}(A)\mathbb{P}(B_{i})=p\frac{1}{n}=\frac{p}{n}$ by independence. The distribution of $X$ can be modeled as $\operatorname{Bin}(n, \frac{p}{n})$. There are $n$ independent Bernoulli trials, and each trial has the same probability of success $\frac{p}{n}$. > >>[!example]- What is the probability of a *collision* (that is, more than one packet heading to the same output)? >>Let $X=X_{1}+X_{2}+\ldots+X_{n}$ denote the total number of packets, where each $X_{i}$ denotes the number of packets destined for the $i$.-th output. Then, $X \sim \operatorname{Bin}(n, p)$, since every packet is generated by one of the $n$ inputs with probability $p$ and goes to exactly one output with probability $\frac{1}{n}$, so counting the packets at each output and summing them gives the total number of packets generated. We have that: >>$$$$