随机算法 (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 . Let be the 0-1 random variable which indicates whether the result is HEADS. We say that follows the Bernoulli distribution with parameter . Formally,
Suppose we flip the same coin repeatedly until HEADS appears, where each coin flip is independent and follows the Bernoulli distribution with parameter . Let be the random variable denoting the total number of coin flips. Then has the geometric distribution with parameter . Formally, .
For geometric , . This can be verified by directly computing by the definition of expectations. There is also a smarter way of computing , by using indicators and the linearity of expectations. For , let be the 0-1 random variable such that if and only if none of the first coin flipings are HEADS, thus . A key observation is that . Thus, due to the linearity of expectations,
Suppose we flip the same (biased) coin for times, where each coin flip is independent and follows the Bernoulli distribution with parameter . Let be the number of HEADS. Then has the binomial distribution with parameters and . Formally, .
A binomial random variable with parameters and is usually denoted by .
As we saw above, by applying the linearity of expectations, it is easy to show that for an .