# 随机算法 (Fall 2011)/Distributions of Coin Flipping

We introduce several important distributions induced by independent coin flips (independent probabilistic experiments), including: Bernoulli trial, geometric distribution, binomial distribution.

# Bernoulli trial (Bernoulli distribution)

Bernoulli trial describes the probability distribution of a single (biased) coin flip. Suppose that we flip a (biased) coin where the probability of HEADS is ${\displaystyle p}$. Let ${\displaystyle X}$ be the 0-1 random variable which indicates whether the result is HEADS. We say that ${\displaystyle X}$ follows the Bernoulli distribution with parameter ${\displaystyle p}$. Formally,

{\displaystyle {\begin{aligned}X&={\begin{cases}1&{\text{with probability }}p\\0&{\text{with probability }}1-p\end{cases}}\end{aligned}}}.

# Geometric distribution

Suppose we flip the same coin repeatedly until HEADS appears, where each coin flip is independent and follows the Bernoulli distribution with parameter ${\displaystyle p}$. Let ${\displaystyle X}$ be the random variable denoting the total number of coin flips. Then ${\displaystyle X}$ has the geometric distribution with parameter ${\displaystyle p}$. Formally, ${\displaystyle \Pr[X=k]=(1-p)^{k-1}p}$.

For geometric ${\displaystyle X}$, ${\displaystyle \mathbf {E} [X]={\frac {1}{p}}}$. This can be verified by directly computing ${\displaystyle \mathbf {E} [X]}$ by the definition of expectations. There is also a smarter way of computing ${\displaystyle \mathbf {E} [X]}$, by using indicators and the linearity of expectations. For ${\displaystyle k=0,1,2,\ldots }$, let ${\displaystyle Y_{k}}$ be the 0-1 random variable such that ${\displaystyle Y_{k}=1}$ if and only if none of the first ${\displaystyle k}$ coin flipings are HEADS, thus ${\displaystyle \mathbf {E} [Y_{k}]=\Pr[Y_{k}=1]=(1-p)^{k}}$. A key observation is that ${\displaystyle X=\sum _{k=0}^{\infty }Y_{k}}$. Thus, due to the linearity of expectations,

{\displaystyle {\begin{aligned}\mathbf {E} [X]=\mathbf {E} \left[\sum _{k=0}^{\infty }Y_{k}\right]=\sum _{k=0}^{\infty }\mathbf {E} [Y_{k}]=\sum _{k=0}^{\infty }(1-p)^{k}={\frac {1}{1-(1-p)}}={\frac {1}{p}}.\end{aligned}}}

# Binomial distribution

Suppose we flip the same (biased) coin for ${\displaystyle n}$ times, where each coin flip is independent and follows the Bernoulli distribution with parameter ${\displaystyle p}$. Let ${\displaystyle X}$ be the number of HEADS. Then ${\displaystyle X}$ has the binomial distribution with parameters ${\displaystyle n}$ and ${\displaystyle p}$. Formally, ${\displaystyle \Pr[X=k]={n \choose k}p^{k}(1-p)^{n-k}}$.

A binomial random variable ${\displaystyle X}$ with parameters ${\displaystyle n}$ and ${\displaystyle p}$ is usually denoted by ${\displaystyle B(n,p)}$.

As we saw above, by applying the linearity of expectations, it is easy to show that ${\displaystyle \mathbf {E} [X]=np}$ for an ${\displaystyle X=B(n,p)}$.