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

From EtoneWiki
Jump to: navigation, search

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,

.

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 . 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,

Binomial distribution

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 .